Maria Timkov ´ a´

Institute of Mathematics, Faculty of Science, P.J. Saf ˇ arik University ´ Jesenna 5, 041 54 Ko ´ sice, Slovak Republic ˇ

maria.timkova@student.upjs.sk

The H-force number of a hamiltonian graph G is the smallest number k with the property that there exists a set W ⊆ V (G) with |W| = k such that each cycle passing through all vertices of W is a hamiltonian cycle. In this paper, we determine the H-force numbers of generalized dodecahedra.

Keywords: hamiltonian graph, H-force number, generalized dodecahedron Mathematics Subject Classification : 05C45

Throughout this paper we consider graphs without loops or multiple edges; for terminology not defined here we refer to [3].

Let G = (V, E) be a hamiltonian graph and let W be a nonempty subset of V (G). A cycle in G is a W-cycle if it contains all vertices of W. The set W enforces a hamiltonian cycle in G (or, W is an H-force set) if each W-cycle of G is hamiltonian. The H-force number of G, denoted h(G), is the cardinality of the smallest H-force set in G.

The H-force number of a graph was introduced in [4] as a possible tool which unifies several concepts in theory of hamiltonian graphs and allows to develop a kind of hierarchic partition in this graph family. Note that there are several different approaches which develop such a hierarchy like pancyclicity or hamiltonian-connectedness, the other way how to study the quality of a hamiltonian graph is to study the existence of hamiltonian cycles passing through particular edges, see [5], [8]. One possible approach how to classify hamiltonian graphs concerns the notion of k-hamiltonicity:

Received: 23 May 2013, Revised: 13 October 2013, Accepted: 23 October 2013.

given an n-vertex graph G and an integer k, 1 ≤ k ≤ n − 3, G is k-hamiltonian if, for all sets U ⊆ V , 0 ≤ |U| ≤ k, the graph G − U (obtained from G by deleting all vertices of U) is hamiltonian. In particular, a graph is 1-hamiltonian if it is hamiltonian and the graph that results from deletion of any vertex is also hamiltonian. There are several sufficient conditions for graphs to be 1-hamiltonian, in many cases similar to the classical conditions for hamiltonicity (see [1], [2] or [7]). Note that if a graph is k-hamiltonian for k ≥ 1, then its H-force number is equal to its order, and vice versa; thus, it is interesting to explore graphs with H-force number being less than their orders. The graphs with small H-force number were studied in [4], which provided the complete characterization of graphs with H-force number 2 (or 3 in the case of 3-connected graphs, and 4 for 3-connected planar graphs, respectively). In general, determining the H-force number of a hamiltonian graph is a difficult problem, even for special graphs. The aim of this paper is to determine the H-force numbers of generalized dodecahedra, i.e. the 3-connected planar cubic graphs consisting of two k-gonal faces separated by the strip of 2k pentagons.

Given an integer k, the graph G^k is constructed in the following way: take three cycles C^O = v1v² . . . vkv1, C^M = vk+1vk+2vk+3 . . . v3kvk+1, and C^I = v3k+1v3k+2 . . . v4kv3k+1 drawn in the plane such that C^M lies in the interior of C^O and C^I lies in the interior of C^M (we refer to CO, CM, C^I as the outer, middle and inner cycle of Gk, the above described labelling of vertices will be called primary in the sequel). Next, for each i = 1, . . . , k, add new edges vivk+2i−1, vk+2iv3k+ⁱ . This can be done is such a way that the resulting graph G^k is plane; it contains two k-gons separated by two layers of 2k pentagons in total, is 3-connected and cubic, and has 4k vertices and 6k edges.

Theorem 1. Let G^k be a generalized dodecahedron, then

• (i) h(G3) = 9;
• (ii) h(G5) = 15;
• (iii) h(Gk) = ^11k 3 if k ≡ 0 (mod 3), k ≥ 6;
• (iv) h(Gk) = 4k − 2 if k ≡ 1 (mod 3);
• (v) h(Gk) = ¹¹k−⁷ 3 if k ≡ 2 (mod 3), k ≥ 8.

Three edges a, b, c ∈ E(Gk) are concurrent if a ∈ E(CO), b ∈ E(CM), c ∈ E(C^I ) and they belong to two adjacent pentagons with b being their common edge. This term will be also used for any two edges of a concurrent triple.

From the geometrical point of view, when constructing Gk, we can arrange cycles CM, C^O and C^I in such a way that their drawings are regular polygons, their circumscribed circles are concentric and each half line originating from the common centre of circles intersects either no vertex (and in this case it intersects three edges, one of each polygon, that accord to a concurrent triple in Gk) or exactly two vertices of the polygons (according to adjacent vertices of Gk), see Fig. 1.

Note that, in Gk, there exists an automorphism that maps any vertex vⁱ ∈ V (C^I ) ∪ V (CO) to arbitrary vertex v^j ∈ V (C^I ) ∪ V (CO) as well as an automorphism that maps any v` ∈ V (CM) to any v^m ∈ V (CM).

Fig. 1

Let \(v_rv_{r+1}, v_sv_{s+1}, v_tv_{t+1} \in E(G_k)\) be three concurrent edges (for the case \(v_sv_t \in E(G_k)\)) see Fig. 2A, analogously the case \(v_rv_s \in E(G_k)\)). If we replace the path \(v_r, v_{r+1}\) by the path \(v_r, v_{r+1}\), the path \(v_s, v_{s+1}\) by the path \(v_s, v_{s_1^*}, v_{s_2^*}, v_{s+1}\), the path \(v_t, v_{t+1}\) by the path \(v_t, v_{t_1^*}, v_{t+1}\), and add two new edges \(v_{r_1^*}v_{s_1^*}, v_{s_2^*}v_{t_1^*}\) then we obtain the graph \(G_{k+1}\). We say that we enlarge the graph \(G_k\) to \(G_{k+1}\) on the concurrent triple \(v_rv_{r+1}, v_sv_{s+1}, v_tv_{t+1}\). Repeating this operation, \(G_k\) can be enlarged to \(G_{k+2}, G_{k+3}\), etc. (Note that \(V(G_k) \subseteq V(G_{k+1}) \subseteq V(G_{k+2}) \subseteq V(G_{k+3}) \subseteq \ldots\))

In the sequel, a cycle C of a graph G misses exactly the vertices of a set \(S \subset V(G)\), \(|S| \leq |V(G)| - 3\), if \(V(C) = V(G) \setminus S\). Note, that if C is nonhamiltonian cycle of G then any H-force set of G contains a vertex of G - C.

Lemma 2. Let a, b, c be three concurrent edges of \(G_k\) and let \(G_{k+1}\) (\(G_{k+3}\)) be enlarged from \(G_k\) on this triple. If C is a cycle of \(G_k\) containing all three edges a, b, c (any two of them), then in \(G_{k+1}\) (\(G_{k+3}\)) there is a cycle \(C^*\) missing exactly the same vertices as C in \(G_k\); moreover, \(C^*\) contains three (two) concurrent edges as well.

Proof. Let C be a cycle of \(G_k\), let \(S \subset V(G_k)\) be the set of vertices missed by C, let \(v_r v_{r+1} \in E(C_I)\), \(v_s v_{s+1} \in E(C_M)\), \(v_t v_{t+1} \in E(C_O)\) be concurrent edges, and let \(G_{k+1}\) and \(G_{k+3}\) be enlarged from \(G_k\) on the mentioned triple of edges (see Fig. 2A, 2B and 3A, 3B, respectively).

• 1. If C contains all three concurrent edges \(v_rv_{r+1}\), \(v_sv_{s+1}\), \(v_tv_{t+1}\), then replace in C the path \(v_r, v_{r+1}\) by the path \(v_r, v_{r_1^*}, v_{r+1}\), the path \(v_s, v_{s+1}\) by the path \(v_s, v_{s_1^*}, v_{s_2^*}, v_{s+1}\), and the path \(v_t, v_{t+1}\) by the path \(v_t, v_{t_1^*}, v_{t+1}\) to create the cycle \(C^*\) in \(G_{k+1}\) containing all four new vertices and thus missing exactly the vertices of S (Fig. 2B). Moreover \(C^*\) contains three concurrent edges of \(G_{k+1}\) (for example \(v_rv_{r_1^*}, v_sv_{s_1^*}, v_tv_{t_1^*}\)).
• 2. (a) If C contains exactly two concurrent edges \(v_sv_{s+1}\), \(v_tv_{t+1}\) (similarly for \(v_rv_{r+1}\), \(v_sv_{s+1} \in E(C)\)) then replace in C the path \(v_s\), \(v_{s+1}\) by the path \(v_s\), \(v_{s_1^*}\), \(v_{r_1^*}\), \(v_{r_2^*}\), \(v_{r_3^*}\), \(v_{s_5^*}\), \(v_{s_6^*}\), \(v_{s+1}\) and the path \(v_t\), \(v_{t+1}\) by the path \(v_t\), \(v_{t_1^*}\), \(v_{s_2^*}\), \(v_{s_3^*}\), \(v_{s_4^*}\), \(v_{t_2^*}\), \(v_{t_3^*}\), \(v_{t+1}\) to create the cycle \(C^*\) in \(G_{k+3}\) containing all 12 new vertices and thus missing exactly the vertices of S (Fig. 3B). Moreover \(C^*\) contains two concurrent edges of \(G_{k+3}\) (for example \(v_sv_{s_1^*}\), \(v_tv_{t_1^*}\)).
  • (b) If C contains exactly two concurrent edges \(v_rv_{r+1}\), \(v_tv_{t+1}\) then replace in C the path \(v_r, v_{r+1}\) by the path \(v_r, v_{r_1^*}, v_{s_1^*}, v_{s_2^*}, v_{s_3^*}, v_{r_2^*}, v_{r_3^*}, v_{r+1}\) and the path \(v_t, v_{t+1}\) by the path \(v_t, v_{t_1^*}, v_{t_2^*}, v_{s_3^*}, v_{t_3^*}, v_{t+1}\) to create the cycle \(C^*\) in \(G_{k+3}\) containing all 12 new vertices and thus missing exactly the vertices of S. Moreover \(C^*\) contains two concurrent edges of \(G_{k+3}\) (for example \(v_rv_{r_1^*}, v_tv_{t_1^*}\)).

Now, the vertices in \(G_{k+1}\) and \(G_{k+3}\) can be relabelled to obtain primary labelling.

In the next, \(d_H(x, y)\) denotes the distance of x, y with respect to the graph H.

Lemma 3. Let \(k \equiv 0 \pmod{3}\), \(k \geq 6\), and let \(v_i, v_j \in V(C_M) \cap V(G_k)\) such that \(2 \neq d_{C_M}(v_i, v_j) \equiv \pm 2 \pmod{6}\). Then there exists a cycle in \(G_k\) that misses exactly the vertices \(v_i, v_j\).

Proof. Because of symmetry of \(G_k\) and the condition \(2 \neq d_{C_M}(v_i, v_j) \equiv \pm 2 \pmod{6}\) we can assume that i = k+1 and \(k+5 \leq j \leq 2k\). For \(j-i=j-k-1 \equiv \pm 2 \pmod{6}\) we prove that there exists a cycle in \(G_k\) that misses exactly two vertices \(v_i, v_j\). Note that any such cycle contains the following two pairs of concurrent edges: \(v_1v_2, v_{k+2}v_{k+3}\) and \(v_kv_1, v_{3k-1}v_{3k}\).

For k = 6 is i = 7, j = 11 and a desired cycle in \(G_6\) is shown on Fig. 4.

For \(k \geq 9\) we consider a cycle C' in \(G_{k-3}\) that misses exactly two vertices \(v_{k-2}, v_{j-3} \in V(G_{k-3}) \cap V(C_M)\) with the distance (on the cycle \(C_M\) in \(G_{k-3}\)) \(j-3-(k-2)=j-k-1\equiv \pm 2\pmod{6}\) for \(j\leq 2k-2\) or distance \(2k-6-(j-k-1)\equiv \mp 2\pmod{6}\) for \(2k-1\leq j\leq 2k\). The cycle C' contains concurrent edges \(v_{k-3}v_1, v_{3k-10}v_{3k-9}\) and by previous lemma we obtain a desired cycle in \(G_k\).

Later we use this lemma in the following way: If W is an H-force set in \(G_k\), \(k \equiv 0 \pmod 3\), that does not contain a vertex \(v_i \in V(C_M)\), then every vertex \(v_j \in V(C_M)\) with \(2 \neq d_{C_M}(v_i, v_j) \equiv \pm 2 \pmod 6\) belongs to W.

Lemma 4. Let k ≡ 2 (mod 3), k ≥ 8, and let vⁱ , v^j , v` ∈ V (CM) ∩ V (Gk) such that these vertices split C<sup>M</sup> into three paths of lengths at least 4 and congruent to 4, 4 and 2 modulo 6. Then there exists a cycle in G<sup>k</sup> that misses exactly the vertices v<sup>i</sup> , v<sup>j</sup> , v` .

Proof. Because of symmetry of G^k we can assume that k+1 = i < j < `. The vertices v<sup>i</sup> , v<sup>j</sup> , v` ∈ V (CM) split the cycle C^M into three paths of lengths pⁱ := j − i ≡ 4 (mod 6), p^j := ` − j ≡ 4 (mod 6), and p` := 3k + 1 − ` ≡ 2 (mod 6), p` 6= 2.

For k = 8 is i = 7, j = 11, ` = 15, and a desired cycle in G⁸ is shown on Fig. 5.

For k ≥ 11 one of pⁱ , p^j , p` must be at least 10.

• 1. If pⁱ ≥ 10 then we consider a cycle C 0 in Gk−³ that misses exactly three vertices vk−² = vi−3, vj−9, v`−<sup>9</sup> splitting the middle cycle of Gk−<sup>3</sup> into three paths of length p<sup>i</sup> − 6, p<sup>j</sup> , p` (congruent to 4, 4, and 2 modulo 6). The cycle C ⁰ must contain concurrent edges v1v² and vk−1vk. Through enlargement the graph Gk−³ to G^k on the triple given by mentioned two edges we obtain, by Lemma 2, a desired cycle in Gk.
• 2. If pⁱ = 4 and p^j ≥ 10 then we consider a cycle C 0 in Gk−³ that misses exactly three vertices vi−3, vj−3, v`−<sup>9</sup> splitting the middle cycle of Gk−<sup>3</sup> into three paths of length p<sup>i</sup> , p<sup>j</sup> − 6, p` (congruent to 4, 4, and 2 modulo 6). The cycle C ⁰ must contain following two concurrent edges: vj−2vj−¹ and the corresponding edge from the outer cycle of Gk−3. By Lemma 2 we obtain a desired cycle in Gk.
• 3. If pⁱ = p^j = 4 and p` ≥ 10 then we consider a cycle C 0 in Gk−<sup>3</sup> that misses exactly three vertices vi−3, vj−3, v`−³ splitting the middle cycle of Gk−³ into three paths of length pi , p^j , p` − 6 (congruent to 4, 4, and 2 modulo 6). The cycle C <sup>0</sup> must contain following two concurrent edges: v`−2v`−¹ and the corresponding edge from the outer cycle of Gk−3. By Lemma 2 we obtain a desired cycle in Gk.

In a similar way, one can prove

Lemma 5. Let k ≡ 2 (mod 3) and let R ⊆ V (Gk) be

1. the set of two vertices vⁱ ∈ V (CM) and v^j ∈ V (C^I ) where vⁱ is adjacent to a vertex on C^O and 2 6= d(vⁱ , v^j ) 6≡ 1 (mod 3) (see Fig. 6), or

• 2. the set of three vertices vⁱ , v^j , v` ∈ V (CO) such that these vertices split C<sup>O</sup> into three paths of lengths congruent to 1, 1 and 0 modulo 3 (see Fig. 7), or
• 3. the set of three vertices v<sup>i</sup> , v<sup>j</sup> ∈ V (CO) and v` ∈ V (CM) where both v^j and v` are adjacent to vⁱ (see Fig. 8).

Then there exists a cycle in G^k that misses exactly the vertices of R.

Lemma 6. Let k ≡ 0 (mod 3) and let R ⊆ V (Gk) be

• 1. the set of one vertex of C^O (see Fig. 9), or
• 2. the set of two adjacent vertices of C^M (see Fig. 10).

Then there exists a cycle in G^k that misses exactly the vertices of R.

Lemma 7. Let k ≡ 1 (mod 3) and let R ⊆ V (Gk) be

• 1. a cycle that misses exactly one vertex of C^M (see Fig. 11), and
• 2. a cycle that misses exactly two vertices vⁱ ∈ V (CO) and v^j ∈ V (C^I ) with d(vⁱ , v^j ) = 4 (see Fig. 12), and
• 3. a cycle that misses exactly two vertices vⁱ , v^j ∈ V (CO) with d^CO (vⁱ , v^j ) 6≡ 2 (mod 3) (see Fig. 13).

Then there exists a cycle in G^k that misses exactly the vertices of R.

Lemma 8. Let k ≥ 3 and let R ⊆ V (Gk) be

• 1. the set of two vertices vⁱ ∈ V (CM) and v^j ∈ V (CO) where vⁱ is adjacent to a vertex of C^O and d(vⁱ , v^j ) ≥ 3 (see Fig. 14), or
• 2. the set of two vertices vⁱ ∈ V (CO) and v^j ∈ V (C^I ) with d(vⁱ , v^j ) 6= 4 (see Fig. 15A, 15B), or
• 3. the set of two vertices vⁱ , v^j ∈ V (CM) with 1 6= d^CM (vⁱ , v^j ) ≡ 1 (mod 2) (see Fig. 16), or
• 4. the set of three vertices vⁱ , v^j ∈ V (CM) and v` ∈ V (CO) where both v<sup>j</sup> and v` are adjacent to vⁱ (see Fig. 17).

Then there exists a cycle in G^k that misses exactly the vertices of R.

In the following, we will use the necessary condition for hamiltonicity of plane graphs:

Theorem 9 (Grinberg [6]). Let G be a plane hamiltonian graph and C be a hamiltonian cycle in G. Let \(g_i\) be the number of i-gonal faces in the exterior of C and \(f_i\) be the number of i-gonal faces in the interior of C. Then \(\sum_{i>3} (i-2)(f_i-g_i)=0\).

Proof of Theorem 1.

For \(1 \le j \le 2k\), denote the edges of \(G_k\) not belonging to the cycles \(C_O\), \(C_M\), or \(C_I\), as follows

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Case (ii) The result for dodecahedron (k = 5) was proved in [4]. A smallest H-force set is \(V(G_5) - \{v_6, v_8, v_{10}, v_{12}, v_{14}\}.\)

Case (v) Let \(k \equiv 2 \pmod{3}\), \(k \ge 8\).

Let \(S = \{v_{k+1}, v_{3k+1}, v_{3k+3}, v_{3k+6}, v_{3k+9}, ..., v_{3k+k-2}, v_{4k}\}\). First, we show that the set \(Z = V(G_k) \setminus S\) is an H-force set, that is, for any nonempty subset T of S, there is no cycle that misses exactly the vertices of T (i.e. there is no nonhamiltonian Z-cycle in \(G_k\)). In the second step we prove that Z is a smallest H-force set, which will mean \(h(G_k) = |Z| = \frac{11k-7}{3}\).

1. Let \(T = \{v_j\}\), \(v_j \in V(C_M)\). We prove that in the graph \(G_k\), there is no cycle that misses exactly one vertex \(v_j \in V(C_M)\). Suppose there exists such cycle. Then the graph \(G_k - v_j\) is hamiltonian and, in this graph, \(f_i + g_i \neq 0\) holds only for \(i \in \{5, 9, k\}\); moreover,

\[f_5 + g_5 = 2k - 3,\] \(f_9 + g_9 = 1,\) \(f_k + g_k = 2.\)

Then \(0 = \sum (i-2)(f_i - g_i) = 3(f_5 - g_5) + (k-2)(f_k - g_k) + 7(f_9 - g_9) \equiv \pm 7 \pmod{3}\), a contradiction.

2. Let \(T = \{v_j\}\), \(v_j \in V(C_O) \cup V(C_I)\). We prove that in the graph \(G_k\), there is no cycle that misses exactly one vertex of \(C_O\) (similarly for \(C_I\)). Suppose that \(G_k - v_j\) is hamiltonian. In this graph we have \(f_i + g_i \neq 0\) only for \(i \in \{5, k, k+4\}\), and furthermore,

\[f_5 + g_5 = 2k - 2,\] \(f_k + g_k = 1,\) \(f_{k+4} + g_{k+4} = 1.\)

Hence \(0 = \sum (i-2)(f_i - g_i) = 3(f_5 - g_5) + (k-2)(f_k - g_k) + (k+2)(f_{k+4} - g_{k+4}) \equiv \pm 1 \pmod{3}\), a contradiction.

• 3. Let \(v_{k+1} \in T\). We prove that no cycle in the graph \(G_k\) misses the vertex \(v_{k+1}\) and some other vertex from S. Suppose to the contrary that there is a Z-cycle C of \(G_k\) with \(v_{k+1} \notin V(C)\).
  • (a) Let \(v_{3k+1}v_{4k} \in E(C)\) and let \(a_j \notin E(C)\), for all j with \(3 \le j \le 2k-1\), \(j \equiv 0 \pmod 3\). All edges of C are in this case uniquely determined, but ultimately we obtain two disjoined cycles, a contradiction.

• (b) Let \(v_{3k+1}v_{4k} \in E(C)\) and let j be the smallest integer with \(3 \leq j \leq 2k-1\), \(j \equiv 0 \pmod 3\) and \(a_j \in E(C)\). The structure of layers of 5-gons of \(G_k\) yields that all edges of C are uniquely determined. For j odd, C contains the path \(v_{3k-1}, v_{3k}, v_{4k}, v_{3k+1}, v_{k+2}, v_{k+3}, v_{k+4}, v_{3k+2}, v_{3k+3}, v_{3k+4}, v_{k+8}, \ldots, v_{3k+\frac{j-1}{2}}, v_{k+j-1}, v_{k+j}, v_{\frac{j+1}{2}}, v_{\frac{j-1}{2}}, \ldots, v_4, v_{k+7}, v_{k+6}, v_{k+5}, v_3, v_2, v_1, v_k\). Subsequently C does not contain any other \(a_j\) with \(3 \leq j \leq 2k-1\), \(j \equiv 0 \pmod 3\) and does not contain the edges \(v_{k+j}v_{k+j+1}\) (since C contains the path \(v_{k+j-1}, v_{k+j}, v_{\frac{j+1}{2}}, v_{\frac{j+1}{2}}\)) and \(v_{\frac{j+1}{2}}v_{\frac{j+3}{2}}\) as well (since C contains the path \(v_{k+j}, v_{\frac{j+1}{2}}, v_{\frac{j-1}{2}}\)). Therefore C contains the edges \(v_{k+j+3}v_{k+j+2}\) (since \(a_{j+1} = v_{k+j+3}v_{3k+\frac{j+3}{2}} \notin E(C)\)), \(v_{k+j+1}v_{k+j+2}\) (since \(v_{k+j}v_{k+j+1} \notin E(C)\)), and \(v_{k+j+2}v_{\frac{j+3}{2}}\) (since \(v_{\frac{j+1}{2}}v_{\frac{j+3}{2}} \notin E(C)\)), a contradiction (analogously for j even).
• (c) Let \(v_{3k+1}v_{4k} \notin E(C)\). Similarly as in the cases (a) and (b), there is no supposed Z-cycle in \(G_k\).
• 4. Let \(v_{3k+1}, v_{4k} \in T\) and \(v_{k+1} \notin T\) (i.e. \(v_{k+1} \in V(C)\)). Analogously to the previous case 3, the edges of C are uniquely determined and they induce two disjoined cycles, if \(a_j \notin E(C)\), for all j with \(3 \le j \le 2k-1\), \(j \equiv 0 \pmod 3\), a contradiction. Otherwise, for the smallest integer j with \(3 \le j \le 2k-1\), \(j \equiv 0 \pmod 3\) such that \(a_j \in E(C)\), the cycle C does not contain the vertex \(v_{\frac{j+3}{2}} \in Z\), if \(j \equiv 3 \pmod 6\), or the vertex \(v_{3k+\frac{j}{2}+1} \in Z\), if \(j \equiv 0 \pmod 6\), a contradiction.
• 5. Let \(v_{3k+1} \in T\) and \(v_{4k}, v_{k+1} \notin T\) (i.e. \(v_{4k}, v_{k+1} \in V(C)\)). Analogously to the previous cases 3 and 4, if \(a_j \notin E(C)\), for all j with \(3 \leq j \leq 2k-1\), \(j \equiv 0 \pmod 3\), then necessarily \(v_1v_2, v_1v_k, v_1v_{k+1} \in E(C)\), a contradiction. Otherwise, for the smallest integer j with \(3 \leq j \leq 2k-1\), \(j \equiv 0 \pmod 3\) and \(a_j \in E(C)\), the cycle C does not contain vertex \(v_{k+j+3}\) or vertex \(v_{3k-1}\) belonging to Z, a contradiction. Especially for j=3, let t with \(t \equiv 0 \pmod 3\), j < t < 2k, be the smallest integer with \(a_t \notin E(C)\). Then the cycle C does not contain vertex \(v_{\frac{t}{2}}\) (if t even) or vertex \(v_{3k+\frac{t-1}{2}}\) or vertex \(v_{k+t+3}\) (if t odd), a contradiction. If there is no such t (i.e. if all edges \(a_t\) with \(t \equiv 0 \pmod 3\), j < t < 2k, belong to E(C)) then \(W = V(G) \setminus \{v_{3k+1}\}\) and there is no cycle in \(G_k\) missing exactly one vertex, a contradiction.

Thus, we just proved that Z is an H-force set. Now, let W be a smallest H-force set in \(G_k\). We will show that \(|W| \ge |Z|\).

• 1. Let \((V(C_O) \cup V(C_I)) \subseteq W\). Without loss of generality, let \(v_{k+1} \notin W\) (otherwise, because of symmetry of \(G_k\), all vertices of \(C_M\) belong to W, thus W = V(G)). As there exists (by Lemma 8 (3)) a cycle that misses exactly two vertices \(v_{k+1}, v_j \in V(C_M)\) with \(1 \neq d_{C_M}(v_{k+1}, v_j) \equiv 1 \pmod{2}\), all these vertices \(v_j\) belong necessarily to W.
  • (a) Suppose \(v_{k+2} \notin W\). Possibly except of \(v_{k+3}\) and \(v_{3k}\), the set W contains all vertices of \(V(C_M)\) (again by Lemma 8 (3)), thus \(|W| \ge 4k 4 \ge |Z|\).
  • (b) Suppose \(v_{k+5} \notin W\). By Lemma 8 (3), for \(v_i = v_5\), the set W contains the vertices \(v_{k+2}\) and \(v_{3k}\). As there exists (by Lemma 4) a cycle that misses exactly three vertices \(v_i, v_j, v_\ell \in V(C_M)\) splitting \(C_M\) into three paths of lengths at least 4 and congruent to 4, 4 and 2 modulo 6, the set W contains all vertices \(v_{k+m} \in V(C_M)\) where \(m \not\equiv 5 \pmod{6}\), \(1 \leq m \leq 2k\), or \(m \notin \{k+1, k+3, k+7, 3k-1\}\). By repeated use of

• Lemma 4 (for \(v_i = v_{3k-1}\), \(v_j = v_3\), \(v_\ell = v_7\)), the set W contains at least one of these three vertices as well. Thus \(|W| \ge \frac{11k-7}{3} = |Z|\).
• (c) Let \(v_{k+2}, v_{3k} \in W\) and let \(v_j \notin W\) where \(2 \neq d_{C_M}(v_{k+1}, v_j) \equiv 2 \pmod 6\). Then by Lemma 4, \(v_{k+m} \in W\) for \(m \equiv 5 \pmod 6\), \(5 \leq m \leq j-k-4\) and for \(m \equiv 1 \pmod 6\), \(j-k+4 \leq m \leq 2k-3\). For each mentioned m, the vertices \(v_{k+m-2}\) and \(v_{k+m+2}\) lie on \(C_M\) at distance 4, thus, one vertex of each pair \(v_{k+m-2}, v_{k+m+2}\) must belong to W (otherwise we have two vertices from \(C_M\) at distance 4 and not belonging to W-already considered in (b)). Ultimately we have \(|W| \geq \frac{11k-4}{3} \geq |Z|\).
• (d) Let \(v_{k+2}, v_{3k}, v_{k+5}, v_{3k-3} \in W\) and let \(v_j \in W\) for \(2 \neq d_{C_M}(v_{k+1}, v_j) \equiv 2 \pmod{6}\). The vertices \(v_{k+m-2}\) and \(v_{k+m+2}\) for \(m \equiv 2 \pmod{6}\), \(9 \leq m \leq 2k-7\) lie on \(C_M\) at distance 4, thus, similarly as in the previous case, one vertex of each pair \(v_{k+m-2}, v_{k+m+2}\) must belong to W. From the same reason, one of the vertices \(v_{k+3}, v_{3k-1}\) belongs to W as well. Ultimately we have \(|W| \geq \frac{11k-1}{3} \geq |Z|\).
• 2. Let \((V(C_M) \cup V(C_I)) \subseteq W\). Without loss of generality, let \(v_1 \notin W\) (otherwise, because of symmetry of \(G_k\), all vertices of \(C_O\) belong to W, thus W = V(G)).
  • (a) Suppose \(v_j \notin W\) where \(d_{C_O}(v_1, v_j) \equiv 1 \pmod{3}\). As there exists (by Lemma 4) a cycle that misses exactly three vertices \(v_i, v_j, v_\ell \in V(C_M)\) splitting \(C_O\) into three paths of lengths congruent to 1, 1 and 0 modulo 3, the set W contains all vertices \(v_m \in V(C_O)\) where \(m \not\equiv 0 \pmod{3}\), 1 < m < j, and all vertices \(v_m \in V(C_O)\) where \(m \not\equiv 1 \pmod{3}\), j < m < k. Thus \(|W| \geq \frac{11k-4}{3} \geq |Z|\).
  • (b) Suppose that all \(v_j \in V(C_O)\) with \(d_{C_O}(v_1, v_j) \equiv 1 \pmod{3}\) belong to W. The remaining vertices of \(C_O\) are pairwise adjacent, thus, at least half of them belongs to W (otherwise we have two adjacent vertices from \(C_O\) not belonging to W already considered in (a)) and we obtain \(|W| \geq \frac{11k-1}{3} \geq |Z|\).
• 3. Let \(V(C_M) \subseteq W\) and let vertices \(v_i \in V(C_O)\) and \(v_j \in V(C_I)\) do not belong to W. Then by Lemma 8 (2) we have \(|W| \ge 4k 4 \ge |Z|\).
• 4. Let \(v_{k+1} \notin W\). Then by Lemma 8 (1), \(v_3, \ldots, v_{k-1} \in W\). Furthermore, by Lemma 8 (3), the set W contains also the vertices \(v_{k+m}\) for m even and \(4 \le m \le 2k-2\). Finally, by Lemma 5 (1), W contains the vertices \(v_{3k+m}\) for \(m \not\equiv 0 \pmod{3}\) and \(2 \le m \le k-1\) as well.
  • (a) Suppose \(v_1 \notin W\). Then using Lemma 5 (3) and Lemma 8 (1),(2),(4) we obtain \(|W| \ge 4k 4\).
  • (b) Suppose \(v_1 \in W\) and \(v_2 \notin W\). Then using Lemma 8 (1),(2) we get \(|W| \ge 4k 8\).
  • (c) Suppose \(v_{k+2} \notin W\). Then using Lemma 8 (1),(3) we obtain \(|W| \ge 4k 8\).
  • Due to symmetry of \(G_k\), the vertices \(v_k \in V(C_O)\) and \(v_{3k} \in V(C_M)\) belong to W as well, i.e. \(V(C_O) \subseteq W\).
  • (d) Suppose W does not contain a vertex \(v_j \in V(C_I)\). Then by Lemma 5 (1), all vertices \(v_\ell \in C_M\) with \(2 \neq d(v_j, v_\ell) \not\equiv 1 \pmod{3}\) belong to W. The remaining vertices (i.e. \(\{v_{3k+m}: m \equiv 0 \pmod{3}, 2 \leq m \leq k-1\} \cup \{v_{3k+1}, v_{4k}\} \setminus \{v_j\} \subseteq V(C_I)\) and \(\{v_{k+m}: m \equiv 2j-6k-1+6t \pmod{2k}, 0 \leq t \leq \frac{2k+2}{6}\} \setminus \{v_{k+1}\} \subseteq V(C_M)\)) form pairs in the distance 5. By Lemma 5 (1), one vertex of each pair must belong to W, thus \(|W| \geq \frac{11k-7}{3} \geq |Z|\).

We showed, that the smallest H-force set of G^k contains at least ¹¹k−⁷ 3 vertices.

Case (i) For k = 3 it is easy to check that h(G3) = 9, the set V (G3) \ {v4, v6, v8} is a smallest H-force set in G3.

Case (iii) Let k ≡ 0 (mod 3), k ≥ 6. Let W be an arbitrary H-force set in Gk.

In Gk, there exists a cycle that misses exactly one vertex of C^O (by Lemma 6 (1)). Hence, all vertices of C^I and C^O belong to W.

Without loss of generality, let vk+1 ∈/ W. We already know, that there exist cycles in G^k missing exactly two vertices

• (a) vk+1 and v^j ∈ V (CM) with d^CM (vk+1, v^j ) ≡ 1 (mod 2) (by Lemma 8 (3) and 6 (2)), or
• (b) vk+1 and v^j ∈ V (CM) with 2 6= d^CM (vk+1, v^j ) ≡ ±2 (mod 6) (by Lemma 3).

Hence, for S = {vk+1}∪{v^j : d^CM (vk+1, v^j ) ≡ 0 (mod 6)} we just found out that V (Gk)\S ⊆ W. Now we prove that V (Gk) \ S is an H-force set.

In Gk, there is no cycle that misses exactly one vertex vk+1. Assume to the contrary that the graph G^k − vk+1 is hamiltonian. We have fⁱ + gⁱ 6= 0 only for i ∈ {5, 9, k}, moreover

\[f_5 + g_5 = 2k - 3,\] \(f_9 + g_9 = 1,\) \(f_k + g_k = 2.\)

If fk−g^k = 0, then 0 = P(i−2)(fi−gi) = 3(f5−g5)+(k−2)(fk−gk)+7(f9−g9) ≡ ±7 (mod 3), a contradiction.

Otherwise f^k − g^k = ±2 and 0 = P(i − 2)(fⁱ − gi) = 3(f⁵ − g5) ± 2(k − 2) ± 7. Thus ±2(k − 2) ± 7 ≡ 0 (mod 3) and the equality from the Grinberg's theorem is fulfilled only if both k-gons with 9-gon appear in the same region determined by a hamiltonian cycle of G^k − vk+1. On the other hand, edges v1v2, vkv¹ belong to any hamiltonian cycle and obviously separate one k-gon and the 9-gon, a contradiction.

Similarly as in the case (v), there is no cycle in G^k missing vertex vk+1 and some other vertices from S.

Case (iv) Let k ≡ 1 (mod 3), k ≥ 4. Let W be an arbitrary H-force set in Gk.

In Gk, there exists a cycle that misses exactly one vertex of C^M (by Lemma 7 (1)). Hence, all vertices of C^M belong to W.

Without loss of generality, let v¹ ∈/ W. In G^k there exist cycles missing exactly two vertices

• (a) v¹ and v^j ∈ V (C^I ) (by Lemma 7 (2) and 8 (2)), or
• (b) v¹ and v^j ∈ V (CO) with d^CO (v1, v^j ) 6≡ 2 (mod 3) (by Lemma 7 (3)).

Hence, for S = {v1}∪{v^j : d^CO (v1, v^j ) ≡ 2 (mod 3)} we just found out that V (Gk)\S ⊆ W. If there is some v^j ∈ S \ {v1} that does not belong to W, then, according to previous observations, all other vertices of S \ {v1} belong necessarily to W because their distance from v^j is congruent to 0 or 1 modulo 3.

In Gk, there is no cycle that misses exactly one vertex v¹ ∈ V (CO). Assume to the contrary that the graph G^k − v¹ is hamiltonian. We have fⁱ + gⁱ 6= 0 only for i ∈ {5, k, k + 4}, moreover

\[f_5 + g_5 = 2k - 2,\] \(f_k + g_k = 1,\) \(f_{k+4} + g_{k+4} = 1.\)

then \[0 = \sum (i-2)(f_i - g_i) = 3(f_5 - g_5) + (k-2)(f_k - g_k) + (k+2)(f_{k+4} - g_{k+4}) \equiv \pm (k-2) \equiv \pm 1 \pmod{3}\], a contradiction.

Moreover, there is no cycle that misses exactly the vertices v¹ and v3, because v² is a pendant vertex in G^k − v¹ − v3.

Hence, the set V (Gk) \ {v1, v3} is a smallest H-force set. ✷

Acknowledgement

This work was supported by Slovak Grant VEGA 1/0652/12.

References

• [1] G. Chartrand, S.F. Kapoor, D.R. Lick, n-hamiltonian graphs, J. Combin. Theory 9 (1970), 308-312.
• [2] P. Erdos, V. Chv ¨ atal, A note on hamiltonian circuits, ´ Discrete Math. 2 (1972), 111-113.
• [3] R. Diestel, Graph Theory, Springer, 2000.
• [4] I. Fabrici, E. Hexel, S. Jendrol', On vertices enforcing a hamiltonian cycle, Discuss. Math. Graph Theory 33 (2013), 71–89.
• [5] F. Goring, J. Harant, Hamiltonian cycles through prescribed edges of at least 4-connected ¨ maximal planar graphs, Discrete Math. 310 (2010), 1491–1494.
• [6] E. Grinberg, Plane homogeneous graphs of degree 3 without hamiltonian circuits, Latvian Math. Yearbook (1968), 51–58 (in Russian).
• [7] D.A. Nelson, Hamiltonian Graphs, Master thesis, Vanderbilt University, 1973.
• [8] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997), 341-345.