The circumference of the square of a connected graph

Research output: Research - peer-reviewJournal article

View graph of relations

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
StatePublished - 2014