Minimum Degree and Dominating Paths

<jats:title>Abstract</jats:title><jats:p>A <jats:italic>dominating path</jats:italic> in a graph is a path <jats:italic>P</jats:italic> such that every vertex outside <jats:italic>P</jats:italic> has a neighbor on <jats:italic>P</jats:italic>. A result of Broersma from 1988 implies that if <jats:italic>G</jats:italic> is an <jats:italic>n</jats:italic>‐vertex <jats:italic>k</jats:italic>‐connected graph and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0001.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0001" />, then <jats:italic>G</jats:italic> contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0002.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0002" />. For <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0003.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0003" />, where <jats:italic>a</jats:italic> is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in <jats:italic>n</jats:italic> when <jats:italic>n</jats:italic> is sufficiently large (the base of the logarithm depends on <jats:italic>a</jats:italic>). The preceding results are sharp. For constant <jats:italic>s</jats:italic> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0004.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0004" />, an <jats:italic>s</jats:italic>‐vertex dominating path is guaranteed by <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0005.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0005" /> when <jats:italic>n</jats:italic> is sufficiently large, but <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0006.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0006" /> (where <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22021-math-0007.png" xlink:title="urn:x-wiley:03649024:media:jgt22021:jgt22021-math-0007" />) does not even guarantee a dominating set of size <jats:italic>s</jats:italic>. 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.</jats:p>