EXTREMAL GRAPHS FOR DEGREE SUMS AND DOMINATING CYCLES

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 wit...

Full description

Saved in:
Bibliographic Details
Published in:Bulletin of the Australian Mathematical Society 2024-09, p.1-7
Main Authors: CHEN, LU, WU, YUEYU
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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}.$
ISSN:0004-9727
1755-1633
DOI:10.1017/S0004972724000522