scientific article; zbMATH DE number 1802820
A cycle \(C\) of a graph \(G\) is called a \(q\)-dominating cycle if every vertex of \(G\) which is not contained in \(C\) is adjacent to at least \(q\) vertices of \(C\). Thus a \(1\)-dominating cycles is the classical dominating cycle. In [Discrete Math. 67, 205-208 (1987; Zbl 0634.05045)] J. A. Bondy and G. Fan presented the following sufficient condition for the existence of a dominating cycle. Theorem. Let \(G\) be a \(k\)-connected graph on \(n\) vertices, where \(k\geq 2\). If \(\sum^k_{i=0} d(x_i)\geq n- 2k\) for any \(k+1\) independent vertices \(x_0,x_1,\dots, x_k\) with \(N(x_i)\cap N(x_j)= \varnothing\) for \(0\leq i\neq j\leq k\), then \(G\) has a dominating cycle. The author presentes the following extension of the previus theorem. Theorem. Let \(k\) and \(q\) be positive integers and let \(G\) be a \(k\)-connected graph on \(n\) vertices, where \(k\geq 2\). If for any \(k+1\) independent vertices \(x_0,x_1,\dots, x_k\) with \(|N(x_i)\cap N(x_j)|\leq 2q- 2\) for \(0\leq i\neq j\leq k\), \(\sum^k_{i=0} d(x_i)\geq n+(k+ 1)(q- 3)+ 2\), then \(G\) has a \(q\)-dominating cycle.
- A sufficient condition for dominating cycles
- scientific article; zbMATH DE number 4008435
- scientific article; zbMATH DE number 57430
- scientific article; zbMATH DE number 57532
- scientific article; zbMATH DE number 1150387
- Degree sums and dominating cycles
- scientific article; zbMATH DE number 5914869
- A note on a longest cycle which is vertex dominating
- Cycles within specified distance from each vertex.
- scientific article; zbMATH DE number 3895104
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3147265)
