Locally pancyclic graphs
type: Item
instance of: scholarly article
title: Locally pancyclic graphs
zbMATH Open document ID: 0929.05047
author: Ladislav Stacho
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-01-11T00:00:00Z
review text: It was shown by \textit{J. A. Bondy} [Stud. Sci. Math. Hung. 4, 473-475 (1969; Zbl 0184.27702)] that if \(G\) is a graph of order \(n\) in which \(d_G(x) + d_G(y) \geq n\) for each pair of nonadjacent vertices \(x\) and \(y\) of \(G\), then \(G\) is either pancyclic or the complete bipartite graph \(K_{n/2,n/2}\). This result is generalized by proving a local version of the Bondy result. Let \(W\) be a set of at least \(3\) vertices of \(G\). It is shown that if \(d_G(x) + d_G(y) \geq n\) for each pair of nonadjacent vertices \(x\) and \(y\) of \(W\), then either for each \(i\) with \(3 \leq i \leq | W| \) there will be a cycle of \(G\) containing precisely \(i\) vertices of \(W\), or \(W = K_{2,2}\), or \(| W| = n\), and \(G = K_{n/2,n/2}\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1346886
zbMATH Keywords: pancyclic
zbMATH Keywords: hamiltonian
zbMATH Keywords: degree
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: jctb.1998.1885
OpenAlex ID: W2086376513
cites work: Hamiltonian degree conditions which imply a graph is pancyclic
cites work: Cycles through specified vertices
cites work: Pancyclic graphs. I
cites work: An Ore-type condition for pancyclability
cites work: Updating the hamiltonian problem—A survey
cites work: Q3944634
cites work: Parallel concepts in graph theory
cites work: On Hamilton's ideals
cites work: Note on Hamilton Circuits
cites work: Pancyclic graphs and a conjecture of Bondy and Chvatal
cites work: A cycle structure theorem for Hamiltonian graphs
cites work: Old Hamiltonian Ideas from a New Point of View
cites work: Pancyclism and bipancyclism of Hamiltonian graphs
DOI: 10.1006/JCTB.1998.1885
description: scientific article; zbMATH DE number 1346886