Hostname: page-component-7bb8b95d7b-l4ctd Total loading time: 0 Render date: 2024-09-19T16:10:43.273Z Has data issue: false hasContentIssue false
  • English
  • Français

EXTREMAL GRAPHS FOR DEGREE SUMS AND DOMINATING CYCLES

Part of: Graph theory

Published online by Cambridge University Press:  13 September 2024

LU CHEN Open the ORCID record for LU CHEN [Opens in a new window]  and
YUEYU WU Open the ORCID record for YUEYU WU [Opens in a new window]
LU CHEN
Affiliation:
College of Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, PR China e-mail: [email protected]
YUEYU WU*
Affiliation:
College of Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, PR China
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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}.$

Keywords

extremal graphdegree sumslongest cycledominating cycle

MSC classification

Primary: 05C69: Dominating sets, independent sets, cliques
Secondary: 05C07: Vertex degrees 05C38: Paths and cycles
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , First View , pp. 1 - 7
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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.

References

Bondy, J. A., ‘Longest paths and cycles in graphs of high degree’, Research Report CORR 80-16 (University of Waterloo, Waterloo, Ontario, 1980).Google Scholar
Bondy, J. A. and Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics, 244 (Springer, London, 2008).CrossRefGoogle Scholar
Fournier, I. and Fraisse, P., ‘On a conjecture of Bondy’, J. Combin. Theory Ser. B 39 (1985), 17–26.CrossRefGoogle Scholar
Lu, M., Liu, H. and Tian, F., ‘Two sufficient conditions for dominating cycles’, J. Graph Theory 49 (2005), 135–150.CrossRefGoogle Scholar
Wu, Y., Chen, Y. and Cheng, E., ‘Degree sums and dominating cycles’, Discrete Math. 344 (2021), Article no. 112224.CrossRefGoogle Scholar
Zhang, C., ‘Hamilton cycles in claw-free graph’s’, J. Graph Theory 12 (1988), 209–216.CrossRefGoogle Scholar