TY - JOUR
TI - The circumference of the square of a connected graph
LA - eng
AU - Brandt, S.
AU - Muttel, J.
AU - Rautenbach, D.
JF - Combinatorica
VL - 34
IS - 5
SP - 547
EP - 559
PY - 2014
SN - 14396912, 02099683
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.
DO - 10.1007/s00493-014-2899-4
ER -