Premium
Minimum Degree and Dominating Paths
Author(s) -
Faudree Ralph J.,
Gould Ronald J.,
Jacobson Michael S.,
West Douglas B.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22021
Subject(s) - mathematics , combinatorics , vertex (graph theory) , dominating set , logarithm , graph , degree (music) , constant (computer programming) , path (computing) , shortest path tree , discrete mathematics , physics , mathematical analysis , computer science , acoustics , programming language
A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P . A result of Broersma from 1988 implies that if G is an n ‐vertex k ‐connected graph and δ ( G ) > n − k k + 2 − 1 , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least min { n − 1 , 2 δ ( G ) } . For δ ( G ) > a n , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a ). The preceding results are sharp. For constant s andc ′ < 1 , an s ‐vertex dominating path is guaranteed by δ ( G ) ≥ n − 1 − c ′ n 1 − 1 / swhen n is sufficiently large, but δ ( G ) ≥ n − c ( s ln n ) 1 / sn 1 − 1 / s(where c > 1 ) does not even guarantee a dominating set of size s . We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.