Degree sums and dominating cycles

Yueyu Wu, Yaojun Chen, T. C.Edwin Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

A cycle C of a graph G is dominating if any vertex of V(G)∖V(C) has at least one neighbor on C and V(G)∖V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this paper, we show that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)∕3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy (1980) for k=2 and Lu et al. (2005) for k=3.

Original languageEnglish
Article number112224
JournalDiscrete Mathematics
Volume344
Issue number3
DOIs
Publication statusPublished - Mar 2021

Keywords

  • Degree sums
  • Dominating cycle
  • Longest cycle

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this