Counting the number of dissociation sets in cubic graphs

Let G be a graph. A dissociation set of G is a subset of vertices that induces a subgraph with vertex degree at most 1. The dissociation polynomial of G is D-G(lambda) = Sigma(lambda vertical bar D vertical bar)(D is an element of D(G)), where D(G) is the set of all dissociation sets of G. In this paper, we prove that for any cubic graph G and any lambda is an element of (0, 1], [GRAPHICS] . with equality if and only if G is a disjoint union of copies of the complete graph K-4. When lambda = 1, the value of D-G(lambda) is exactly the number of dissociation sets of G. Hence, for any cubic graph G on n vertices, vertical bar D(G)vertical bar <= vertical bar D(K-4)vertical bar(n/4) = 11(n/4).

Automated summary

Given a graph G, a dissociation set is a subset of vertices inducing a subgraph with vertex degree at most 1. The dissociation polynomial is defined as D-G(lambda) = Sigma(lambda | D |)(D ∈ D(G)), where D(G) denotes the set of all dissociation sets of G. In this paper, it is proved that for any cubic graph G and any lambda ∈ (0, 1], [GRAPHICS], with equality if and only if G is a disjoint union of copies of the complete graph K-4. When lambda = 1, the value of D-G(lambda) is exactly the number of dissociation sets of G. Hence, for any cubic graph G on n vertices, |D(G)| <= |D(K-4)|(n/4) = 11(n/4).