Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set

• Autorzy: Haynes Teresa W. , Henning Michael A.

Identyfikatory

DOI

10.7494/OpMath.2025.45.2.179

• Języki publikacji: EN

Abstrakty

EN

A graph G whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We define the TI-augmentation number ti(G) of a graph G to be the minimum number of edges that must be added to G to ensure that the resulting graph is a TI-graph. We show that every tree T of order n ≥ 5 satisfies ti(T) ≤ 1/5n. We prove that if G is a bipartite graph of order n with minimum degree δ(G) ≥ 3, then ti(G) ≤ 1/4n, and if G is a cubic graph of order n, then ti(G) ≤ 1/3n. We conjecture that ti(G) ≤ 1/6n for all graphs G of order n with δ(G) ≥ 3, and show that there exist connected graphs G of sufficiently large order n with δ(G) ≥ 3 such that ti(T) ≥ (1/6− ε)n for any given ε > 0.

Słowa kluczowe

EN

total domination; independent domination; vertex partitions

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 2
• Strony: 179--198
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Haynes Teresa W.

• Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614–0002 USA
• University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa

• https://orcid.org/0000-0002-0865-0871

autor

Henning Michael A.

• University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa

• https://orcid.org/0000-0001-8185-067X

Bibliografia

• [1] D.W. Bange, A.E. Barkauskas, P.J. Slater, Disjoint dominating sets in trees, Sandia Laboratories Rept. SAND-78–1087J, 1978.
• [2] I. Broere, M. Dorfling, W. Goddard, J.H. Hattingh, M.A. Henning, E. Ungerer, Augmenting trees to have two disjoint total dominating sets, Bull. Inst. Combin. Appl. 42 (2004), 12–18.
• [3] W. Cames van Batenburg, J. Goedgebeur, G. Joret, Large independent sets in triangle-free cubic graphs: beyond planarity, Adv. Comb. (2020), Paper no. 7.
• [4] P. Delgado, W.J. Desormeaux, T.W. Haynes, Partitioning the vertices of a graph into a total dominating set and an independent dominating set, Ars Combin. 144 (2019), 367–379.
• [5] W.J. Desormeaux, T.W. Haynes, M.A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017), 52–63.
• [6] M. Dorfling, W. Goddard, J.H. Hattingh, M.A. Henning, Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets, Discrete Math. 300 (2005), 82–90.
• [7] K. Fraughnaugh, S.C. Locke, 11/30 (Finding large independent sets in connected triangle-free 3-regular graphs), J. Combin. Theory Ser. B 65 (1995), no. 1, 51–72.
• [8] W. Goddard, M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), 839–854.
• [9] T.W. Haynes, M.A. Henning, Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set, Opuscula Math. 44 (2024), no. 4, 543–563.
• [10] T.W. Haynes, M.A. Henning, Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set, Australas. J. Combin. 89 (2024), 97–115.
• [11] T.W. Haynes, M.A. Henning, A characterization of graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set, Discrete Appl. Math. (to appear).
• [12] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs, Series: Developments in Mathematics, vol. 64, Springer, Cham, 2020.
• [13] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Series: Developments in Mathematics, vol. 66, Springer, Cham, 2021.
• [14] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts, Series: Springer Monographs in Mathematics, Springer, Cham, 2023.
• [15] P. Heggernes, J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998), 128–142.
• [16] M.A. Henning, C. Löwenstein, D. Rautenbach, Partitioning a graph into a dominating set, a total dominating set, and something else, Discuss. Math. Graph Theory 30 (2010), no. 4, 563–574.
• [17] M.A. Henning, C. Löwenstein, D. Rautenbach, J. Southey, Disjoint dominating and total dominating sets in graphs, Discrete Appl. Math. 158 (2010), 1615–1623.
• [18] M.A. Henning, I. Peterin, A characterization of graphs with disjoint total dominating sets, Ars Math. Contemp. 16 (2019), no. 2, 359–375.
• [19] M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008), 159–162.
• [20] M.A. Henning, J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009), no. 1, 119–129.
• [21] M.A. Henning, A. Yeo, Graphs with disjoint total dominating sets, [in:] Total Domination in Graphs, Springer Monographs in Mathematics, 2013, 119–124.
• [22] M.A. Henning, A. Yeo, Total domination in graphs. Series: Springer Monographs in Mathematics, Springer, Cham, New York, 2013.
• [23] O. Ore, Theory of Graphs, vol. 38, American Mathematical Society, Providence, RI, 1962.
• [24] J. Southey, Domination Results: Vertex Partitions and Edge Weight Functions, PhD Thesis, Univ. Johannesburg, May 2012.
• [25] J. Southey, M.A. Henning, Dominating and total dominating partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011), no. 3, 699–708.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)