Downhill Domination in Graphs

• Autorzy: Teresa W. Haynes , Stephen T. Hedetniemi , Jessie D. Jamieson , William B. Jamieson
• 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

EN

downhill path; downhill domination number

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 603-612

Daty

wydano

2014-08-01

otrzymano

2013-04-08

poprawiono

2013-09-09

zaakceptowano

2013-09-09

online

2014-07-16

Twórcy

autor

Teresa W. Haynes

• Department of Mathematics and Statistics East Tennessee State University Johnson City, TN 37614, USA

autor

Stephen T. Hedetniemi

• School of Computing Clemson University Clemson, SC 29634, USA

autor

Jessie D. Jamieson

• Department of Mathematics University of Nebraska-Lincoln Lincoln, NE 68588, USA

autor

William B. Jamieson

• Department of Mathematics University of Nebraska-Lincoln Lincoln, NE 68588, USA

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).

Identyfikatory

DOI

10.7151/dmgt.1760