Let G be a simple undirected graph.

I found some examples of connected graphs G with line graphs containing no hamilton cycle, but none of them was $2$-connected.

  • Are there $2$-connected graphs with a line graph containing no hamilton-cycle ?
  • If yes, what is the smallest ? (Due to my search, it should have more than $7$ vertices)
  • $\begingroup$ Since line graphs tend to have a hamilton-cycle, I wonder if there is a classification of graphs with a line graph without a hamilton cycle. $\endgroup$ – Peter Oct 2 '14 at 10:01
  • $\begingroup$ Have you checked this paper sciencedirect.com/science/article/pii/S0893965912001036 dealing with a conjecture of Thomassen, stating that every $4$-connected line graph is hamiltonian? Its not really what you're asking for but it may offer some insight. $\endgroup$ – Jernej Oct 2 '14 at 10:09
  • $\begingroup$ I did not read the paper, but I noticed the conjecture. $\endgroup$ – Peter Oct 2 '14 at 10:11
  • $\begingroup$ Is the line graph of a $2$-connected graph always $2$-connected ? $\endgroup$ – Peter Oct 2 '14 at 10:13
  • $\begingroup$ Hm.. what is surely true is that if $G$ is $2$-edge connected then $L(G)$ is $2$-connected. This may give a clue for counterexamples. $\endgroup$ – Jernej Oct 2 '14 at 10:19

Here is a counterexample on (incidentally) 8 vertices. I guess this can be generalized.enter image description here

The idea is to only look for $2$-connected non-hamiltonian graphs since the line graph of a hamiltonian graph is always hamiltonian.

A natural question now is whether one can find a different kind of such graphs (not Theta graphs)

  • $\begingroup$ The line graph of this graph is from the type I am particular interested and for which I know no name. I call them "strange graphs". Every vertex is start vertex for some hamiltonian path, but the graph contains no hamilton cycle. The line graphs might help to classify those graphs. $\endgroup$ – Peter Oct 2 '14 at 10:21
  • $\begingroup$ Did you check that it is the least example ? $\endgroup$ – Peter Oct 2 '14 at 11:14
  • $\begingroup$ @Peter Yes it is the least example. $\endgroup$ – Jernej Oct 2 '14 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.