9
$\begingroup$

Let $G$ be a simple $2$-connected graph with $m+n$ vertices ($n>m \geq 3$) with degree sequence $(m-1)^m$, $(n-1)^n$; that is, $G$ is degree-equivalent to two disjoint cliques $K_m$, $K_n$ of different order.

Question: Does $G$ contain a Hamiltonian cycle or a Hamiltonian path?

The few related theorems that I know do not imply existence of such a cycle or path.

Any relevant answer/comment would be greatly appreciated.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It looks like $G$ is disconnected. Any graph with a Hamiltonian path is trivially connected. $\endgroup$
    – Dominic van der Zypen
    Aug 2, 2022 at 8:13
  • 2
    $\begingroup$ By condition the graph $G$ is 2-connected. Here is a minimal example of such a graph: Let's take a cycle on seven vertices $0-1-2-3-4-5-6-0$ and add two edges $0-2$ and $1-3$. We will obtain a graph with degree sequence $3,3,3,3,2,2,2$. $\endgroup$
    – kabenyuk
    Aug 2, 2022 at 9:16

2 Answers 2

Reset to default
21
$\begingroup$

Here is a 9-vertex graph with degree sequence 4 4 4 4 4 3 3 3 3 that does not have a Hamilton cycle (because it is bipartite on an odd number of vertices).

enter image description here

Edit: Here is one line of SageMath showing that this is the only example of this size.

[g.graph6_string() for g in graphs.nauty_geng("-C 9 16 -d3 -D4") if not g.is_hamiltonian()]

Edit 2: Turns out this graph is more structured than the picture shows and it easily leads to an infinite family.

For some $m \geqslant 3$, take the graph $K_{m,m}$ and delete a matching. This leaves $2m$ vertices, each of degree $m-1$. Now add another vertex adjacent to the $m$ vertices of one colour class. This upgrades these $m$ vertices to degree $m$, and the new vertex also has degree $m$. So now we have $m$ vertices of degree $m-1$ and $m+1$ vertices of degree $m$, as required. The graph is still bipartite and has an odd number of vertices.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I noticed that an analogous counterexample can be made on 7 vertices. I also noticed that your (Gordon’s) graph (as well as the one on 7 vertices) has a Hamilton path. So, the question about existence of Hamilton path remains open. I also noticed that such a simple graph (not required to be 2-connected) is: always connected; may have no more than one cut-vertex or one bridge and in either case it has a Hamilton path; If m=n, then the graph is Hamiltonian and its complement is pancyclic. The above makes me think that all such graphs have Hamilton paths. $\endgroup$
    – Valentin Brimkov
    Aug 3, 2022 at 14:17
2
$\begingroup$

Building from Gordon's answer, we can add one more vertex to his graph and join it to all five vertices of degree 4, as shown in the figure below, vertex 10 is the one added.

degree 3 and 5 non-Hamiltonian graph

This gives us six vertices of degree 5 and still four vertices of degree 3, and the graph still isn't Hamiltonian, for similar reasons. Note that the graph is no longer bipartite though.

We can now add another vertex adjacent to all those of degree 5 and repeat this process as many times as necessary to get non-Hamiltonian graphs with n>m+1, and any chromatic number.

From nauty there is also a second graph with vertices of degree 3 and 5 shown below which is not bipartite either; it is non-Hamiltonian by considering the three vertices of degree 3 on the right which all share the same three neighbours alternate degree 3 and 5 non-Hamiltonian graph

Improve this answer
$\endgroup$

Your Answer

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

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