Circumference of a graph and its distance dominating longest cycles (Q2214043)

A cycle \(C\) of a graph \(G\) is \(m\)-dominating if each vertex of \(G\) is at distance at most \(m\) from \(C\). Similarly, \(C\) is \(m\)-edge-dominating if each edge of \(G\) is at distance at most \(m\) from \(C\). The first main theorem asserts that if \(G\) is a graph with connectivity \(k\ge 2\) and the circumference of \(G\) is at most \((2m+2)k-1\) for some non-negative integer \(m\), then every longest cycle of \(G\) is \(m\)-dominating. The second main theorem asserts that if \(G\) is a graph with connectivity \(k\ge 2\) and the circumference of \(G\) is at most \((2m+3)k-1\), then every longest cycle of \(G\) is \(m\)-edge-dominating. It is demonstrated that the bounds from the theorems are sharp. It is also shown that the connectivity assumption in the theorems cannot be replaced by the minimum degree.