×

Degree sum and vertex dominating paths. (English) Zbl 1407.05176

Let \(\sigma_2(G)\) denote the minimum degree-sum of a graph \(G\), that is, the minimum value of \(d(u) + d(v)\) over all nonadjacent pairs \(u,v\). The authors prove that if \(G\) is an \(n\)-vertex, \(k\)-connected graph with \(\sigma_2(G) \geq 2n/(k+2) + f(k)\), where \(f(k)\) is a constant depending only on \(k\), then for any set of vertices \(T\) with \(|T| \leq n/(900k^4)\), the graph \(G\) has a path through \(T\) containing at most \((20k)|T|\) vertices.
As a corollary of this result, the authors prove that every graph satisfying this hypothesis has a dominating path \(P\) on at most \((20k)\gamma(G)\) vertices. Here, a dominating set for \(G\) is a set of vertices \(X\) such that every vertex of \(G\) either lies in \(X\) or has a neighbor in \(X\); a dominating path is a path whose vertices form a dominating set; and \(\gamma(G)\) is the domination number of \(G\), that is, the smallest size of a dominating set in \(G\). The corollary follows from the main result via a lemma proving that every graph \(G\) with \(\sigma_2(G) \geq 2\beta n\) for \(\beta \in (0,1)\) has a dominating set \(X\) with \(|X| \leq \left\lceil \log_{1/(1-\beta)} n\right\rceil\); taking \(T=X\) in the path theorem (as can be done for sufficiently large \(n\)) yields a dominating path.
To prove the sharpness of the domination result, the authors construct an \(n\)-vertex \(k\)-connected graph with \(\sigma_2(G) = \frac{2n - 4(k+1)}{k+2}\) yet the graph has no dominating path. The authors conjecture that this example is extremal: that every graph \(k\)-connected \(n\)-vertex graph \(G\) with \(\sigma_2(G) > \frac{2n-4(k+1)}{k+2}\) has a dominating path on at most \(O(\ln n)\) vertices.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C38 Paths and cycles
05C07 Vertex degrees
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI