آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,578 |
| تعداد مشاهده مقاله | 1,707,519 |
| تعداد دریافت فایل اصل مقاله | 1,590,793 |
A note on independent domination in almost-regular graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 10، دوره 11، شماره 4، اسفند 2026، صفحه 1175-1180 اصل مقاله (332.11 K) | ||
| نوع مقاله: Short notes | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31146.2756 | ||
| نویسندگان | ||
| Wayne Goddard* 1، 2؛ Michael A. Henning2 | ||
| 1School of Mathematical and Statistical Sciences, Clemson University, Clemson, USA | ||
| 2Department of Mathematics and Applied Mathematics, University of Johannesburg Auckland Park, 2006 South Africa | ||
| چکیده | ||
| A classic result in domination theory is that a regular graph has independent domination number at most half the order. We strengthen this result to ``almost-regular'' graphs by showing that if a graph has minimum degree $\delta > 0$ and maximum degree at most $\delta + 3$, and the subgraph induced by the vertices of degree $\delta + 3$ (if any) is bipartite, then the independent domination number is at most half the order. We also discuss related questions. | ||
| کلیدواژهها | ||
| independent domination؛ almost-regular graph؛ one-half bound | ||
| مراجع | ||
|
[1] A. Akbari, S. Akbari, Doosthosseini, A.Z. A.Z. Hadizadeh, M.A. Henning, and A. Naraghi, Independent domination in subcubic graphs, J. Combin. Optim. 43 (2022), 28–41. https://doi.org/10.1007/s10878-021-00743-z
[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. Combin. Theory Ser. B 158 (2023), no. 2, 341–352. https://doi.org/10.1016/j.jctb.2022.10.004
[4] E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976), no. 3, 213–222. https://doi.org/10.1016/0012-365X(76)90026-1
[5] 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
[6] 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
[7] W. Goddard and M.A. Henning, Acyclic total dominating sets in cubic graphs, Appl. Anal. Discrete Math. 13 (2019), 73–84.
[8] W. Goddard, M.A. Henning, J. Lyle, and J. Southey, On the independent domination number of regular graphs, Annals Combin. 16 (2012), 719–732. https://doi.org/10.1007/s00026-012-0155-4
[9] J. Haviland, Upper bounds for independent domination in regular graphs, Discrete Math. 307 (2007), no. 21, 2643–2646. https://doi.org/10.1016/j.disc.2007.01.001
[10] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in graphs: Core concepts, Springer Monographs in Mathematics, Springer, Cham, 2023.
[11] 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
[12] C. Payan, Coverings by minimal transversals, Discrete Math. 23 (1978), no. 3, 273–277. https://doi.org/10.1016/0012-365X(78)90008-0
[13] L. Sun and J. Wang, An upper bound for the independent domination number, J. Combin. Theory Ser. B 76 (1999), no. 2, 240–246. https://doi.org/10.1006/jctb.1999.1907 | ||
|
آمار تعداد مشاهده مقاله: 169 تعداد دریافت فایل اصل مقاله: 128 |
||