PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 2 | 335-347
Tytuł artykułu

Effect of edge-subdivision on vertex-domination in a graph

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with Δ(G) > 1, ξ(G) ≤ 3. We show that the conjecture is false and construct for any positive integer n ≥ 3, a graph G of order n with ξ(G) > [1/3]log₂ n. The main results of this paper are the following: (i) For any connected graph G with at least three vertices, ξ(G) ≤ γ(G)+1 where γ(G) is the domination number of G. (ii) If G is a connected graph of sufficiently large order n, then ξ(G) ≤ 4√n ln n+5
Słowa kluczowe
Wydawca
Rocznik
Tom
22
Numer
2
Strony
335-347
Opis fizyczny
Daty
wydano
2002
Twórcy
  • School of Mathematics, Tata Institute of Fundamental Research, Homi Bhabha Road, Colaba, Mumbai 400 005, India
  • School of Mathematics, Tata Institute of Fundamental Research, Homi Bhabha Road, Colaba, Mumbai 400 005, India
Bibliografia
  • [1] N. Alon and J. H. Spencer, The Probabilistic Method, Second Edition, John Wiley and Sons Inc. (Tel Aviv and New York, 2000).
  • [2] R. Diestel, Graph Theory, Second Edition (Springer-Verlag, New York, 2000).
  • [3] 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.
  • [4] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely and L.C. van der Merwe, Domination Subdivision Numbers, preprint.
  • [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Dekker, New York, 1998).
  • [6] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1179
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.