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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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

Improve this answer
$\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
    Commented 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$
    – Timothy Chow
    Commented Nov 4, 2013 at 18:27
  • $\begingroup$ joro,Thank you very much!Your answer is very helpful!!! $\endgroup$
    – user40096
    Commented Nov 7, 2013 at 14:17
  • $\begingroup$ @user40096 You are welcome. $\endgroup$
    – joro
    Commented 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
    Commented Nov 10, 2013 at 7:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .