The set of degree sequences in question is:
$$ D_1=\{4^4,6^4,4^4\} $$
$$ D_2=\{4^4,6^4,6^4,4^4\} $$
$$ D_3=\{4^4,6^4,6^4,6^4,4^4\} $$
$$ D_4=\{4^4,6^4,6^4,6^4,6^4,4^4\} $$
$$ … $$
$$ D_N=\{4^4,6^4,…,4^4\} $$
Where the superscripts are the number of vertices and the base is the degree of those vertices. In $D_N,$ there are $N,$ $6's.$
Here is $D_4:$
As you can see this graph is self-similar. You essentially start with the outer shell of four vertices and four edges and then build inwards towards the center.
Questions:
$1.$ I am wondering how many different graphs have these degree sequences. I've found one graph for each $D_N.$
$2.$ Is the set of $D_N$ an example of a class of graphs?
$3.$ As you go from $D_1$ to $D_2$ to $D_3$ and so on, how does the computational complexity increase for finding a hamiltonian path?
Best Answer
For any natural $n$, $D_n$ is degree sequence with $8$ vertices of degree $4$ and $6n$ vertices of degree $6$. I expect there is a lot of graphs with this degree sequence. For instance, it matches a union of a complete bipartite graph $K_{4,4}$ and any $6$-regular graph with $6n$ vertices (for instance, a union of any six mutually disjoint perfect mathching on $6n$ vertices).
As far as I know, class is a non-rigorous notion of a graph theory, so I think it is OK to call by class the family of graphs whose degree sequence is $D_n$.
I guess that Hamiltonian Path problem is NP-hard for the graph with $D_n$, because it is NP-hard even for families of graphs with much more simple structure than $6$-regular graphs. Namely, according to Wikipedia’s article:
But for the family of the graphs which you have illustrated it looks that a spiral is such a path. Namely, for the drawn graph a Hamiltonian path is
or