1
$\begingroup$

I'm trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence. For disconnected graphs it would be easier, I could choose a degree sequence of $(2,2,2,2,2,2)$ and have $C_6$, which has a Hamiltonian path, and two disjoint 3-cycles, which are non-Hamiltonian.

How to do it with two connected graphs?

$\endgroup$

2 Answers 2

5
$\begingroup$

The degree sequence $\langle 3,3,2,2,2,2\rangle$ will work:

           *——*——*                *      *  
           |  |  |                |\    /|  
           *——*——*                | *——* |  
                                  |/    \|  
                                  *      *
$\endgroup$
1
$\begingroup$

The idea is that one of them has a central vertex or edge such that removing it leaves the graph not connected.

When I solved the exercise I found a bigger example than $(2,2,3,3,3,3)$, where the two graphs have score $(2,2,3,3,3,3,4)$: one is $C_6$ with a central vertex of degree 4, the other is a double $K_3$, with the extra vertex of degree 4 connected to 2 vertices of the first $K_3$ and to 2 vertices of the other one.

$\endgroup$

You must log in to answer this question.

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