PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 3 | 603-612
Tytuł artykułu

Downhill Domination in Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A path π = (v1, v2, . . . , vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds
Słowa kluczowe
Wydawca
Rocznik
Tom
34
Numer
3
Strony
603-612
Opis fizyczny
Daty
wydano
2014-08-01
otrzymano
2013-04-08
poprawiono
2013-09-09
zaakceptowano
2013-09-09
online
2014-07-16
Twórcy
  • Department of Mathematics and Statistics East Tennessee State University Johnson City, TN 37614, USA, haynes@etsu.edu
Bibliografia
  • [1] T.W. Haynes, S.T. Hedetniemi, J. Jamieson and W. Jamieson, Downhill and uphill domination in graphs, submitted for publication (2013).
  • [2] P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30.
  • [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998).
  • [4] J.D. Hedetniemi, S.M. Hedetniemi, S.T. Hedetniemi and T. Lewis, Analyzing graphs by degrees, AKCE Int. J. Graphs Comb., to appear.
  • [5] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1760
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ć.