Counting the number of dissociation sets in cubic graphs

Jianhua Tu; Junyi Xiao; Rongling Lang; Jianhua Tu; Junyi Xiao; Rongling Lang

doi:10.3934/math.2023507

AIMS Mathematics

2023, Volume 8, Issue 5: 10021-10032. doi: 10.3934/math.2023507

Previous Article Next Article

Research article

Counting the number of dissociation sets in cubic graphs

1.
School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China
2.
Department of Mathematics, Beijing University of Chemical Technology, Beijing 100029, China
3.
School of Electronics and Information Engineering, Beihang University, Beijing 100191, China

Received: 28 September 2022 Revised: 09 February 2023 Accepted: 15 February 2023 Published: 23 February 2023
MSC : 05A17, 05C31, 05C69

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) = \sum_{D \in \mathcal{D}(G)} \lambda^{|D|} $, where $ \mathcal{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 \in(0, 1] $,

$ \frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda) $

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, $ |\mathcal{D}(G)|\leq|\mathcal{D}(K_4)|^{n/4} = 11^{n/4}. $
- extremal graph theory,
- counting,
- cubic graphs,
- dissociation sets,
- graph polynomials
Citation: Jianhua Tu, Junyi Xiao, Rongling Lang. Counting the number of dissociation sets in cubic graphs[J]. AIMS Mathematics, 2023, 8(5): 10021-10032. doi: 10.3934/math.2023507

Related Papers:

Abstract

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) = \sum_{D \in \mathcal{D}(G)} \lambda^{|D|} $, where $ \mathcal{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 \in(0, 1] $,

$ \frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda) $

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, $ |\mathcal{D}(G)|\leq|\mathcal{D}(K_4)|^{n/4} = 11^{n/4}. $

References

[1]	J. Cutler, A. J. Radcliffe, Minimizing the number of independent sets in triangle-free regular graphs, Discrete Math., 341 (2018), 793–800. https://doi.org/10.1016/j.disc.2017.11.016 doi: 10.1016/j.disc.2017.11.016
[2]	E. Davies, M. Jenssen, W. Perkins, B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc., 96 (2017), 47–66. https://doi.org/10.1112/jlms.12056
[3]	E. Davies, M. Jenssen, W. Perkins, B. Roberts, Extremes of the internal energy of the Potts model on cubic graphs, Random Struct. Algor., 53 (2018), 59–75. https://doi.org/10.1002/rsa.20767 doi: 10.1002/rsa.20767
[4]	D. Galvin, P. Tetali, On weighted graph homomorphisms, Discrete Math. Theor. Comput. Sci., 63 (2004), 97–104. https://doi.org/10.1090/dimacs/063/07 doi: 10.1090/dimacs/063/07
[5]	J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput., 10 (2001), 219–237. https://doi.org/10.1017/S0963548301004631 doi: 10.1017/S0963548301004631
[6]	G. Perarnau, W. Perkins, Counting independent sets in cubic graphs of given girth, J. Combin. Theory Ser. B, 133 (2018), 211–242. https://doi.org/10.1016/j.jctb.2018.04.009 doi: 10.1016/j.jctb.2018.04.009
[7]	M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981). https://doi.org/10.1137/0210022
[8]	Y. F. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput., 19 (2010), 315–320. https://doi.org/10.1017/S0963548309990538 doi: 10.1017/S0963548309990538

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)