How many Distinct Hamiltonian Maximal Planar Graphs are there (n vertices) and could this representation help?

Question

If we make a regular polygon with n vertices (n edges) and triangulate on the inside with n-3 edges, then triangulate on the outside with (n-3) edges (or draw dotted lines inside again), a Maximal Planar Graph is formed. Edges shouldn't be repeated and there's no loops or directions.

How many distinct graphs of this type are there?

It's connected to an earlier question where it was asked 'How many Distinct Maximal Planar Graphs are there? How many distinct Maximal Planar Graphs exist with $n$ vertices?

Will Orrick gave the OEIS numbers A000109. It was then wondered if there was a known formula for those numbers or bounds on them. It's conjectured that graphs of the type in this question might constitute most Maximal Planar Graphs, so a formula for the 'polygon' types might be an approximate formula or a lower bound for all types of Maximal Planar Graphs.

Dividing the polygon on the inside can be done in C(n-2) ways, where C(n) are the Catalan numbers A000108, so a connection was looked for - and A000109 seem to be close to C(n-2)*2^(n-13) at least for n=9 to 23.

So, the answer to this question would be of interest and any thoughts on connecting the A000108 and A000109 numbers. Lots of ways have been tried so far, e.g. since the next Catalan number can be formed by adding the product of ones before, e.g. C(4) = C(3)*C(1) + C(2)*C(2) + C(1)*C(3), perhaps something similar happens for A000109, or by incorporating numbers from both sequences. Lots of coincidences (probably) have been found including the 233 number in A000109 say X(10) is C(9-2) - the sum of the Catalan numbers before it.

Think I'm going to go crazy looking for patterns any longer! Any suggestions please!

Answer 1

This is too long to be a comment, but only provides a modest reduction in the $C_{n-2}^2$ upper bound.

For $n\ge3$ let $a_n$ be the number of unordered pairs of triangulations of the $n$-gon with no common diagonals. Let $g(x)=a_3x^3+a_4x^4+a_5x^5+a_6x^6+\ldots$ be the generating function. The first few coefficients are $a_3=\frac{1}{2}$, $a_4=1$, $a_5=5$, $a_6=34$ (see A257887). The non-integer value of $a_3$ makes sense in light of the property that there is one unordered pair of triangulations for every set of two ordered pairs of triangulations in which the triangulations trade places, except in the case of the triangle, where the only choice is for both triangulations to be empty. The OEIS omits the $a_3$ term. To understand why $a_6=34$ let $T$, $Z$, and $F$ denote the triangle, Z-shaped, and fan triangulations described in one of your comments. Then there is one $TT$ pair, six $TF$ pairs, $12$ $ZF$ pairs, nine $ZZ$ pairs, and six $FF$ pairs. The $TT$ pair and three of the $ZZ$ pairs give the octahedron; all others give the graph $K_6$ minus a path of length $4$ described by Dan Uznanski in a comment here. This example shows that one must account, not only for rotations and reflections of a pair of triangulations, but also for different choice Hamiltonian circuit, which can result in different triangulation pairs for the same graph.

Danièle Huguet and Dov Tamari in La structure polyédrale des complexes de parenthésages, J. Combin. Inform. System Sci., 3(2):69–81, 1978 showed that the generating function satisfies $$ x=\sum_{j=0}^\infty C_j^2\left(x-\frac{2}{x}g(x)\right)^{j+1}. $$ In other words, $g(x)$ can be obtained by inverting the formal power series $$ \phi(x)=\sum_{j=0}^\infty C_j^2x^{j+1}, $$ which means finding the formal power series $u(x)$ such that $\phi(u(x))=x$. Then $g(x)=\frac{x}{2}(x-u(x))$. I have not been able to find a copy of Huguet and Tamari's paper, but a derivation is also given in

Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, and Stephan Wagner, Counting Planar Tanglegrams, in James Allen Fill and Mark Daniel Ward eds., 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Leibniz International Proceedings in Informatics (LIPIcs) 110:32:1–32:18, 2018.

Ralaivaosaona, Ravelomanana, and Wagner point out that $\phi(x)$ is the series expansion of a complete elliptic integral and use this to do an asymptotic analysis. They find that $a_n$ grows like a constant times $n^{-3}\left(\frac{4\pi}{4-\pi}\right)^n$. The upper bound $C_{n-2}^2$ grows like a constant times $n^{-3}\cdot16^n$. The revised upper bound has slower growth since $\frac{4\pi}{4-\pi}\approx14.64$.

Answer 2

Here is the work so far. In what follows the number of distinct Hamiltonian Maximal Planar Graphs with n vertices is $X(n)$. It should follow A000109 https://oeis.org/A000109/list up to $n=11$ when the first non Hamiltonian occurs.

Also used are the number of distinct ways to divide a polygon https://oeis.org/A000207 . $A(n)$ will be a number from this list corresponding to the number of distinct ways to triangulate a polygon with $n$ sides (offset by $2$ from the list in the link) . There is a formula for these, not written here.

Since a Maximal Planar Hamiltonian graph can be represented by a regular polygon triangulated by 'inside' edges and also triangulated again with 'outside' edges, without repeating edges, the following is suggested. $$ \begin{array}{c|cc} n & A(n) & X(n)\\ \hline 3 & 1 & 1\\ 4 & 1 & 1\\ 5 & 1 & 1\\ 6 & 3 & 2\\ 7 & 4 & 5\\ 8 & 12 & 14\\ 9 & 27 & 50\\ 10 & 82 & 233\\ 11 & 228 & 1249\\ \end{array} $$

Dividing the pentagon on the inside can be done in $1$ way with a fan $F$ from one vertex. there is only one distinct way to do it on the outside, another fan, $1\times1=1$

For the hexagon let's start with the maximum number of edges possible from either set of edges, leaving a vertex, it's $3$, making a fan $F$. Let the hexagon be $ABCDEF$. If the $3$ inside (say) edges leave node $B$. The outside edges can't repeat any of these, one of the outside edges must also join $A$ to $C$, to ensure it's triangulated and not repeat edges. This leaves a pentagon to triangulate by the outside edges, but using one less edge (one was used for $AC$) - the number of distinct ways for that is $A(5)$

There are two remaining ways to divide the hexagon with inside edges, a triangle $T$ and a $Z$ shape. Next the case where the maximum number from one set of edges leaving a vertex is $2$. If we draw diagrams using the $2$ remaining ways to divide the hexagon but not using a fan $F$, we find an extra distinct case from this, so $X(6)=A(5)+1$.

---

In a similar way using tracing paper, with the $4$ ways to divide a heptagon, it's found that $X(7) = A(6) + 2$. The $A(6)$ is the number using a Fan of $4$ edges at one corner of the heptagon, similar to above, and the $2$ comes by combining the other $3$ ways, each of the $2$ new cases came when one of the set of edges has $3$ edges from one set leaving a vertex. The case where the maximum number is $2$ edges leaving a vertex gave no extra distinct cases.

So a pattern is now being looked for of this type $$ X(n) = A(n-1)+aX(n-1)+bX(n-2)+cX(n-3)\ldots $$ where $a$, $b$, $c$ etc...are integer coefficients.

The pattern isn't clear and might involve the factors of the number $n$, perhaps the Catalan numbers? So a definite reason isn't given here for the coefficients, perhaps it's coincidence, but it's possible to build up the $X(n)$ in this way e.g. $$ \begin{array}{r|rcl|l} n & X(n) &\!=\!& A(n-1)+aX(n-1)+\ldots &\\ \hline 6 & 2 &\!\!=\!\!& 1 + 1 &\\ 7 & 5 &\!\!=\!\!& 3 + 2 &\\ 8 & 14 &\!\!=\!\!& 4 + 2\times5 &\\ 9 & 50 &\!\!=\!\!& 12 + 2\times14 + 2\times5 &\\ 10 & 233 &\!\!=\!\!& 27 + 3\times50 + 4\times14 &\\ 11 & 1248 &\!\!=\!\!& 82 + 4\times233 + 3\times50 + 6\times14 & \text{1248 instead of 1249 as there is one}\\ & & & & \text{non Hamiltonian graph for $n=11$.} \end{array} $$

Answer 3

Here is a partial answer.

In what follows the number of distinct Hamiltonian Maximal Planar Graphs with n vertices is $X(n)$. It should follow A000109 https://oeis.org/A000109/list up to $n=11$ when the first non Hamiltonian occurs.

Also used are the number of distinct ways to divide a polygon https://oeis.org/A000207 . $A(n)$ , offset by 2 from the list, will be a number from this list corresponding to the number of distinct ways to triangulate a polygon with $n$ sides There is a formula for these, not written here.

Since a Maximal Planar Hamiltonian graph can be represented by a regular polygon triangulated by 'inside' edges and also triangulated again with 'outside' edges, without repeating edges, the following is suggested.

For example the hexagon. Let's start with the maximum number of added edges leaving a vertex, it's $3$, making a fan $F$. Let the hexagon be $ABCDEF$. If the $3$ inside (say) edges leave node $B$. The outside edges can't repeat any of these, one of the outside edges must also join $A$ to $C$, to ensure it's triangulated and not repeat edges. This leaves a pentagon to triangulate by the outside edges, but using one less edge (one was used for $AC$) - the number of distinct ways for that is $A(5)$

So we would expect $X(6)$ to be $A(5) + e(2)$ where the $e(2)$ is the number of graphs where the maximum number of edges leaving any node is 2. For the hexagon $e(2)$ is 1. After $n=6$ the minimum maximum number of edges leaving any node is 3.

$X(7) = A(6) + e(3)$
$X(8) = A(7) + e(4) + e(3)$,

From $n=13$ onwards the minimum maximum number of edges leaving any node is 4

Here is a table of $A(n)$ and $X(n)$. \begin{array}{c|cc} n & A(n) & X(n)\\ \hline 3 & 1 & 1\\ 4 & 1 & 1\\ 5 & 1 & 1\\ 6 & 3 & 2\\ 7 & 4 & 5\\ 8 & 12 & 14\\ 9 & 27 & 50\\ 10 & 82 & 233\\ 11 & 228 & 1249\\ \end{array}

The pattern for the $e(i)$ isn't clear but some have been found using a computer program. $$ X(6)=1+1 $$ $$ X(7)=3+2 $$ $$ X(8)=4+8+2 $$ $$ X(9)=12+23+14+1 $$ $$ X(10)=27+84+92+29+1 $$ $$ X(11)=82+281+508+333+44+0 $$

the $X(11)$ total is one short of the A000109 numbers so the program confirms that there is at most one non-Hamiltonian graph for n=11. One graph is [was], missing for n=10 which the computer couldn’t find for Perhaps there's an undiscovered non-Hamiltonian graph with 10 nodes! [edit 14/02/2021, thanks to Will Orrick's suggestion of improving isomorphism testing, it's been found]

Now for the cases where one of the 'fan' is missing, e.g the $e(3)$ for the heptagon. The inner edges are now 3 for the fan, from, say vertex $B$, and one somewhere else. The outer edges cannot include the missing fan element (that would cause the maximum number leaving a vertex to be bigger than 3), so must include $AC$, leaving a shape with 6 sides to triangulate (with 3 more edges) which we would expect is again to do with $A(6)$, but this time with extra restrictions. The remaining outer edges can't triangulate this remaining hexagon in a way that repeats the one inner edge that's inside it, or causes more than 3 edges from a vertex.

Even if many edges were missing from a fan of inner edges coming from vertex $B$, none of them can be used by the outer edges without causing too many edges to leave a vertex, so again $AC$ is needed as one of the outer edges. If for example we were trying to find $e(16)$ for $X(30)$, then it would still seem to involve $A(29)$, but with many extras and restrictions. Extras meaning we might have to reintroduce reflections and rotations (of distinct triangulations of the remaining 29 a-gon), restrictions due to keeping the maximum number of edges leaving a vertex to 16 (other cases would be covered by $e(17)$ etc...) and also avoiding the 11 inside edges which can be inside the 29 a-gon.

Alternative system:

Now also found are a set of $e(i)$, where the maximum must come from at least one set of triangulations, inner or outer (but not both combined). i.e. one that was previously $e(5)$ in the above, having a vertex of maximum degree 7, might count as $e(4)$ below, if its connections are 2 in the polygon, 4 inner connections and one outer connection.

For this system,

$$ X(6)=1+1 $$ $$ X(7)=3+2 $$ $$ X(8)=4+7+3 $$ $$ X(9)=12+22+15+1 $$ $$ X(10)=27+77+96+32+1 $$ $$ X(11)=82+261+498+361+46+0 $$

$X(6)$ and $X(7)$ are the same as before, $X(8)$ is the first different one. It is the graph with the lowest number of vertices that can't be drawn in polygon form, where the edges from a vertex of maximum degree can all be inside edges. It has an interesting structure (below) with lots of symmetry. The $X(11)$ numbers were from a run of 600,000 graphs, it's possible there could be some 'shuffling left' by one or two (for rows above n=10), but since the numbers didn't change during the second half of the run it's likely that they are exact.

The $X(8)$ first different one, can be drawn as a regular octagon (vertices 1-8) with these inside edges (1,3), (1,4), (1,5), (5,7), (5,8) and these outside edges, which are best dawn inside again with dotted lines to appreciate the symmetry (3,5), (3,6), (3,7), (7,1), (7,2).

On the computer program and the missing graph...

Despite repeated runs, one of the n=10 Hamiltonian graphs is missing. The program finds 232 instead of 233. Perhaps there is an undiscovered n=10 non-Hamiltonian graph! To help others check this and in other ways, here are the details. [Edit: the list is complete now, thanks Will].

To check for isomorphism the program makes an ID set and used two 'tests' initially. Test1 was the sum of the squares of the degrees of all nodes, typically about 250 for n=10. If two graphs are different for Test1, they are not isomorphic.

The second test assigned a value test2(i) to each node, made up of summing, for each connecting node, j, (excluding itself) deg(j)*[11+deg(j)-deg(i)]. Where deg(j) is the degree of node j. Test2 is the sum of all these values. If two graphs are different for Test2, again,they are not isomorphic. the 11 is random to increase the size and make it less likely that the same number can be got by summing a different set of numbers the -deg(i) is included for a similar reason.

So for two graphs to be isomporphic they should have identical Test1 and Test2.

This system didn't distinguish and find all 50 for n=9, it found 48. So another test, Test3, was introduced.

The third test assigned a value test3(i) to each node, made up of summing, for each connecting node, j, (excluding itself) test2(j)*[test2(j)+2-deg(i)]. Test3 is the sum of all these values.

Now all 50 were found for n=9, but 232 out of 233 for n=10. So Test4 was introduced, which is like Test3, test4(i) is by summing test3(j)*[test3(j)+2-deg(i)] and Test4 is the sum of these. [Edit, after Will's 'edge ID' was added, all 233 have been found].