Distance-dominating cycles in quasi claw-free graphs
The paper concerns quasi claw-free graphs. For a vertex \(u\) of a graph \(G\) the symbol \(N(u)\) denotes the open neighbourhood of \(u\) in \(G\), i.e. the set consisting of all vertices which are adjacent to \(u\) in \(G\). The closed neighbourhood of \(u\) is \(N[u]= N(u)\cup \{u\}\). If for any two vertices \(a_1\), \(a_2\) having distance 2 in \(G\) there exists at least one vertex \(u\in N(a_1)\cap N(a_2)\) such that \(N[u]\subseteq N[a_1]\cup N[a_2]\), then \(G\) is called quasi claw-free. The paper studies connectivity and dominance in such graphs. A cycle \(C\) is \(m\)-dominating in \(G\), if for each vertex of \(G\) there exists a vertex of \(C\) having distance at most \(m\) from it. The main result states that if a quasi claw-free graph \(G\) is \(\kappa\)-connected for \(\kappa\geq 2\) and \(m\) is a nonnegative integer, then either \(G\) has an \(m\)-dominating cycle, or \(G\) has a set of at least \(\kappa+ 1\) vertices such that the distance between every pair of them is at least \(2m+3\).
This page was built for publication: Distance-dominating cycles in quasi claw-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808712)
