Pancyclic graphs and degree sum and neighborhood union involving distance two. (English) Zbl 1241.05059

Zhao, Kewen; Tzeng, Yu-Jong; Zhang, Ping

Discrete Appl. Math. 160, No. 3, 218-223 (2012); retraction ibid. 160, No. 16-17, 2497 (2012).

Summary: For a graph \(G\), \(\delta\) denotes the minimum degree of \(G\). In [J. Comb. Theory, Ser. B 11, 80–84 (1971; Zbl 0183.52301)], J. A. Bondy proved that, if \(G\) is a 2-connected graph of order \(n\) and \(d(x)+ d(y)\geq n\) for each pair of non-adjacent vertices \(x\), \(y\) in \(G\), then \(G\) is pancyclic or \(G= K_{n/2,n/2}\). In [J. Nanjing Norm. Univ., Nat. Sci. Ed. 29, No. 2, 31–34 (2006; Zbl 1110.05055)], W. Wu, Z. Qi, X. Yuan and Z. Sun proved that, if \(G\) is a 2-connected graph of order \(n\geq 6\) and \(|N(x)\cup N(y)|+ \delta\geq n\) for each pair of non-adjacent vertices \(x\), \(y\) of \(d(x,y)= 2\) in \(G\), then \(G\) is pancyclic or \(G= K_{n/2,n/2}\).
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\geq 6\) and \(|N(x)\cup N(y)|+ d(w)\geq n\) for any three vertices \(x\), \(y\), \(w\) of \(d(x,y)= 2\) and \(w x\) or \(wy\not\in E(G)\) in \(G\), then \(G\) is pancyclic or \(G= K_{n/2,n/2}\). This result also generalizes the above two results.
Editorial remark: According to the retraction notice, “the original submission was made without the approval of the two previously listed co-authors Ping Zhang and Yu-Jong Tzeng, who neither contributed to the research nor agreed with corresponding author Kewen Zhao to have a paper submitted in their names. This represents a clear violation of our policies on authorship.”

MSC:

05C38	Paths and cycles
05C05	Trees
05C12	Distance in graphs

Keywords:

pancyclic graphs; degree sum; neighborhood union

Citations:

Zbl 0183.52301; Zbl 1110.05055