Independent domination, order, size, and maximum degree

Dantas, Simone; Henning, Michael A.; Arelis Baldeon Penao, Giovanna; Rautenbach, Dieter

doi:10.22049/cco.2025.30756.2609

تعداد نشریات	6
تعداد شماره‌ها	126
تعداد مقالات	1,592
تعداد مشاهده مقاله	1,807,635
تعداد دریافت فایل اصل مقاله	1,674,271

	Independent domination, order, size, and maximum degree
Communications in Combinatorics and Optimization
مقاله 2، دوره 11، شماره 4، اسفند 2026، صفحه 1073-1080 اصل مقاله (358.36 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2025.30756.2609
نویسندگان
Simone Dantas¹؛ Michael A. Henning²؛ Giovanna Arelis Baldeon Penao¹؛ Dieter Rautenbach^* ³
¹Instituto de Matemática e EstatÍstica, Universidade Federal Fluminense, Niterói, Brazil
²Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa
³Institute of Optimization and Operations Research, Ulm University, Ulm, Germany
چکیده
For a connected graph $G$ with $n>2\Delta$ vertices, $m$ edges, and maximum degree at most $\Delta\geq 3$, we show $i(G)\leq \left(1-\Omega\left(\frac{1}{\Delta^4}\right)\right)n-\frac{m}{\Delta}+O\left(\frac{1}{\Delta^2}\right)$ and discuss related problems.
کلیدواژه‌ها
independent domination؛ regular graph؛ bound

مراجع
[1] C. Berge, The Theory of Graphs and Its Applications, John Wiley & Sons, Inc., New York, 1962. [2] E.K. Cho, I. Choi, and B. Park, On independent domination of regular graphs, J. Graph Theory 103 (2023), no. 1, 159–170. https://doi.org/10.1002/jgt.22912 [3] E.K. Cho, J. Kim, M. Kim, and S. Oum, Independent domination of graphs with bounded maximum degree, J. Comb. Theory, Ser. B 158 (2023), 341–352. https://doi.org/10.1016/j.jctb.2022.10.004 [4] E.K. Cho and M. Kim, Independent domination versus packing in subcubic graphs, Discrete Appl. Math. 357 (2024), 132–134. https://doi.org/10.1016/j.dam.2024.06.007 [5] E.J. Cockayne, O. Favaron, H. Li, and G. MacGillivray, The product of the independent domination numbers of a graph and its complement, Discrete Math. 90 (1991), no. 3, 313–317. https://doi.org/10.1016/0012-365X(91)90151-Q [6] E.J. Cockayne, O. Favaron, C. Payan, and A.G. Thomason, Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math. 33 (1981), no. 3, 249–258. https://doi.org/10.1016/0012-365X(81)90268-5 [7] E.J. Cockayne and S.T. Hedetniemi, Independence graphs, Cong. Numer. 10 (1974), 471–491. [8] P. Dankelmann, G.S. Domke, W. Goddard, P. Grobler, J.H. Hattingh, and H.C. Swart, Maximum sizes of graphs with given domination parameters, Discrete Math. 281 (2004), no. 1-3, 137–148. https://doi.org/10.1016/j.disc.2003.07.010 [9] P. Erdös and P. Kelly, The minimal regular graph containing a given graph, A Seminar on Graph Theory, Holt, Rinehart and Winston, New York-Toronto, 1967, pp. 65–69. [10] O. Favaron, On a conjecture of fink and jacobson concerning $k$-domination and $k$-dependence, J. Comb. Theory, Ser. B 39 (1985), no. 1, 101–102. https://doi.org/10.1016/0095-8956(85)90040-1 [11] O. Favaron, Stability, domination and irredundance in a graph, J. Graph Theory 10 (1986), no. 4, 429–438. https://doi.org/10.1002/jgt.3190100402 [12] O. Favaron,$ $k-domination and $k$-independence in graphs, Ars Combin. 25 (1988), 159–167. [13] O. Favaron, Two relations between the parameters of independence and irredundance, Discrete Math. 70 (1988), no. 1, 17–20. https://doi.org/10.1016/0012-365X(88)90076-3 [14] O. Favaron, A bound on the independent domination number of a tree, Vishwa Internat. J. Graph Theory 1 (1992), 19–27. [15] O. Favaron, Global alliances and independent domination in some classes of graphs, Electron. J. Comb. 15 (2008), Article number: R123. https://doi.org/10.37236/847 [16] O. Favaron, T.W. Haynes, and P.J. Slater, Distance-$k$ independent domination sequences, J. Comb. Math. Comb. Comput. 33 (2000), 225–237. [17] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), no. 7, 839–854. https://doi.org/10.1016/j.disc.2012.11.031 [18] J. Haviland, On independent domination and size, Australas. J. Comb. 42 (2008), 279–284. [19] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, 2023. [20] P.C.B. Lam, W.C. Shiu, and L. Sun, On independent domination number of regular graphs, Discrete Math. 202 (1999), no. 1-3, 135–144. https://doi.org/10.1016/S0012-365X(98)00350-1 [21] O. Ore, Theory of Graphs, American Math. Soc., 1962. [22] M. Rosenfeld, Independent sets in regular graphs, Isr. J. Math. 2 (1964), no. 4, 262–272. https://doi.org/10.1007/BF02759743
آمار تعداد مشاهده مقاله: 394 تعداد دریافت فایل اصل مقاله: 440

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Independent domination, order, size, and maximum degree