Research output: Contribution to journal › Journal article

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.

Language | English |
---|---|

Journal | Combinatorica |

Volume | 34 |

Issue number | 5 |

Pages (from-to) | 547-559 |

ISSN | 0209-9683 |

DOIs | |

State | Published - 2014 |