Pancyclic graphs and degree sum and neighborhood union involving distance two

Kewen Zhao, Yu Jong Tzeng, Ping Zhang

Research output: Contribution to journalArticle

Abstract

For a graph G, δ denotes the minimum degree of G. In 1971, Bondy proved that, if G is a 2-connected graph of order n and d(x)+d(y)<n for each pair of non-adjacent vertices x, y in G, then G is pancyclic or G=Kn 2,n2. In 2006, Wu et al. proved that, if G is a 2-connected graph of order n<6 and |N(x)∪N(y)|+δ<n for each pair of non-adjacent vertices x, y of d(x,y)=2 in G, then G is pancyclic or G=Kn2,n2. In this paper, we introduce a new condition which generalizes two conditions of degree sum and neighborhood union and prove that, if G is a 2-connected graph of order n<6 and |N(x)∪N(y)|+d(w)<n for any three vertices x, y, w of d(x,y)=2 and wx or wy∉E(G) in G, then G is pancyclic or G=Kn 2,n2. This result also generalizes the above two results.

Original languageEnglish (US)
Pages (from-to)218-223
Number of pages6
JournalDiscrete Applied Mathematics
Volume160
Issue number3
DOIs
StatePublished - Feb 1 2012

Keywords

  • Degree sum
  • Neighborhood union
  • Pancyclic graphs

Fingerprint Dive into the research topics of 'Pancyclic graphs and degree sum and neighborhood union involving distance two'. Together they form a unique fingerprint.

Cite this