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:
How many Hamiltonian cycles are in $G$? (an upper bound would be nice)
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).
- Is it somehow obvious that the number of hamiltonian cycles in $G$ is exponential as well?
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