Abstract
The celebrated result of Fleischner states that the square of every 2-connected graph is Hamiltonian. We investigate what happens if the graph is just connected. For everyn ≥ 3, we determine the smallest lengthc(n) of a longest cycle in the square of a connected graph of order n and show thatc(n) is a logarithmic function inn. Furthermore, for everyc ≥ 3, we characterize the connected graphs of largest order whose square contains no cycle of length at leastc.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
R. Diestel:Graph Theory, Springer, 2010.
H. Fleischner: The square of every two-connected graph is Hamiltonian,J. Comb. Theory, Ser. B16 (1974), 29–34.
H. Fleischner: In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts,Monatsh. Math.82 (1976), 125–149.
M. Ch. Golumbic:Algorithmic graph theory and perfect graphs, Elsevier, Amsterdam, 2004.
F. Harary and A. Schwenk: Trees with Hamiltonian square,Mathematika, Lond.18 (1971), 138–140.
Author information
Authors and Affiliations
Department of Mathematics and Computer Science (IMADA), University of Southern Denmark, Odense, Denmark
Stephan Brandt
Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany
Janina Müttel & Dieter Rautenbach
- Stephan Brandt
You can also search for this author inPubMed Google Scholar
- Janina Müttel
You can also search for this author inPubMed Google Scholar
- Dieter Rautenbach
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toStephan Brandt.
Rights and permissions
About this article
Cite this article
Brandt, S., Müttel, J. & Rautenbach, D. The circumference of the square of a connected graph.Combinatorica34, 547–559 (2014). https://doi.org/10.1007/s00493-014-2899-4
Received:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative