PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2001 | 21 | 2 | 239-253
Tytuł artykułu

### Domination Subdivision Numbers

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
239-253
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-12-21
Twórcy
autor
• Department of Mathematics, East Tennessee State University, Johnson City, TN 37614 USA
autor
• Department of Computer Science, Clemson University, Clemson, SC 29634 USA
• Department of Computer Science, Clemson University, Clemson, SC 29634 USA
autor
• Department of Computer Science, Clemson University, Clemson, SC 29634 USA
autor
• Department of Mathematics, Bob Jones University, Greenville, SC 29614 USA
• Division of Mathematics and Science, Northeast State Technical Community College, Blountville, TN 37617 USA
Bibliografia
• [1] Arumugam, private communication, June 2000.
• [2] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079.
• [3] D. Hare and W. McCuaig, A characterization of graphs whose domination and matching numbers are equal, unpublished manuscript, 1998.
• [4] T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000) 271-280, doi: 10.7151/dmgt.1126.
• [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
• [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs (Advanced Topics, Marcel Dekker, Inc., New York, 1998).
• [7] T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, submitted.
• [8] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.
• [9] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and matching number, Utilitas Math. 55 (1999) 65-72.
Typ dokumentu
Bibliografia
Identyfikatory