Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
cannonical link button


Opuscula Mathematica

Tytuł artykułu

A note on the p-domination number of trees

Autorzy Lu, Y.  Hou, X.  Xu, J.-M. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
EN Let p be a positive integer and G = (V (G), E(G)) a graph. A p-dominating set of G is a subset S of V (G) such that every vertex not in S is dominated by at least p vertices in S. The p-domination number ϒp(G) is the minimum cardinality among the p-dominating sets of G. Let T be a tree with order n ≥ 2 and p ≥ 2 a positive integer. A vertex of V (T) is a p-leaf if it has degree at most p - 1, while a p-support vertex is a vertex of degree at least p adjacent to a p-leaf. In this note, we show that ϒp(T) ≥ (n + /Lp(T)/ - /Sp(T)/)/2, where Lp(T) and Sp(T) are the sets of p-leaves and p-support vertices of T, respectively. Moreover, we characterize all trees attaining this lower bound.
Słowa kluczowe
EN p-domination number   trees  
Wydawca AGH University of Science and Technology Press
Czasopismo Opuscula Mathematica
Rocznik 2009
Tom Vol. 29, no. 2
Strony 157--164
Opis fizyczny Bibliogr. 8 poz.
autor Lu, Y.
autor Hou, X.
autor Xu, J.-M.
  • University of Science and Technology of China Department of Mathematics Hefei, Anhui, 230026, China,
[1] M. Blidia, M. Chellali, L. Volkmann, Some bounds on the p-domination number in trees, Discrete Math. 306 (2006), 2031–2037.
[2] G. Chartrant, L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman & Hall, London, 1996.
[3] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math. 26 (2006), 5–11.
[4] J.F. Fink, M.S. Jacobson, n-Domination in graphs, [in:] Y.Alavi, A.J.Schwenk (Eds.), Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York, 1985, 283–300.
[5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in graphs, New York, Marcel Deliker, 1998.
[6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, New York, Marcel Deliker, 1998.
[7] M. Lemanska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24(2) (2004), 165–169.
[8] L.Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput. 61 (2007), 159–167.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-AGHT-0001-0008