Publications
Sort:
Open Access Research Article Issue
Counting the number of dissociation sets in cubic graphs
AIMS Mathematics 2023, 8(5): 10021-10032
Published: 15 May 2023
Abstract PDF (219.5 KB) Collect
Downloads:1

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 ( λ ) = D D ( G ) λ | D | , 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 λ ( 0 , 1 ],

1 | V ( G ) | ln D G ( λ ) 1 4 ln D K 4 ( λ )

with equality if and only if G is a disjoint union of copies of the complete graph K 4 . When λ = 1, the value of D G ( λ ) 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 .

Total 1