1
$\begingroup$

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

enter image description here

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?

$\endgroup$
3
$\begingroup$
  1. 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).

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

  3. 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:

The problem of finding a Hamiltonian cycle or path is in FNP; the analogous decision problem is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two of Karp's $21$ NP-complete problems. They remain NP-complete even for undirected planar graphs of maximum degree three, for directed planar graphs with indegree and outdegree at most two, for bridgeless undirected planar $3$-regular bipartite graphs, for $3$-connected $3$-regular bipartite graphs, subgraphs of the square grid graph, and cubic subgraphs of the square grid graph.

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

ABCDEGFHLIKJPMONSQTRVWUX

or

AGBFCHDEIOKNJPLMTXRVSWQU

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