Loading...
Please wait, while we are loading the content...
Similar Documents
Minimum degree and dominating paths (2014).
| Content Provider | CiteSeerX |
|---|---|
| Author | Faudree, Ralph J. Gould, Ronald J. Jacobson, Michael S. West, Douglas B. |
| Abstract | A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. Let G be an n-vertex connected graph. If δ(G)≥n/3−1, then G contains a dominating path, and this is sharp (for 2-connected graphs, δ(G)≥(n+1)/4 suffices). For n/3−1≤δ(G)≤n−1, the lengths of dominating paths include all values from the shortest up to at least min{n−1,2δ(G)}, and this is sharp. For δ(G)>an, 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). For constant s and c ′ <1, an s-vertex dominating path is guaranteed by δ(G)≥n−1−c ′ n 1−1/s when n is sufficiently large, but δ(G)≥n−c(slnn) 1/s n 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. |
| File Format | |
| Publisher Date | 2014-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dominating Path Minimum Degree Minimum Degree Condition N-vertex Connected Graph Minimum Length 2-connected Graph Dominating Set Leaf Neighbor S-vertex Dominating Path |
| Content Type | Text |
