The circumference of the square of a connected graph

S. Brandt, J. Muttel, D. Rautenbach

Research output: Contribution to journalJournal articleResearchpeer-review

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 every n a parts per thousand yen 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c a parts per thousand yen 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.
Original languageEnglish
JournalCombinatorica
Volume34
Issue number5
Pages (from-to)547-559
ISSN0209-9683
DOIs
Publication statusPublished - 2014

Cite this

Brandt, S. ; Muttel, J. ; Rautenbach, D. / The circumference of the square of a connected graph. In: Combinatorica. 2014 ; Vol. 34, No. 5. pp. 547-559.
@article{2550b26219df4a108c27d5a24080cd15,
title = "The circumference of the square of a connected graph",
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 every n a parts per thousand yen 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c a parts per thousand yen 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.",
author = "S. Brandt and J. Muttel and D. Rautenbach",
note = "ISI Document Delivery No.: AT7SD Times Cited: 0 Cited Reference Count: 5 Brandt, Stephan Muettel, Janina Rautenbach, Dieter DFG [RA873/5-1] We were supported by the DFG project {"}Cycle Spectra of Graphs{"} RA873/5-1. 0 SPRINGER HEIDELBERG HEIDELBERG COMBINATORICA",
year = "2014",
doi = "10.1007/s00493-014-2899-4",
language = "English",
volume = "34",
pages = "547--559",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Heinemann",
number = "5",

}

Brandt, S, Muttel, J & Rautenbach, D 2014, 'The circumference of the square of a connected graph', Combinatorica, vol. 34, no. 5, pp. 547-559. https://doi.org/10.1007/s00493-014-2899-4

The circumference of the square of a connected graph. / Brandt, S.; Muttel, J.; Rautenbach, D.

In: Combinatorica, Vol. 34, No. 5, 2014, p. 547-559.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - The circumference of the square of a connected graph

AU - Brandt, S.

AU - Muttel, J.

AU - Rautenbach, D.

N1 - ISI Document Delivery No.: AT7SD Times Cited: 0 Cited Reference Count: 5 Brandt, Stephan Muettel, Janina Rautenbach, Dieter DFG [RA873/5-1] We were supported by the DFG project "Cycle Spectra of Graphs" RA873/5-1. 0 SPRINGER HEIDELBERG HEIDELBERG COMBINATORICA

PY - 2014

Y1 - 2014

N2 - 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 every n a parts per thousand yen 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c a parts per thousand yen 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.

AB - 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 every n a parts per thousand yen 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c a parts per thousand yen 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.

U2 - 10.1007/s00493-014-2899-4

DO - 10.1007/s00493-014-2899-4

M3 - Journal article

VL - 34

SP - 547

EP - 559

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 5

ER -