آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 127 |
| تعداد مقالات | 1,609 |
| تعداد مشاهده مقاله | 1,821,307 |
| تعداد دریافت فایل اصل مقاله | 1,691,822 |
Average size of 1-nearly independent vertex sets | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 01 مهر 1405 | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31202.2779 | ||
| نویسندگان | ||
| Audace A.V. Dossou-Olory1؛ Eric O.D. Adriantiana* 2، 3 | ||
| 1Institut National de l’Eau, Centre d’Excellence d’Afrique pour l’Eau et l’Assainissement and Institut de Mathématiques et de Sciences Physiques, Dangbo, Université d’Abomey-Calavi, Bénin | ||
| 2Department of Mathematics (Pure and Applied), Rhodes University, Makhanda, 6140 South Africa | ||
| 3National Institute for Theoretical and Computational Sciences (NITheCS), Stellenbosch, South Africa | ||
| چکیده | ||
| A $k$-nearly independent vertex subset of a graph $G$ is a set of vertices that induces a subgraph containing exactly $k$ edges. For $k = 0$, this coincides with the classical notion of independent subsets. This paper investigates the average size, $av_1(G)$ of the $1$-nearly independent vertex subsets of both graphs and trees of a given order $n$. Let $E_n$ denote the $n$-vertex edgeless graph, so that $av_1(E_n) = 0$. We determine all $n$-vertex graphs $G\neq E_n$ that minimize or maximize $av_1$. Similarly, we identify the trees of order $n$ that achieve the minimum value of $av_1$, and prove that the maximum value lies between $n/2$ and $(n+1)/2$ if $n>8$. Finally, we construct a family of $n$-vertex trees which attains the upper bound with an additive error tending to zero, as $n$ tends to infinity. | ||
| کلیدواژهها | ||
| 1-nearly independent vertex sets؛ extremal graph structures؛ average size | ||
| مراجع | ||
|
[1] E.O.D. Andriantiana, Energy, Hosoya index and Merrifield–Simmons index of trees with prescribed degree sequence, Discrete Appl. Math. 161 (2013), no. 6, 724–741. https://doi.org/10.1016/j.dam.2012.10.010
[2] E.O.D. Andriantiana, V. Razanajatovo Misanantenaina, and S. Wagner, The average size of independent sets of graphs, Eur. J. Math. 6 (2020), no. 2, 561–576. https://doi.org/10.1007/s40879-019-00333-8
[3] E.O.D. Andriantiana and Z.B. Shozi, The number of 1-nearly independent vertex subsets, Quaest. Math. 47 (2024), no. 12, 2353–2373. https://doi.org/10.2989/16073606.2024.2367714
[4] E.O.D. Andriantiana and Z.B. Shozi, The number of 1-nearly independent edge subsets, Iranian J. Math. Chem. 16 (2025), no. 1, 65–84. https://doi.org/10.22052/ijmc.2024.254977.1871
[5] E. Davies, M. Jenssen, W. Perkins, and B. Roberts, On the average size of independent sets in triangle-free graphs, Proc. Amer. Math. Soc. 146 (2018), no. 1, 111–124. http://doi.org/10.1090/proc/13728
[6] D. Galvin, Two problems on independent sets in graphs, Discrete Math. 311 (2011), no. 20, 2105–2112. https://doi.org/10.1016/j.disc.2011.06.015
[7] W. Gan, P.S. Loh, and B. Sudakov, Maximizing the number of independent sets of a fixed size, Combin. Probab. Comput. 24 (2015), no. 3, 521–527. https://doi.org/10.1017/S0963548314000546
[8] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), no. 3, 219–237. https://doi.org/10.1017/S0963548301004631
[9] R.D. Martin, Statistical mechanics of the independent set problem, Discrete Math. 309 (2009), no. 10, 3323–3331.
[10] A. Nilli, The average size of an independent set in graphs with a given chromatic number, J. Combin. Theory Ser. B 45 (1988), no. 1, 112–114. https://doi.org/10.1016/0095-8956(88)90060-3
[11] Y. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315–320. https://doi.org/10.1017/S0963548309990538 | ||
|
آمار تعداد مشاهده مقاله: 3 |
||