0
$\begingroup$

I have a given planar chordal graph $G$. Due to the construction of $G$ I know that there exists at least one Hamiltonian cycle in $G$. My question is:

  1. How many Hamiltonian cycles are in $G$? (an upper bound would be nice)

  2. Can they all be found, i.e., is there a known algorithm.

I found a work on the number of such cycles in planar graphs of certain classes, there the number is exponential (paper).

  1. Is it somehow obvious that the number of hamiltonian cycles in $G$ is exponential as well?
$\endgroup$
0
$\begingroup$

I did the algorithm/pseudocode of the Eulerians ... you would only have to readapt for the necessary/sufficient conditions of the Hamiltonians (if you do not understand something you will tell me):

Develop a program with MAXIMA that determines if your graph is Eulerian. Try it with some of the preconstructed graphs in MAXIMA. (Indication: include in the writing the entries sent to MAXIMA and its response)

-The code presented below serves to know if a graph (not a digraph) is Eulerian. In the "sieve" process of successive iterations of the program we can know if it is not Eulerian (value: true) if: it is not a graph / is directed, if it is a graph is or is not connected, Or if in spite of fulfilling the two previous requirements it does not fulfill that all the degrees of its vertices are pairs (and therefore the value: false in the definition "the_graph_is_eulerian").

INPUTS (% iX)$\hspace{40mm}$ /*COMMENTS */

Being "i" the initial of the English word "input" and $X$ an element of the set of natural numbers $\{1,2,3, ...\}$

%i1) load(graphs) \$

$\hspace{8mm}$the_graph_is_eulerian (G) $:=$ block ([Value: true],

$\hspace{27mm}$ if not is_graph (G) then return ("It is a digraph and/or is not a graph"),

$\hspace{27mm}$ if not is_connected (G) then return ("It is not a connected graph"),

$\hspace{27mm}$ for d in degree_sequence (G) do

$\hspace{37mm}$ if remainder $(d, 2)=1$ then return (Value: false),

$\hspace{27mm}$ Value)\$

the graphs package is loaded to work with the graphs */

a block with a real variable is defined */

the is_graph (G) function returns true if G is a graph. So if is_graph (G) = false or equivalently not is graph (G) = true, then the text in parentheses and quoted appears in the screen*/

the reasoning of the previous line but with the function is_connected (G), which determines if it is connected */

scrolls the list of degrees of the vertices of G */

if some degree of that list of G is not even (by dividing it between 2 da of rest 1) then false */

You can send the image of the hamiltoniano graph in question and we do it ... by hand can be made by process, following the algorithm, by "brute force" ... or directly in the MAXIMA software introducing its nodes and asking him something like "is_hamiltonian_cycle (Graph_x) "... and it says :D; There is a reserved function for this.

In the Eulerian it is not predetermined, but with this code that I just sent you ... as if it were!

As for the chordal graph ... what do you mean, it is obvious that the number of cycles is exponential?

Software: http://maxima.sourceforge.net/download.html

Graph Package Info: http://maxima.sourceforge.net/docs/manual/es/maxima_55.html

$\endgroup$
  • $\begingroup$ For a problem I am working on I would like to know how many hamiltonian cycles can there be for such a graph $G$, as in an upper bound. I would think that it could be exponentially many cycles but I did not find a reference. $\endgroup$ – gue Apr 6 '17 at 8:15
  • $\begingroup$ Thanks for the offer of solving a graph for me, but I actually do not have one specific graph but rather the concept. I am also not certain if the proposed eulerian approach can be modified to find hamiltonian cycles (efficiently). $\endgroup$ – gue Apr 6 '17 at 8:16
0
$\begingroup$

Here's a way to get some exponential upper bound. We will not use the chordal assumption, just the planarity. In fact, we'll prove the following: if a graph $G$ is $d$-degenerate, then $G$ contains at most $(1+d+{d\choose 2})^n$ Hamilton cycles.

Recall that a graph $G$ is $d$-degenerate if there is an ordering $v_1,\dots,v_n$ wherein each $v_i$ has at most $d$ neighbors to the left. If $H$ is a hamilton cycle in $G$, then every vertex is incident to $2$ edges in $H$. We will say that an edge is owned by $v_i$ if $v_i$ is the large of its vertices, e.g. if we have the edge $e=v_3v_{12}$ then $v_{12}$ owns $e$. Thus, in a hamilton cycle $H$, each vertex owns at most $2$ edges of $H$. Therefore, the number of hamilton cycles is upper bounded by the number of ways to select at most $2$ edges for each vertex to own. For a given vertex, there are at most $1+d+{d\choose 2}$ ways to do this, so we have at most $(1+d+{d\choose 2})^n$ hamilton cycles.

Since all planar graphs are $\leq 5$-degenerate, we see that a planar graph on $n$ vertices has at most $16^n$ hamilton cycles. This is a really awful bound, but it shows that your intuition that you can't have more than exponentially many hamilton cycles is correct.

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