Michael Tapfuma Muzheve

Department of Mathematics, Texas A&M University - Kingsville, Kingsville, TX 78363, USA.

michael.muzheve@tamuk.edu

We study decompositions and packings in truncated triangulations G^T △ obtained from simple connected plane graphs G with minimum degree two. We show G^T △ is a 3-connected cubic planar graph with at least 2|E(G)| ² − 2|E(G)| + 1 perfect matchings, a Λ-factor, and can be decomposed into a union of C6's and K2's if G is bipartite. Additionally, we show that G^T △ is hamiltonian if G is bipartite with a dominating path P satisfying, for any e = xy /∈ E(P) exactly one of x and y is in V (P). We also prove a result giving necessary and sufficient conditions for the hamiltonicity of G^T △. Additional results include showing that a truncated triangulation of a cubic plane bipartite graph G has a hamiltonian cycle that separates specific faces of G^T △ if and only if the triangulation G△ has an A-trail.

Keywords: truncation, triangulation of the plane, cubic, perfect matching, hamiltonian, A-trail, dominating path Mathematics Subject Classification : 05C70, 05C45

DOI: 10.5614/ejgta.2026.14.1.15

1. Introduction

We use graph notation and terminology from West [14] and study properties of cubic planar graphs obtained by operating on simple connected plane graphs with minimum degree two. These derived graphs, which we call truncated triangulations and denote by G^T △ are cubic, planar, and 3 connected. We examine decompositions and packings in G^T △, and demonstrate that some graphs

Received: 30 October 2023, Revised: 11 February 2026, Accepted: 1 March 2026.

G^T △ can be decomposed into a union of cycles of length six and K2's. We also show that all truncated triangulations G^T △ contain multiple perfect matchings and a Λ-factor.

Additionally, we study the hamiltonicity of the graphs G^T △ and prove a result showing that G^T △ is hamiltonian if and only if the graph G△ obtained in an intermediate step of constructing G^T △ contains a spanning non-crossing trail T with certain properties. We also show G^T △ is hamiltonian if G is bipartite and contains a dominating path P satisfying the condition that for any e = xy /∈ E(P) exactly one of the vertices x and y is in V (P). Based on these results, we identify classes of graphs for which G^T △ is hamiltonian. Identifying the subgraphs T of G△ and P of G is in line with work done by other researchers who in trying to decide hamiltonicity in a graph derived from G, identified structures in G or other related graphs that would help answer the hamiltonicity question. Examples of this approach include showing that if a plane cubic graph G has an edgedominating subgraph with certain properties, then its vertex envelope G^∗ V is hamiltonian [4], and finding a dominating cycle in a graph G to show the line graph of G is hamiltonian [7]. Additional examples are, showing that if a plane graph G has an independent set of vertices I such that G − I is a tree, then the vertex envelope of G is hamiltonian [10], that a graph G is hamiltonian if its reduced graph R(G) is hamiltonian [13], and considering the independence of some covering set S of a graph G, and the properties of ⟨S⟩ to decide if the maximum degree minimum covering graph G^S is hamiltonian[11].

Research on truncated graphs abounds, examples which include a study on truncated cage graphs [2] and a study of generalized truncations of complete graphs [12].The current research differs from what is already in the literature in that the graphs that are being truncated are triangulations of the plane that are not necessarily regular graphs. The triangulations of the plane are obtained from smaller plane connected graphs.

The study of decompositions, packings, and hamiltonian cycles are motivated in part by Gallai's conjecture and Bannet's conjecture, both of which are stated below. Among other goals, this study aims to build on work done by other researchers, see for example [1], who studied path and acyclic path decomposition numbers, obtaining bounds on the parameters and characterizing graphs that attain those bounds.

Conjecture 1. Gallai's conjecture[9]: If G is a connected graph on n vertices, then G can be decomposed into ⌈n/2⌉ paths.

Conjecture 2. Barnette's conjecture[5]: Every planar, cubic, bipartite, 3-connected graph is hamiltonian.

The operation studied in this article bears similarities with the vertex envelope [4] or leapfrog operation and the quadrupling (chamfering) operation [6], which are well known in physical chemistry and widely used in the study of fullerenes and tubelenes. For example, when applied to a connected cubic plane simple graph G, the resulting graph is also cubic and planar for each of the three operations. In addition, for each face F of G, there is a face of derived graph with the same length as F. A discussion of other similarities of truncated triangulations and the quadrupling operation is included later in the article. What distinguishes the truncated triangulations from other operations are the bigger orders and sizes of the graphs G^T △ relative to the graph G. For example, the order and size of G^T △ are each three times those of the vertex envelope of a graph G. Another unique

Figure 1. Operation applied to C³

feature of G^T △ is that there is a face of G^T △ corresponding to each vertex and to each face of G, and there are two faces corresponding to each edge of G. Compare that to the vertex envelope and leapfrog operation for which faces corresponding to only vertices and faces of the original graph G are present.

2. Definitions and Preliminary results

A graph G is planar if it has a drawing without crossings. A plane graph is a planar embedding of G. Throughout this article G is a simple connected plane graph with minimum degree two. The faces of a plane graph are the maximal regions of the plane containing no point used in the embedding. The unbounded face of a plane graph is called the outer face. The boundary of a face F of a plane graph is a closed walk around the edges of the face and the number of edges in the boundary is the length l(F) of the face.

Let G be a simple connected plane graph with minimum degree two. We form a new graph by inserting a new vertex v^F inside each face F of G and joining v^F to the vertices on the boundary of F so that planarity is preserved. Note that if e = uv is a bridge of G on the boundary of face a F, then F is treated as two faces locally at u and v. The new graph, which we denote by G△ is a triangulation of the plane with vertex set V (G△) = V (G) ∪ {v^F |F is a f ace of G}, and edge set E(G△) = E(G) ∪ {(v, v^F )|v ∈ V (G) is on the boundary of F}. If v ^∗ ∈ V (G△), then the degree of v ∗ is d^G△ (v ∗ ) = 2dG(v), if v ∗ corresponds to a vertex v of G, otherwise d^G△ (v ∗ ) = d^G△ (v^F ) = l(F), where F is a face of G.

We then form another new graph by truncating every vertex of G△ (See Figure 1 for an example). We refer to the graphs as truncated triangulations and denote them by G^T △. Note that truncating essentially replaces each vertex v ^∗ of G△ with a face of size d^G△ (v ∗ ) while maintaining the adjacencies induced by adjacencies in G△ between vertices of G and vertices v^F .

Based on the construction, the faces of G^T △ are of three types.

• 1. Faces F^v corresponding to each vertex v of G with length 2dG(v). We note that each face F^v is insulated by 2dG(v) hexagonal faces.
• 2. Faces F ′ corresponding to each face F of G having length l(F). Each face F ′ is insulated by l(F) hexagonal faces.

3. Hexagonal faces corresponding to edges of G. For each edge e of G, there are two such faces of G^T △ which are adjacent and sharing the edge e ′ of G^T △ that corresponds to e. We denote the faces by F^e1 and F^e2 . If e and f are adjacent edges of G, then either F^e1 or F^e2 is adjacent to F^f1 or F^f2 . Therefore, any such face F^ei is adjacent to three other faces of the same type.

We refer to these three types of faces as faces of type Fv, type F ′ , and type F^ei , and note that each face of type F^v and each face of type F ′ is insulated by faces of type F^ei only.

Proposition 2.1. G^T △ is a cubic planar graph of order 6|E(G)| and size 9|E(G)|. If G is r-regular, the order of G^T △ is 3r|V (G)|.

Proof. Planarity and being cubic follows immediately from the construction of G^T △. We count the vertices of G^T △ by counting the vertices on all faces of type F^v and their neighbors lying on faces of type F ′ . By construction, the faces of type F^v together with the faces of type F ′ form a 2-factor of G^T △. For each vertex v ∈ V (G), there are 2dG(v) vertices of G^T △ on the boundary of Fv. Every vertex on the boundary of a face of type F ′ is connected to exactly one vertex on the boundary of some face of type Fv. Therefore, there are 3dG(v) vertices of G^T △ associated with each v ∈ V (G). Hence the order of G^T △ is

\[3\sum_{v\in V(G)} d_G(v) = 3(2|E(G)| = 6|E(G)|\]

If G is r-regular, then 2|E(G)| = P v∈V (G) dG(v) = r|V (G)|. Therefore, the order of G^T △ is

\[6|E(G)| = 3(2|E(G)|) = 3(r|V(G)|) = 3r|V(G)|\]

The number of edges of G^T △ is equal to (the number of edges in each face type Fv) + (the number edges in each face of type F ′ ) + (the number of edges corresponding to edges of G and connecting vertices on boundaries of faces of type Fv) + (the number of edges connecting vertices on boundaries of faces of type F^v to vertices on boundaries of face of type F ′ ). Therefore, the size of G^T △ is

\[|E(G_{T\Delta})| = 2 \sum_{v \in V(G)} d_G(v) + 2|E(G)| + |E(G)| + \sum_{v \in V(G)} d_G(v)\] \[= 2 \sum_{v \in V(G)} d_G(v) + \sum_{v \in V(G)} d_G(v) + \frac{1}{2} \sum_{v \in V(G)} d_G(v) + \sum_{v \in V(G)} d_G(v)\] \[= \frac{9}{2} \sum_{v \in V(G)} d_G(v)\] \[= \frac{9}{2} (2|E(G)|)\] \[= 9|E(G)|\]

Proposition 2.2. The three smallest orders of G^T △ are 18, 24 , and 30. Additionally, there is exactly one such graph of order 18, one of order 24, and two of order 30, up to isomorphism.

Proof. Since \(G_{T\triangle}\) is defined only for simple connected plane graphs with minimum degree two, the smallest such graph G is the cycle on three vertices, \(C_3\). By Theorem 2.1, the order of \((C_3)_{T\triangle}\) is \(6|E(C_3)|=6(3)=18\). Order 24 follows from applying the operation on the only suitable graph \(C_4\). For order 30, it can be easily verified that the only suitable graphs with five edges are \(C_5\) and the graph obtained from \(C_4\) by connecting any two nonadjacent vertices.

Proposition 2.3. Let G be a simple connected plane graph with minimum degree two. Then \(G_{T\triangle}\) has 3|E(G)|+2 faces and at least 2|E(G)| faces of length 6. If G is cubic, then \(G_{T\triangle}\) has at least \(4|V(G)|=\frac{8}{3}|E(G)|\) faces of length 6.

Proof. The first part of the theorem follows easily from Euler's formula and Proposition 2.1. Since \(G_{T_{\triangle}}\) is planar, the number of faces of \(G_{T_{\triangle}}\) equals \(|E(G_{T_{\triangle}})| - |V(G_{T_{\triangle}})| + 2 = 9|E(G)| - 6|E(G)| + 2 = 3|E(G)| + 2\).

As discussed earlier, for each vertex v of G, there is a face \(F_v\) of \(G_{T\Delta}\) with length \(2d_G(v)\), and for each \(e \in E(G)\) there are two hexagonal faces \(F_{e_1}\) and \(F_{e_2}\) of \(G_{T\Delta}\). Also, if G contains a hexagonal face F, then there is a hexagonal face F' of \(G_{T\Delta}\) corresponding to F. Let \(E_1 = \{F_v | v \in V(G)\}\), \(E_2 = \{F_{e_i} | e \in E(G) \text{ with } i = 1 \text{ or } 2\}\), and \(E_3 = \{F' | F \text{ is a face of } G \text{ of length } 6\}\). Note that \(E_1, E_2\), and \(E_3\) are pairwise disjoint. Then the number of hexagonal faces of \(G_{T\Delta}\) is \(|E_1 \cup E_2 \cup E_3| = |E_1| + |E_2| + |E_3| \ge |E_2| = 2|E(G)|\). If G is cubic, each face \(F_v\) has length six for every \(v \in V(G)\). Therefore \(|E_1 \cup E_2 \cup E_3| = |E_1| + |E_2| + |E_3| \ge |E_1| + |E_2| = |V(G)| + 2|E(G)| = |V(G) + 3|V(G)| = 4|V(G)|\), which is also equal to \(\frac{8}{3}|E(G)|\sin 2|E(G)| = 3|V(G)|\) when G is cubic.

Proposition 2.4. G is bipartite if and only if \(G_{T\Delta}\) is bipartite.

Proof. If G is bipartite, then all its faces have even length and the face sizes are retained in \(G_{T\triangle}\). The rest of the faces of \(G_{T\triangle}\) are either of type \(F_{e_i}\) having length six or they are of type \(F_v\) with length \(2d_G(v)\). Therefore \(G_{T\triangle}\) is bipartite since all its faces are of even length.

Conversely, if \(G_{T\triangle}\) is bipartite, then all its faces have even length. In particular, all faces F' corresponding to faces of G have even length. Therefore G is bipartite.

Theorem 2.1. Let G be a simple connected plane graph with minimum degree two. Then \(G_{T_{\triangle}}\) is 3-connected.

Proof. \(G_{\triangle}\), which is a triangulation of the plane is connected by definition. \(G_{T_{\triangle}}\) is also connected by definition since truncating each vertex v of \(G_{\triangle}\) does not disconnect the graph. Since every edge of \(G_{T_{\triangle}}\) is in some cycle, \(G_{T_{\triangle}}\) is 2-edge connected. It follows that \(G_{T_{\triangle}}\) is 2-connected, otherwise \(G_{T_{\triangle}}\) has a cut-vertex with minimum degree four, a contradiction to the fact that \(G_{T_{\triangle}}\) is cubic.

Now suppose \(G_{T\triangle}\) has a 2-vertex cut \(\{v_1, v_2\}\). Since \(G_{T\triangle}\) is cubic, there are two vertices \(w_1\) and \(w_2\) such that \(e_1 = v_1w_1\) and \(e_2 = v_2w_2\) is a 2-edge cut of \(G_{T\triangle}\) (see Figure 2). The faces labeled (1) and (2) can be of type \(F_v\), F' or \(F_{ei}\). We investigate if having a scenario represented in Figure 2 is possible by looking at different pairs of face types for (1) and (2).

Figure 2. Exploring if a 2-vertex cut is possible in GT△

• 1. First we note that a type F^v and a type F^ei have at most one edge in common. So, if (1) is a type F^v (F^ei ), then (2) cannot be a type F^ei (Fv) face.
• 2. The other possibility is having (1) as a type F^v (F ′ ) face and (2) as a type F ′ (Fv) face. This would result in F^v and F ′ having two edges in common, which is also not possible since any two such faces have no edge in common.
• 3. Any two faces of type F^v have no edge in common. Therefore if (1) is face Fv, then (2) cannot be face F^w and vice versa.
• 4. Let (1) be a face of type F^ei . Then (2) cannot be of type F^v as discussed above. Face (2) can also not be of type F^ei , otherwise we end up with two faces of type F^ei with at least two edges in common, which is not possible since any two such faces have at most one edge in common. The only other possibility is that (2) is a face of type F ′ . This is also not possible since a type F^ei face and a type F ′ face have at most one edge in common. A similar argument can be used to show that if (2) is of type F^ei , then (1) cannot be of type Fv, F^ei or F ′ .
• 5. As seen earlier if (1) or (2) is of type F ′ , then the other face cannot be of type F^v or F^ei . The only other possibility is that the second face is of type F ′ , but this is also not possible since any two faces of type F ′ have no edge in common.

The cases discussed above exhaust all the possible arrangements of faces of G^T △ around the edges e¹ = v1w¹ and e² = v2w2. Therefore G^T △ does not have 2-vertex cut. Hence G^T △ is 3-connected.

A fullerene graph is a 3-connected 3-regular planar graph containing only pentagonal and hexagonal faces. The following result follows easily from Theorem 2.1 and the properties of G^T △ discussed so far.

Proposition 2.5. If G is a fullerene graph, then G^T △ is also a fullerene graph.

3. Decompositions and Packings in G^T △

A collection D of edge-disjoint subgraphs H1, H2, ..., H^k of a graph G is a decomposition of G if every edged of G belongs to exactly one Hⁱ [1].

Proposition 3.1. Let G be a simple connected plane graph with minimum degree two. Then G^T △ can be decomposed into a union of cycles and K2's.

Figure 3. Identifying the cycles of length six for the decomposition

Proof. Let C be the collection of all cycles induced by edges on the boundaries of faces of type F^v or type F ′ . If we delete all the edges of C, then each component of the resultant graph K is a K2. Hence C ∪ K is the required decomposition of G^T △.

Proposition 3.2. Let G be a simple connected bipartite plane graph with minimum degree two. Then G^T △ can be decomposed into a union of cycles of length six and K2's in at least two ways.

Proof. As seen earlier, for each edge e of G, there are two adjacent faces F^e1 and F^e2 of G^T △ each with length six. We simulate the process of identifying the cycles of length in the decomposition of G^T △ by tripling each edge of G to form a graph G^d (see Figure 3).We embed the edges of G^d so that each edge e ∈ E(G) lines between the two new edges. In Gd, there are two digons corresponding to each edge e of G, and by construction, they also correspond to F^e1 and F^e2 of G^T △. For each face of F of G, there are 2l(F) digons in Gd, half of them inside F and the other half outside of F. Starting with any face F, color any digon and then go around F and coloring digons that are alternately in and outside of F. The coloring process is then extended to all digons, starting with faces that are adjacent to F in G. The set of colored digons will correspond to a set of hexagonal faces that forms a 2-factor Q of G^T △, and the edges not in Q form a perfect match K of G^T △. Thus Q ∪ K is the required union of cycles of length six and K2's. The uncolored set of digons will induce a second decomposition of G^T △.

Consider graphs G and H. A subgraph of G with components isomorphic to H is called an H-packing of G. If V (P) = V (G) for some H-packing P, then P is called an H-factor [8]. We denote the path on three vertices by Λ [8]. We note that if H ∼= K2, then an H-factor of G is a perfect matching of G.

Theorem 3.1. The graph G^T △ has a Λ-factor with |V (G^T △)|/3 components.

Proof. Since each face of type F^v has even size in G^T △, we form a perfect matching M of G^T △ by choosing a set of disjoint edges in each face Fv. We note that for each edge e ′ = uv in M, there is a unique edge f ′ of G^T △ connecting either u or v with a vertex w on the boundary of some face of type F ′ in G^T △. The subgraph of G^T △ induced by the edges in M and all such edges f ′ forms a Λ-factor of G^T △ in which each three-vertex component is induced by {e ′ , f′}. Every vertex of G^T △ belongs to precisely one component of the Λ-factor, and the components are disjoint by construction. Hence the number of components is |V (G^T △)|/3 as required.

Theorem 3.2. If G is bipartite, then \(G_{T\Delta}\) has a \(C_6\)-packing with |E(G)| components.

Proof. If G be a connected bipartite planar graph with minimum degree two, then \(G_{T\Delta}\) can be decomposed into a union of cycles of length six and \(K_2\)'s by Proposition 3.2. By construction, the cycles of length six form a 2-factor \(\mathcal{Q}\) of \(G_{T\Delta}\). Since for each edge e of G, exactly one of \(F_{e_1}\) and \(F_{e_2}\) is chosen for inclusion in the 2-factor \(\mathcal{Q}\), there are |E(G)| component of the 2-factor.

Theorem 3.3. Let G be a simple connected plane graph with minimum degree two. Then \(G_{T\triangle}\) has at least 2|E(G)|(|E(G)|-1)+1 perfect matchings.

If n and m are the order and size of \(G_{T\triangle}\) respectively, then the number of perfect matching of \(G_{T\triangle}\) is at least \(\frac{n^2}{18} - \frac{1}{3}n + 1 = \frac{2}{81}m^2 - \frac{2}{9}m + 1\).

Proof. Denote the set of edges of \(G_{T\Delta}\) corresponding to edges of G by E' and let E'' be the set of all edges of \(G_{T\Delta}\) connecting vertices on the boundary of faces of type \(F_v\) to vertices on faces of type F'. Then \(E' \cup E''\) is a perfect matching of \(G_{T\Delta}\). As discussed earlier, for each edge e of G there are two hexagonal faces of \(G_{T\Delta}\) which we denote by \(F_{e_1}\) and \(F_{e_2}\). Therefore, there are \(|2E(G)| = 2m_G\) such faces, where \(m_G = |E(G)|\). Three edges of each face \(F_{e_i}\) are in the perfect matching \(E' \cup E''\). Suppose \(e_1, e_2, e_3, e_4, e_5\), and \(e_6\) are the consecutive edges on the boundary of some face \(F_{e_i}\) and the edges \(e_1, e_3\), and \(e_5\) are in the matching \(E' \cup E''\). We can form another matching of \(G_{T\Delta}\) by replacing \(e_1, e_3\), and \(e_5\) with \(e_2, e_4\), and \(e_6\). If we do this all \(2m_G\) such faces, one at a time we get an additional \(2m_G\) perfect matchings of \(G_{T\Delta}\). Instead of switching out the edges \(e_1, e_2, e_3, e_4, e_5\), and \(e_6\) in one face at a time, we can do that in two faces at a time. Let \(F_{e_k}\)be a face of \(G_{T\Delta}\). Then by construction of \(G_{T\Delta}\), \(F_{e_k}\) is adjacent to three other faces of type \(F_{e_i}\). Therefore, there are \(2m_G - 3 - 1 = 2m_G - 4\) faces of type \(F_{e_i}\) that are nonadjacent to \(F_{e_k}\), where 3 is for the faces adjacent to \(F_{e_k}\) and 1 is for the face \(F_{e_k}\) itself. Since there are \(2m_G\) faces of type \(F_{e_i}\), there are \(2m_G(2m_G-4)\) pairs of nonadjacent faces in which we can simultaneously switch out the edges to get \((2m_G(2m_G-4)) \div 2 = 2m_G^2 - 4m_G\) additional perfect matchings of \(G_{T\Delta}\). Therefore, the number of perfect matchings of \(G_{T\triangle}\) is at least

\[1 + 2m_G + 2m_G^2 - 4m_G = 2m_G^2 - 2m_G + 1\]\[= 2m_G(m_G - 1) + 1\]

Since \(2m_G = \sum_{v \in V(G)} d_G(v)\) and the order of \(G_{T \triangle}\) is \(n = 3 \times \sum_{v \in V(G)} d_G(v)\), the number of perfect

matchings is at least

\[2m_G^2 - 2m_G + 1 = 2\left(\frac{1}{2}\sum_{v \in V(G)} d_G(v)\right)^2 - 2\left(\frac{1}{2}\sum_{v \in V(G)} d_G(v)\right) + 1\] \[= \frac{1}{2}\left(\sum_{v \in V(G)} d_G(v)\right)^2 - \sum_{v \in V(G)} d_G(v) + 1\] \[= \frac{1}{2}\left(\frac{1}{3}n\right)^2 - \frac{1}{3}n + 1\] \[= \frac{n^2}{18} - \frac{1}{3}n + 1.\]

Since \(G_{T\triangle}\) is cubic, 2m=3n. So \(n=\frac{2}{3}m\). Substituting for n in \(\frac{n^2}{18}-\frac{1}{3}n+1\), we get

\[\frac{n^2}{18} - \frac{1}{3}n + 1 = \frac{(\frac{2}{3}m)^2}{18} - \frac{1}{3}\left(\frac{2}{3}m\right) + 1\]\[= \frac{4m^2}{9 \cdot 18} - \frac{2}{9}m + 1\]\[= \frac{2m^2}{81} - \frac{2}{9}m + 1\]

We note in passing that if the graph G in Theorem 3.3 is bipartite, then additional perfect matchings of \(G_{T\triangle}\) can be formed using only the edges of \(G_{T\triangle}\) on the boundaries of faces of type \(F_v\) and F'.

4. Hamiltonian Cycles in \(G_{T\triangle}\)

In this section we investigate the hamiltonicity of truncated triangulations. Since \(G_{T\triangle}\) 3-connected by Theorem 2.1, Barnette's conjecture would imply the truncated triangulation of any simple connected bipartite plane graph with minimum degree two is hamiltonian.

We begin this section by proving a result giving necessary and sufficient conditions for a graph G to be hamiltonian. Let \(S = \{S_1, S_2, ..., S_k\}, k \geq 1\) be a finite collection of (not necessarily distinct) sets \(S_i\), i = 1, ..., k. The intersection graph I(S) is defined by V(I(S)) = S and \(E(I(S)) = \{S_i S_j | S_i, S_j \in S \text{ and } S_i \cap S_j \neq \emptyset\}\)

Theorem 4.1. Let G be a graph. The G contains a hamiltonian cycle H if and only if there is a set \(Q = \{C_1, ..., C_n\}\) of cycles of G, with \(\bigcup_{i=1}^n V(C_i) = V(G)\) and

• 1. any two distinct cycles in Q have at most one edge in common.
• 2. I(Q) is a tree.

Furthermore, such an H consists of precisely those edges that belong to exactly one of the cycles C1, ..., Cn.

Proof. Suppose G has a hamiltonian cycle H. Then C¹ = H satisfies the properties stated above. Conversely, if Q = {C1}, then C¹ is a hamiltonian cycle of G. So, suppose |Q| > 1. Then I(S) has end vertex which we denote by c1. Number the cycles so that c¹ corresponds to C1, and let Q¹ = Q − {C1}. We take the cycle generated by Q1, break is at the edge it shares with C1, affixing C1, and eliminating the common edge. The result is a constructed hamiltonian cycle of G.

Theorem 4.2. Let G be a cubic plane bipartite graph. Then G^T △ has a hamiltonian cycle that separates all faces of type F^v and all faces of type F ′ if and only if G△ has an A-trail.

Proof. Let H be a hamiltonian cycle of G^T △ that separates all faces of type F^v and all faces of type F ′ . After marking all the edges on H in G^T △, we form G△ by shrinking each face of type F^v and type F ′ into a vertex, maintaining adjacencies with the rest of vertices of G^T △. Since H separates all faces of type F^v and F ′ , this operation transforms H into a eulerian trail T of G△ with the transitions of T at each vertex made of edges that are consecutive in the clockwise arrangement around each vertex. Therefore T is an A-trail of G△.

Let T be an A-trail of G△. If we truncate each vertex of G△ to form G^T △, the edges of G^T △ corresponding to edges of T form a perfect match of G^T △. Let e ′ 1 and e ′ ² be two edges of G^T △ corresponding to a transition (e1, e2) of T. For each such pair, we form H in G^T △ by including all pairs e ′ 1 and e ′ 2 and the edge f to which both e ′ 1 and e ′ 2 adjacent on a face of type F^v or F ′ . The resulting graph H is a connected, 2-regular graph, spanning subgraph of G^T △ that separates all faces of type F^v and type F ′ as required. Therefore, the result holds.

Theorem 4.3. Let G be a plane cubic graph. Then G^T △ is hamiltonian if and only if G△ contains a non-crossing closed trail T with the following properties.

• 1. V (T) = V (G△).
• 2. deg^T (v) = deg^G△ (v) if and only if H splits the face F^v of G^T △.
• 3. If e¹ ∈ (E(G△) − E(T)) is incident with v ∈ V (G△), then there are two edges e and f such that e¹ lies between e and f is a clockwise arrangement of the edges incident with v induced by plane embedding of the graph. Also, either (e, f) or (f, e) is a transition of T at v. In fact, we can have clockwise arrangement e, e1, e2, ..., en, f with e1, e2, ..., eⁿ not in T and either (e, f) or (f, e) is a transition of T.

Proof. Let G be a plane cubic graph and assume G^T △ has a hamiltonian cycle H, and mark the edges of H in G^T △. Maintaining adjacencies, we shrink all faces of type F^v or type F ′ into vertices to get G△. If we let T be the subgraph of G△ induced by edges of H in G△, then T spans G△. Since for any face of type F^v or F ′ the vertices on the boundary of F^v and F ′ are either consecutive in H or they are split into two or more subsets of consecutive vertices depending on how H passes through the vertices, every vertex of G△ has even degree of at least two in T. Therefore T is a eulerian subgraph of G△ and the transitions of T are non-crossing due to planarity and H being a

Figure 4. Extending trail T of \(G_{\triangle}\) to hamiltonian cycle of \(G_{T_{\triangle}}\)

hamiltonian cycle.

We now assume \(G_{\triangle}\) contains a non-crossing trail T with the listed properties. Figure 4 shows how to extend T into a hamiltonian cycle H' of \(G_{T\triangle}\) based on the transitions of T at each vertex of \(G_{\triangle}\). Figure 4(a) is a situation where only one transition exists at a vertex v of \(G_{\triangle}\) and how all but one edge of the edges on the face corresponding to v are in H' and consecutive in H'. Figure 4(b) shows how we obtain H' when each edge incident with v belongs to some transition of T. In this case H' splits the face \(F_v\) in \(G_{T\triangle}\). Figure 4(c) illustrates how H' is obtained when we have edges incident with v that are not part of any transition of T, and therefore lie between two edges of the same transition in the clockwise arrangement of the edges incident with v.

Corollary 4.1. If \(G_{\triangle}\) has a hamiltonian cycle H such that at each vertex v the edges consecutive in H are adjacent in the cyclic ordering around v, then \(G_{T_{\triangle}}\) is hamiltonian.

Corollary 4.2. Let G be the cycle graph \(C_n\). Then \(G_{T_{\triangle}}\) is hamiltonian.

Proof. We prove the result by showing that \((C_n)_{\triangle}\) contains a non-crossing trail T as described in Theorem 4.3. Let \(C_n\) be a cycle of length n and let \(v_1, v_2, ..., v_n\) be vertices of \(C_n\) in their clockwise ordering around a planar embedding of \(C_n\). Let \(e_i\) be the edges of \(C_n\) where i=1,2,...,n and \(e_i=v_iv_{i+1}\). We label the vertex of \((C_n)_{\triangle}\) corresponding to the interior face of \(C_n\) with \(v_F\) and the one corresponding to the outer face with \(v_0\). We also label the edge connecting \(v_F\) to \(v_i\) with \(f_i\) and the edges connecting \(v_0\) to \(v_i\) with \(f_i'\). We let \(T=v_F, f_2, v_2, e_1, v_1, f_1', v_0, f_2', v_2, e_2, v_3, f_3, v_F\) for n=3 and \(T=v_F, f_2, v_2, e_1, v_1, f_1', v_0, f_2', v_2, e_2, v_3, f_3, v_F, f_4, v_4, e_4, v_5, f_5, v_F, ..., f_n, v_n, e_n, v_{n+1}, f_{n+1}, v_F\) for even numbers \(n \geq 4\), with the subscripts taken modulo n. For odd numbers \(n \geq 5\),

we let \[T = v_F\], \(f_2\), \(v_2\), \(e_1\), \(v_1\), \(f'_1\), \(v_0\), \(f'_2\), \(v_2\), \(e_2\), \(v_3\), \(f_3\), \(v_F\), \(f_4\) \(v_4\), \(e_4\), \(v_5\), \(f_5\), \(v_F\), ..., \(f_{n-1}\), \(v_{n-1}\), \(e_{n-1}\), \(v_n\), \(f_n\), \(v_F\).

It is easy to check that the trail T has properties listed in Theorem 4.3 by construction. Therefore \((C_n)_{T\triangle}\) is hamiltonian.

Theorem 4.4. Let G be a plane cubic bipartite graph with minimum degree two. If G contains a dominating path P such that for any edge e = xy of G not in E(P) exactly one of x and y is in V(P), then \(G_{T_{\triangle}}\) is hamiltonian.

Proof. We know by Proposition 3.2 that G can be decomposed into a set \(S = \{C_{e_i} | e_i \in E(G)\}\) of cycles of length six and \(K_2\)'s. We form a collection of cycles \(Q = S \cup \{F_v^* | v \in V(P)\}\) in \(G_{T_{\triangle}}\), where \(F_v^*\) is a cycle induced by the face \(F_v\). We show that Q satisfies the properties specified in Theorem 4.1.

Since S is a 2-factor of \(G_{T\Delta}\), \(C_{e_i}\cap; C_{e_j}=\emptyset\) for any \(C_{e_i}, C_{e_j}\in S\). By definition of \(G_{T\Delta}\), if \(v,w\in V(P)\) and \(v\neq w\), then \(F_v^*, F_w^*\in \mathcal{Q}\) have no edge in common. Consider \(C_{e_i}, F_v^*\in \mathcal{Q}\) with \(C_{e_i}\in S\). Since each \(C_{e_i}\) corresponds to some face \(F_{e_i}\) of \(G_{T\Delta}\) and \(F_v\) and \(F_{e_i}\) have at most one edge in common, it follows that \(C_{e_i}\) and \(F_v^*\) have at most one edge in common. Therefore, any two distinct cycles in \(\mathcal{Q}\) have at most one edge in common.

We now show that the intersection graph \(I(\mathcal{Q})\) is a tree. We represent the path P with \(P=v_0v_1...v_k\) and let \(e_i\) be the edge connecting \(v_{i-1}\) and \(v_i\). We denote by \(\mathcal{Q}_P\) the subset of \(\mathcal{Q}\) obtained by taking only the elements of \(\mathcal{Q}\) that correspond vertices and edges in P. So \(\mathcal{Q}_P=\{F_{v_0}^*,C_{e_1},F_{v_1}^*,C_{e_2},...,C_{e_k},F_{v_k}^*\}\). It is easy to see that \(I(\mathcal{Q}_P)\) is a tree with vertex set \(\mathcal{Q}_P\) and the edges are \(F_{v_{i-1}}^*C_{e_i}\) and \(C_{e_i}F_{v_i}^*\), with i=1,2,...,k.

Let \(f_i\) be an edge of G not in P. Then there is a cycle \(C_{f_i}\) in the 2-factor S corresponding to \(f_i\). Since \(f_i\) is incident to exactly one vertex \(v_i\) on the path \(P = v_0v_1...v_k\), we extend \(I(\mathcal{Q}_P)\) to \(I(\mathcal{Q})\) by connecting \(C_{f_i}\) to \(F_{v_i}^*\) for each edge \(f_i\) not in P.

Figure 5 shows how a dominating path, shown with dotted lines, in the ladder graph \(L_n\) can be extended to a dominating path in \(L_{n+1}\). We therefore use Theorem 4.4 to state the following result.

Corollary 4.3. Let G be the ladder graph \(L_n\), with \(n \geq 2\). Then \(G_{T\Delta}\) is hamiltonian.

5. Final Remarks

We conclude by noting that the graphs \(G_{T\triangle}\) are unique in that they each contain multiple perfect matchings (Theorem 3.3) and a \(\Lambda\)-factor (Theorem 3.1). There are also similarities among truncated triangulations \(G_{T\triangle}\), vertex envelopes, which are obtained using the leapfrog operation, and graphs obtained using the quadrupling (chamfering) operation. The properties include being cubic and planar, bipartiteness if G is bipartite, and having a face in the derived graphs corresponding to each face of G. It also true that if G is a fullerene graph, then the graph obtained by applying any of these three operations is also a fullerene graph. In the case of vertex envelopes and \(G_{T\triangle}\), the faces corresponding to faces of G form a 2-factor of the derived graph.

Let \(G_Q\) be the chamfering graph obtained by performing the quadrupling transformation [6] of a plane connected simple graph G. Then \(G_{T\Delta}\) is isomorphic to the graph obtained from \(G \cup G_Q\)

Figure 5. Dominating paths in ladder graphs

by truncating each vertex of G. One way to show this is to observe that we can obtain G^Q from G^T △ by deleting all the edges of G^T △ corresponding to edges of G and contracting every edge e belonging to faces of type Fv. Even with a lot of similarities with other graphs, what sets the graphs G^T △ apart is the large number perfect matchings and hexagonal faces they have (Theorem 3.3 and Proposition 2.3).

References

• [1] S. Arumugam, I. S. Hamid, and V.M. Abraham, Decomposition of Graphs into Paths and Cycles, Journal of Discrete Mathematics, (2013).
• [2] M.V. Diudea and V.R Rosenfeld, The truncation of a cage graph. J Math Chem 55 (2017), 1014–1020.
• [3] H. Fleischner, On spanning subgraphs of a connected bridgeless graph and their application to graphs. J. Combin. Theory Ser. B, 16 (1974), 17-28.
• [4] H. Fleischner, A.M. Hobbs, and M.T. Muzheve, Hamiltonicity in vertex envelopes of plane cubic graphs, Discrete Mathematics, 309(14)(2009), 4793-4809.
• [5] Conjecture attributed to D.W. Barnette, by B. Grünbaum in Unsolved Problem 5, page 343, in: Proc. of the Third Waterloo Conf. on Combinatorics (May, 1968), in: W.T. Tutte (Ed.), Recent Progress in Combinatorics, Academic Press, New York, NY, 1969.
• [6] P.W. Fowler, J.E. Cremona, and J.I. Steer, Systematics of bonding in non-icosahedral carbon clusters. Theoret. Chim. Acta, 73 (1988), 1–26.
• [7] H. Harary and C. Nash-Williams, C. St. J.A, On Eulerian and Hamiltonian graphs and line graphs, Canadian Mathematical Bulletin, 8(6)(1965), 701-709.
• [8] A.K. Kelmans, Packing 3-vertex paths in cubic 3-connected graphs. arXiv: Combinatorics, (2008).

• [9] L. Lovasz, On Covering of graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press (1968), 231–236.
• [10] M.T. Muzheve, A Sufficient Condition for the Hamiltonicity of Vertex Envelopes of Plane Graphs. Model Assisted Statistics and Applications, 19(4)(2024), 325-331.
• [11] S. Pirzadaa, H.A. Ganieb, and, M. Siddique, On some covering graphs of a graph, Electronic Journal of Graph Theory and Applications, 4(2)(2016), 132–147.
• [12] X. Wang, Yin, Fu-Gang; Zhou, and Jin-Xin. On generalized truncations of complete graphs. Ars Mathematics Contemporanea, [S.l.], 19(2)(2020), 325-335.
• [13] N. Viswanathan and D. West. Hamiltonian Cycles and Tight Cutsets, Graphs and Combinatorics 41(1)(2024).
• [14] D. West, Introduction to Graph Theory, Prentice Hall, 2001.