Locally pancyclic graphs (Q1305522): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/jctb.1998.1885 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2086376513 / rank
 
Normal rank

Revision as of 01:20, 20 March 2024

scientific article
Language Label Description Also known as
English
Locally pancyclic graphs
scientific article

    Statements

    Locally pancyclic graphs (English)
    0 references
    0 references
    11 January 2000
    0 references
    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}\).
    0 references
    pancyclic
    0 references
    hamiltonian
    0 references
    degree
    0 references

    Identifiers