Subhamiltonian toroidal graphs

Abstract

The problem of determining whether a graph contains a Hamiltonian cycle is difficult but has been well-studied. A related question asks when is a graph, embeddable on a surface S, a subgraph of a Hamiltonian graph which is also embeddable on S? In particular, if a graph has genus g, is it a subgraph of a Hamiltonian graph of genus g? We answer this question for all complete graphs and complete m-partite graphs of genus 0 and 1.

1 Background and definitions

Let $K_n$ denote the complete graph on n vertices and $K_{r_1, r_2, \ldots , r_m}$, $m \ge 1$, denote the complete m-partite graph. We will assume $r_1 \ge r_2 \ge \cdots \ge r_{m-1} \ge r_m \ge 1$. The join of two graphs, G and H, is the graph obtained by taking disjoint copies of G and H and connecting every vertex of G to every vertex of H. Note that $K_{r_1, r_2, \ldots , r_m}$ can be though of as the join of the complements of the complete graphs, $K_{r_1}, K_{r_2}, \ldots , K_{r_m}$. A graph is embeddable in a surface S if it can be drawn on this surface without edges crossing. If we let $S_h$ denote the sphere with h handles, the (orientable) genus g of a graph G is the smallest value of h for which G can be embedded in $S_h$. In particular, genus 0 graphs can be embedded in the plane and genus 1 graphs can be embedded on a torus. It is known that the genus of $K_n,$ where $n\ge 1,$ is given by $\lceil (n-3)(n-4)/12 \rceil$ and the genus of $K_{m,n}$ is given by $\lceil (m-2)(n-2)/4 \rceil$ [3, pages 118–119]. Euler’s formula for graphs embeddable on an orientable surface of genus g is given by $v-e+f=2-2g$, where v is the number of vertices, e is the number of edges, and f is the number of faces in a drawing without crossings [3, page 103].

A Hamiltonian graph is one which contains a simple cycle that visits every vertex exactly once. We expand upon the notion of a subhamiltonian graph given in [4], which describes such a graph as one that is a subgraph of a planar Hamiltonian graph. Here we define an $S_h$ subhamiltonian graph as one that is a subgraph of a Hamiltonian graph embeddable in $S_h$. Of course, one can always add edges to make a graph Hamiltonian, but the interesting question is when can this be done without increasing the genus of the augmented graph. We provide a partial answer to this question for graphs of genus 0 and 1. In particular, we will show that all complete graphs and complete k-partite graphs of genus 0 and 1 have this property.

2 Subhamiltonian planar graphs

To understand the planar case, we appeal to a structure called a book (see [1, 4, 5]). An n-book consists of n half planes joined together at a common line, called the spine. To embed a graph in a book, the vertices are placed along the spine and each edge of the graph is embedded on a single page so that no two edges cross each other. The book thickness of a graph G is the smallest n for which G admits an n-book embedding. If the vertices are placed in the order $v_1, v_2, \ldots , v_m$ along the spine, we may add any missing edges of the form $\{v_k, v_{k+1}\}, k = 1, 2, \ldots , m-1$, and the edge $\{v_1, v_m\}$ onto any page of the book without creating edge crossings. So, with respect to the book structure, all graphs that are embedded in a n-page book are subgraphs of Hamiltonian n-page embeddable graphs. With this representation, it is clear that all two-page embeddable graphs are $S_0$ subhamiltonian. Furthermore, if a graph is $S_0$ subhamiltonian, one can draw the graph in the plane and trace a Hamiltonian cycle (adding edges, if needed), through the vertices, without causing crossings. This Hamiltonian cycle induces a two-page book embedding in which the edges interior to the cycle form one page, the edges outside the cycle form a second page, and the edges along the cycle can be placed on either page. Now the following result (see [1, 5]) is clear.

Theorem 1

A graph G is $S_0$ subhamiltonian if and only if it is embeddable in a 2-page book.

We note that not all planar graphs are $S_0$ subhamiltonian. In particular, the Goldner–Harary graph is the smallest maximal planar graph that does not contain a Hamiltonian cycle. Since it is maximal, any edges added to form a Hamiltonian cycle would increase the genus (see [1]). This graph has 11 vertices and is the smallest example of such a graph. Hence, all planar graphs with fewer than 11 vertices are $S_0$ subhamiltonian. Some planar graphs are $S_0$ subhamiltonian and some are not. Yannakakis [7, 8] showed that all planar graphs can be embedded in a four-page book. So, the planar graphs that are not $S_0$ subhamiltonian would be those planar graphs with book thickness 3 or 4. There are numerous known families of planar graphs with book thickness 1 or 2. Trees, square grids, planar Hamiltonian graphs, planar bipartite graphs, and all planar triangle-free graphs are $S_0$ subhamiltonian [4].

Theorem 2

All planar complete graphs and complete m-partite graphs are $S_0$ subhamiltonian.

Proof

As noted earlier, the genus of $K_n,$ where $n\ge 1,$ is given by $\lceil (n-3)(n-4)/12 \rceil$. Thus, $K_n$ is planar only for $n = 1, 2, 3, 4$. We note that if G is $S_0$ subhamiltonian, then so is any subgraph of G. As one can easily check, $K_4$ is planar and Hamiltonian. Hence, $K_1, K_2,$ and $K_3$ are also $S_0$ subhamiltonian.

Similarly, since the genus of $K_{m,n}$ is given by $\lceil (m-2)(n-2)/4 \rceil$, it follows that the graphs $K_{m,1}$ and $K_{m,2}$ are planar and bipartite for all $m \ge 1$. Since $K_{3,3}$ is non-planar, it follows that all complete planar bipartite graphs are $S_0$ subhamiltonian. The set of complete planar tripartite graphs consists of $K_{q,1,1} (q \ge 1)$, $K_{2,2,1},$ and $K_{2,2,2}$, since all others would contain a $K_{3,3}$ subgraph. As one can easily check, the graph $K_{2,2,2}$ is planar and Hamiltonian. Hence, it is $S_0$ subhamiltonian, as is its subgraph, $K_{2,2,1}$. When $q \ge 3$, the graph $K_{q,1,1}$ is not Hamiltonian. However, we see that it is planar and subhamiltonian for all $q \ge 1$ via the following two-page book embedding. Let $\{a_1, a_2, \ldots , a_q\},\{b\},$ and $\{c\}$ be the vertex sets of $K_{q,1,1}$. Now position the vertices along the spine in the order $a_1, a_2, \ldots , a_q, b, c$. Edges of the form $\{a_i, b\}$, where $i = 1,2,\ldots , q$ can be embedded on the first page and those of the form $\{a_i, c\}$, where $i = 1,2,\ldots , q$ can be embedded on the second page without edge crossings. Finally, the edge $\{b,c\}$ can be embedded on either of the two pages. Hence, all planar tripartite graphs are $S_0$ subhamiltonian. The only complete planar multipartite graphs with four parts are $K_{1,1,1,1} = K_4$ and $K_{2,1,1,1}$, since all others would contain a $K_{3,3}$ subgraph. We note that $K_{2,1,1,1}$ is planar and Hamiltonian, so both graphs are $S_0$ subhamiltonian. There are no planar multipartite graphs with five or more parts, since such graphs would contain a $K_5$ subgraph. Hence, all planar complete graphs and complete m-partite graphs are $S_0$ subhamiltonian. This completes the proof. $\square$

3 Subhamiltonian toroidal graphs

For the toroidal case, we appeal to the notion of a torus book (see [6]). An n-page torus book is formed by taking the equator of a torus as the spine and nested torus shells, joined together at the spine, as the pages. The torus-book thickness of a graph is the least number of pages needed to embed a graph G so that the vertices of G lie on the spine and each edge of G lies on a single page so that no two edges cross. It is clear that any graph that is one-page torus-book embeddable would also be $S_1$ subhamiltonian via completing the Hamiltonian cycle along the spine, appending any missing edges. Also, any Hamiltonian toroidal graph would be $S_1$ subhamiltonian, but not necessarily with the vertices lined up along the equator. As in the planar case, there are maximal non-Hamiltonian toroidal graphs. Such graphs can be formed by repeated stellations of the faces of graphs embedded on a torus, as was done for planar graphs in [1] . Thus not all genus 1 graphs will be $S_1$ subhamiltonian. We will show that all complete graphs and complete m-partite graphs are not only $S_1$ subhamiltonian, but are embeddable in a one-page torus book with the Hamiltonian cycle along the spine.

Via the genus formula $g = \lceil (n-3)(n-4)/12 \rceil$ for complete graphs, we see that $K_5$, $K_6$, and $K_7$ are the only complete graphs of genus 1. Since these graphs are embeddable on a torus and are Hamiltonian, they are all necessarily $S_1$ subhamiltonian. In Fig. 1, we give an embedding of a $K_7$ in a single torus page, so the desired Hamiltonian cycle can be expressed along the spine of this one-page torus book. By deleting one or two vertices of $K_7$, we attain one-page torus book embeddings of $K_6$ and $K_5$.

Using the genus formula $g = \lceil (m-2)(n-2)/4 \rceil$ for $K_{m,n}$, we see that the complete bipartite graphs of genus 1 are: $K_{3,3}, K_{4,3}, K_{5,3}, K_{6,3},$ and $K_{4,4}$. Each of these graphs is a subgraph of $K_{6, 1, 1, 1}$ or $K_{4, 1, 1, 1, 1}$. We give one-page torus book embeddings of these graphs in Figs. 3 and 6. Hence, all bipartite graphs of genus 1 are $S_1$ subhamiltonian. In the absence of general formulas for the genus of m-partite graphs when $m \ge 3$, we provide the following lemma.

Lemma 1

If either $K_n$ or $K_{r_1, r_2, \ldots , r_m}$, where $r_1 \ge r_2 \ge \cdots \ge r_m \ge 1$, is toroidal, then it must be a subgraph of $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ $K_{4, 1, 1,1,1},$ or $K_{q, 1, 1} (q \ge 1)$.

Fig. 1

$K_{7}$

Proof

The largest complete toroidal graph is $K_7$. Hence, $K_n$ is toroidal for all $n \le 7$.

Now we will consider toroidal complete m-partite graphs $K_{r_1,r_2, \ldots , r_m}$, where $r_1 \ge r_2 \ge \cdots \ge r_m \ge 1$ and $m \ge 1$. Note that in the case where $m = 1$, the graph contains $r_1$ vertices and no edges, so it is subgraph of the planar graph $K_{q, 1, 1}$. So, we will assume that $m \ge 2$. Furthermore, by the genus formula for bipartite graphs, $K_{7,3}$ and $K_{5,4}$ have genus 2. Hence, we seek graphs that do not contain either of these as subgraphs. We will proceed by considering the possible values for $r_1$, the largest of the $r_i$ values. Also, Euler’s formula yields a maximum edge bound of 3v for simple toroidal graphs with v vertices.

Case 1: $r_1 \ge 7$

Then $r_2 + r_3 + \cdots + r_m < 3$, otherwise the graph contains a $K_{7, 3}$ subgraph. Hence, the only possibilities are $K_{r_1, 1}, K_{r_1, 2}$, and $K_{r_1, 1, 1}$. These are all contained within $K_{q, 1, 1}$, which is planar.

Case 2: $r_1 = 5$ or $r_1 = 6$

Then $r_2 + r_3 + \cdots + r_m < 4$, otherwise the graph contains a $K_{5, 4}$ subgraph. All cases that satisfy these conditions are subgraphs of $K_{6,1,1,1}$.

Case 3: $r_1 = 4$

Then $r_2 + r_3 + \cdots + r_m < 5$, otherwise the graph contains a $K_{5, 4}$ subgraph. All cases that satisfy these conditions are subgraphs of $K_{4,1,1,1,1}$.

Case 4: $r_1 = 3$

Then $r_2 + r_3 + \cdots + r_m < 7$, otherwise the graph contains a $K_{7, 3}$ subgraph. We now consider the case where $m \ge 6$ and $r_2 + r_3 + \cdots + r_m \le 6$. Any such complete multipartite graph would contain a $K_{3,1,1,1,1,1}$ subgraph. However, using Euler’s result that the sum of the degrees is twice the number of edges [3], we see that this graph has $(3 \times 5 + 5 \times 7)/2 = 25$ edges, which violates the $3v = 3\times 8 = 24$ edge bound for simple toroidal graphs. Hence, $m \le 5$. Suppose that $m = 5$. Then we must have $r_1 + r_5 \ge 4$, which forces $r_2 + r_3 + r_4 \le 4$, otherwise we will have a $K_{5, 4}$ subgraph. The largest possible remaining graph meeting these conditions is $K_{3,2,1,1,1}$. Now suppose that $m = 4$. By a similar argument, we must have $r_2 + r_3 \le 4$. One possibility is $K_{3,3,1,1} \subseteq K_{3,2,1,1,1}$. The next possibility is $K_{3,2,2,2}$, which is not toroidal since it contains a $K_{5, 4}$ subgraph. The remaining graphs with $m = 4$ are contained within $K_{3,2,2,1} \subseteq K_{3,2,1,1,1}$. Now, if we let $m \le 3$, the largest possibility is $K_{3,3,3}$.

Case 5: $r_1 = 2$

Suppose $m \ge 7$. Then the graph will contain a $K_{2,1,1,1,1,1,1}$ subgraph. But, this graph contains the subgraph $K_{2,2,1,1,1,1}$, which is not toroidal since it has $(4 \times 6 + 4 \times 7)/2 = 26$ edges, violating the $3v = 3 \times 8 = 24$ toroidal edge bound. So, if $m = 6$, the only possible graph is $K_{2,1,1,1,1,1} \subseteq K_7$. Now suppose $m = 5$. The graph $K_{2,2,2,1,1}$ has $(6 \times 6 + 2 \times 7)/2 = 25$ edges, exceeding the $3v = 3 \times 8 = 24$ toroidal edge bound. The next smallest graph is $K_{2,2,1,1,1} \subseteq K_7$. If $m \le 4$, all remaining graphs are subgraphs of $K_{2,2,2,2}$.

Case 6: $r_1 = 1$.

If $m \ge 8$, then the graph contains a $K_8$ subgraph and is not toroidal. Hence, $m \le 7$. The graph $K_{1,1,1,1,1,1,1} = K_7$. $\square$

Lemma 2

The graphs $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ $K_{4, 1, 1,1,1},$ and $K_{q, 1, 1} (q \ge 1)$ all embeddable in a one-page torus book.

Fig. 2

$K_{3,3,3}$

Fig. 3

$K_{6,1,1,1}$

Proof

The graph $K_{q, 1, 1} (q \ge 1)$ is planar and embeddable in a two-page book. A two-page book is clearly contained in a one page torus book, so this embedding yields a one-page torus book embedding, as well (with no edges wrapping around the torus).

Figures 1, 2, 3, 4, 5 and 6 give one-page torus book embeddings of $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ and $K_{4, 1, 1,1,1}.$ $\square$

Fig. 4

$K_{2,2,2,2}$

Fig. 5

$K_{3,2,1,1,1}$

Fig. 6

$K_{4,1,1,1,1}$

Note that all $K_{q, 1, 1} (q \ge 1)$ are planar, whereas $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ and $K_{4, 1, 1,1,1},$ are non-planar since each of these graphs contains a $K_5$ or $K_{3,3}$ subgraph. Since each of these graphs is embeddable in a one-page torus book, by adding any missing edges along the spine we see that these graphs are all subgraphs of toroidal Hamiltonian graphs. The graphs $K_7,$ $K_{3, 3, 3},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ and $K_{4, 1, 1,1,1}$ already contain Hamiltonian cycles, so they are naturally $S_1$ subhamiltonian. However, $K_{6, 1, 1, 1}$ and $K_{q, 1, 1}, q\ge 3$ are not Hamiltonian, so we must add edges to attain the desired Hamiltonian cycle. As a planar graph, $K_{q, 1, 1}$ is $S_0$ subhamiltonian and the non-planar graph $K_{6, 1, 1, 1}$ is $S_1$ subhamiltonian.

In fact, every complete graph and complete m-partite graph of genus one is a subgraph of one of the six toroidal $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ or $K_{4, 1, 1,1,1}$. The following theorem gives a complete listing of all complete and complete m-partite $S_1$ subhamiltonian graphs.

Theorem 3

The following is a complete list of all 35 $S_1$ subhamiltonian complete and complete m-partite graphs. 3

• 1. Two parts: $K_{3,3}$, $K_{4,3}$, $K_{5,3}$, $K_{6,3}$, $K_{4,4}$

• 2. Three parts: $K_{3,2,1}$, $K_{4,2,1}$, $K_{5,2,1}$, $K_{6,2,1}$ , $K_{5,2,3}$, $K_{4,2,2}$, $K_{3,3,1}$, $K_{4,3,1}$ , $K_{3,3,2}$, $K_{3,3,3}$

• 3. Four parts: $K_{3,1,1,1}$, $K_{4,1,1,1}$, $K_{5,1,1,1}$, $K_{6,1,1,1}$, $K_{2,2,1,1}$, $K_{3,2,1,1}$, $K_{4,2,1,1}$, $K_{2,2,2,1}$, $K_{3,2,2,1}$, $K_{2,2,2,2}$, $K_{3,3,1,1}$

• 4. Five parts: $K_{1,1,1,1,1} = K_5$, $K_{2,1,1,1,1}$, $K_{3,1, 1,1,1}$, $K_{4,1, 1,1,1}$, $K_{2,2,1,1,1}$, $K_{3,2,1,1,1}$

• 5. Six parts: $K_{1,1,1,1,1,1} = K_6$, $K_{2,1,1,1,1,1}$

• 6. Seven parts: $K_{1,1,1,1,1,1,1} = K_7$

Proof

The 35 listed graphs are non-planar since all but $K_{1,1,1,1,1} = K_5$ contain a $K_{3,3}$ subgraph and $K_5$ is non-planar. Furthermore, one may easily check that each of the 35 graphs is a subgraph of at least one of $K_7,$ $K_{3, 3, 3},$ $K_{6, 1, 1, 1},$ $K_{2, 2, 2, 2},$ $K_{3, 2, 1,1,1},$ or $K_{4, 1, 1,1,1}.$

$\square$

Graphs such as $K_n (n \ge 3)$, the n-dimensional cube graph $(n \ge 2)$, and the bipartite graph $K_{n,n} (n\ge 2)$ of genus g are Hamiltonian and will necessarily be $S_g$ subhamiltonian. This will also be true for any other genus g graphs that contain Hamiltonian cycles. However, it is not clear which non-Hamiltonian genus g graphs also have this property.