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$
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$

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.