The domination polynomial $D(G,x)$ of a graph $G$ is the generating function its dominating sets. We prove that satisfies wide range reduction formulas. show linear recurrence relations for arbitrary graphs and various special cases. give splitting formulas based on articulation vertices, more generally, sets vertices.

Motivated by the definition of edge elimination polynomial a graph we define covered components counting spanning subgraphs with respect to their number components, edges and components. We prove recurrence relation, which shows that both polynomials are substitution instances each other. give some properties results concerning relations other polynomials.

We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial graph to sums type $\sum_{A\subseteq S} f(A)$ where $S$ is finite set and $f$ mapping from power into an abelian group. give applications domination subgraph component graph, hypergraph, characteristic Crapo's beta invariant matroid, principle inclusion-exclusion. Thus, we discover several known new results in concise unified way. As further our main result, derive maximums-minimums identity...

Whitney's Broken-cycle Theorem states the chromatic polynomial of a graph as sum over special edge subsets.We give definition cycles in hypergraphs that preserves statement theorem there.

The matching polynomial of a graph is the generating function numbers its matchings with respect to their cardinality. A reconstructible, if value for can be determined from values vertex-deleted subgraphs same graph. This note discusses reconstructibility polynomial. We collect previous results, prove it graphs pendant edges and disprove some graphs.

Abstract Let be a graph and the number of independent (vertex) sets G . Then Merrifield–Simmons conjecture states that sign term only depends on parity distance vertices in We prove holds for bipartite graphs by considering generalization term, where vertex subsets instead are deleted.

We give some insight into Tutte's definition of internally and externally active edges for spanning forests. Namely we prove, that every edge subset can be constructed from the exactly one forest by deleting a unique adding edges.

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then set partition $\pi=\{V_1, \ldots, V_k\}$ of the vertex $G$ is connected if each subgraph $G[V_j]$ induced by blocks $V_j$ $\pi$ for $1\le j\le k$. Define $q_{i}(G)$ as number partitions in $i$ blocks. The polynomial $Q(G, x)=\sum_{i=0}^n q_{i}(G)x^i$. This paper presents splitting approach to on separating $X$ and summarizes some properties bond lattice. Furthermore bivariate $Q(G,x,y)=\sum_{i=1}^n \sum_{j=1}^m...

The Merrifield-Simmons conjectures states a relation between the distance of vertices in simple graph $G$ and number independent sets, denoted as $σ(G)$, vertex-deleted subgraphs. Namely, that sign term $σ(G_{-u}) \cdot σ(G_{-v}) - σ(G) σ(G_{-u-v})$ only depends on parity $u$ $v$ $G$. We prove this statement case graphs give some evidence result may not be further generalized to other classes graphs.

The matching polynomial of a graph is the generating function numbers its matchings with respect to their cardinality. A reconstructible, if value for can be determined from values vertex-deleted subgraphs same graph. This note discusses reconstructibility polynomial. We collect previous results, prove it graphs pendant edges and disprove some graphs.

Averbouch, Godlin and Makowsky define the edge elimination polynomial of a graph by recurrence relation with respect to deletion, contraction extraction an edge. It generalizes some well-known polynomials such as chromatic matching polynomial. By introducing two equivalent polynomials, one enumerating subgraphs other colorings, we show that simple is reconstructible from its deck it encodes degree sequence arbitrary graph.

The independence polynomial of a hypergraph is the generating function for its independent (vertex) sets with respect to their cardinality. This article aims discuss several recurrence relations using some vertex and edge operations. Further, an extension well-known relation simple graphs hypergraphs proven other novel are also discussed.

We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial graph to sums type $\sum_{A\subseteq S} f(A)$ where $S$ is finite set and $f$ mapping from power into an abelian group. give applications domination subgraph component graph, hypergraph, characteristic Crapo's beta invariant matroid, principle inclusion-exclusion. Thus, we discover several known new results in concise unified way. As further our main result, derive maximums-minimums identity...

We give some insight into Tutte's definition of internally and externally active edges for spanning forests. Namely we prove, that every edge subset can be constructed from the exactly one forest by deleting a unique adding edges.

Motivated by the definition of edge elimination polynomial a graph we define covered components counting spanning subgraphs with respect to their number components, edges and components. We prove recurrence relation, which shows that both polynomials are substitution instances each other. give some properties results concerning relations other polynomials.