3
$\begingroup$

Let $G$ be a simple graph which is a cycle $C$ equipped with some chords such that $\delta (G)\geq 3$. In other words, every vertex of $C$ is adjacent with at least one of the chords.

I conjecture that there must exist at least one Hamiltonian cycle in $G$ besides $C$. Can you prove it or give a counterexample?

$\endgroup$
1

1 Answer 1

7
$\begingroup$

I think Gordon Royle and Joseph O'Rourke answer it here

A graph is uniquely hamiltonian if it has exactly one Hamilton cycle

Apparently, however, there are uniquely hamiltonian graphs with minimum degree equal to four - the latest edition of Bondy & Murty's Graph Theory even gives a reference to a paper by H. Fleischner entitled "Uniquely hamiltonian graphs of minimum degree 4", To Appear, Journal of Graph Theory and dates it at 2007.

Since the graph have a hamiltonian cycle you can consider it a cycle $C$ and all the edges not in $C$ are chords.

Searching the web for "uniquely hamiltonian graph" returns references.

Added

Explicit counterexample from this paper p. 13

$\endgroup$
5
  • $\begingroup$ onlinelibrary.wiley.com/doi/10.1002/jgt.21729/abstract Abstract We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree. $\endgroup$
    – joro
    Nov 4, 2013 at 15:29
  • 1
    $\begingroup$ Fleischner's paper has been available online since 31 Jan 2013 at the J. Graph Theory website to those with a paid subscription. I expect it should be officially published pretty soon. Note that in his concluding section, Fleischner conjectures that there do not exist any 4-connected uniquely Hamiltonian graphs. $\endgroup$ Nov 4, 2013 at 18:27
  • $\begingroup$ joro,Thank you very much!Your answer is very helpful!!! $\endgroup$
    – user40096
    Nov 7, 2013 at 14:17
  • $\begingroup$ @user40096 You are welcome. $\endgroup$
    – joro
    Nov 7, 2013 at 14:18
  • $\begingroup$ Dear joro,as what I said in the question above,Let G be a simple graph which is a cycle $C$ equipped with some chords such that $\delta (G)\geq 3$,in other words,every vertex of $C$ is adjacent with at least one of the chords.If I let the length of every edge of the cycle $C$ is $1$ and the length of every chord of $C$ is $2$(subdivide each chord with a vertex),can I get a cycle in $G$ which is longer than $C$? $\endgroup$
    – user40096
    Nov 10, 2013 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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