No CrossRef data available.
Article contents
EXTREMAL GRAPHS FOR DEGREE SUMS AND DOMINATING CYCLES
Published online by Cambridge University Press: 13 September 2024
Abstract
A cycle C of a graph G is dominating if $V(C)$ is a dominating set and $V(G)\backslash V(C)$ is an independent set. Wu et al. [‘Degree sums and dominating cycles’, Discrete Mathematics 344 (2021), Article no. 112224] proved that every longest cycle of a k-connected graph G on $n\geq 3$ vertices with $k\geq 2$ is dominating if the degree sum is more than $(k+1)(n+1)/3$ for any $k+1$ pairwise nonadjacent vertices. They also showed that this bound is sharp. In this paper, we show that the extremal graphs G for this condition satisfy $(n-2)/3K_1\vee (n+1)/3K_2 \subseteq G \subseteq K_{(n-2)/3}\vee (n+1)/3K_2$ or $2K_1\vee 3K_{(n-2)/3}\subseteq G \subseteq K_2\vee 3K_{(n-2)/3}.$
MSC classification
- Type
- Research Article
- Information
- Copyright
- © The Author(s), 2024. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.
Footnotes
This research was supported by NSFC under grant number 12101324, by NJUPT under grant number NY221025 and by Foundation of Jiangsu Provincial Double-Innovation Doctor Program under grant number JSSCBS20210533.