Electronic Journal of Graph Theory and Applications

Andrew Bowling and Ping Zhang

Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008-5248, USA

andrew.d.bowling@wmich.edu, ping.zhang@wmich.edu

A zonal labeling of a plane graph G is an assignment of the two nonzero elements of the ring \(\mathbb{Z}_3\) of integers modulo 3 to the vertices of G such that the sum of the labels of the vertices on the boundary of each region of G is the zero element of \(\mathbb{Z}_3\). A plane graph possessing such a labeling is a zonal graph. There is a connection between zonal labelings of connected bridgeless cubic plane graphs and the Four Color Theorem. Zonal labelings of cycles play a role in this connection. The cycle rank of a connected graph of order n and size m is m-n+1. Thus, cycles have cycle rank 1. All zonal connected graphs of cycle rank at most 2 are determined.

Keywords: planar graph, graph embedding, zonal labeling, zonal graph, cycle rank Mathematics Subject Classification: 05C10, 05C15, 05C78

DOI: 10.5614/ejgta.2023.11.1.1

1. Introduction

Let G be a connected plane graph each of whose vertices is labeled with one of the two nonzero elements 1 and 2 of the ring \(\mathbb{Z}_3\) of integers modulo 3. The value of a region (zone) R of G is the sum in \(\mathbb{Z}_3\) of the labels of the vertices on the boundary of R. Such a labeling of G is said to be a zonal labeling if the value of each zone in G is the zero element of \(\mathbb{Z}_3\). If G admits a zonal labeling, then G is zonal. This concept was introduced by Cooroo Egan in 2014 (see [3]).

There is a close connection between the Four Color Theorem and zonal labelings of planar graphs. A connected bridgeless cubic plane graph (or multigraph) is referred to as a cubic map.

Received: 26 May 2022, Revised: 6 January 2023, Accepted: 29 January 2023.

Thus, every cubic map is a 3-regular 2-edge-connected plane graph. The following two results were established in [3].

Theorem 1.1. [3] A connected cubic plane graph G is zonal if and only if G is bridgeless.

Theorem 1.2. [3] There exists a 4-coloring of the regions of a cubic map M if and only if M has a zonal labeling.

Since it is known that there exists a 4-coloring of the regions of every plane map (the Four Color Theorem) if and only if there exists a 4-coloring of the regions of every cubic map (see [5], for example), it follows by Theorem 1.2 that showing every cubic map is zonal is equivalent to establishing the Four Color Theorem.

As described in [3], the argument given that establishes the truth of Theorems 1.1 and 1.2, however, makes use of the Four Color Theorem. It would be considerably more satisfying if it could be shown that every cubic map is zonal without using the Four Color Theorem (and without using computers). Thus, the following fundamental question was stated in [3].

Problem 1.3. Can it be shown that every cubic map is zonal without using the Four Color Theorem or computers?

Problem 1.3 brings up the natural question of determining the zonality of plane graphs and planar graphs in general. A planar graph G is zonal if there exists a zonal planar embedding of G. This concept has been studied in [1, 2, 3, 4]. Since the boundary of every region of a cubic map is a cycle, it is of value to know which cycles and related graphs are zonal. That every nontrivial tree and every cycle is zonal was established in [3].

Theorem 1.4. [3] Every nontrivial tree and every cycle is zonal.

The cycle rank of a connected graph of order n size m is the number m − n + 1. Thus, cycles have cycle rank 1. In general, the graphs of cycle rank 1 are connected graphs possessing exactly one cycle. The goal of this paper is to determine all zonal graphs of cycle rank 1 and 2. All such graphs are necessarily planar.

2. Zonal Unicyclic Graphs

A connected graph containing exactly one cycle is referred to as a unicyclic graph. Thus, the unicyclic graphs are precisely the graphs of cycle rank 1. In order to determine which unicyclic graphs are zonal, we first state some information on zonal labelings. Let ℓ be a labeling of the vertices of a graph G with the labels 1 and 2 of Z3. The vertex labeling ℓ of G defined by ℓ(v) = 3 − ℓ(v) for each vertex v of G is called the complementary labeling of G.

Observation 2.1. [3] If ℓ is a zonal labeling of a connected plane graph, then so too is its complementary labeling ℓ.

The following notation will be useful to us. For a labeling ℓ : V (G) → {1, 2} ⊆ Z³ of a graph G and a subgraph H or a nonempty set X of vertices of G, let

\[\sum (\ell, H) = \sum_{x \in V(H)} \ell(x) \text{ in } \mathbb{Z}_3 \text{ and } \sum (\ell, X) = \sum_{x \in X} \ell(x) \text{ in } \mathbb{Z}_3.\]

In particular, if B is the boundary of a region R of a plane graph G and \(\ell\) is a labeling of G, then \(\sum (\ell, B)\) is the value of B (as well as the value of R).

Lemma 2.2. Let X be a nonempty set of vertices of a graph.

• (1) For each i = 1, 2, there is a labeling \(\ell_i : X \to \{1, 2\} \subseteq \mathbb{Z}_3\) of X such that \(\sum (\ell_i, X) = i\) in \(\mathbb{Z}_3\).
• (2) If \(|X| \ge 2\), then there is a labeling \(\ell_0: X \to \{1,2\} \subseteq \mathbb{Z}_3\) of X such that \(\sum (\ell_0, X) = 0\) in \(\mathbb{Z}_3\).

Proof. First, we verify (1). For each i = 1, 2, define a labeling \(\ell_i : X \to \{1, 2\}\) of X as follows.

• * If \(|X| \ge 1\) is odd, then |X| = 2k + 1 for some nonnegative integer k. Let \(\ell_1\) assign the label 1 to k+1 vertices of X and assign the label 2 to k vertices of X, giving the sum \(\sum (\ell_1, X) = 1 \cdot (k+1) + 2k = 1\) in \(\mathbb{Z}_3\). Let \(\ell_2\) be the complementary labeling of \(\ell_1\), that is, let \(\ell_2\) assign the label 1 to k vertices of X and assign the label 2 to k+1 vertices of X, giving the sum \(\sum (\ell_2, X) = 1 \cdot k + 2(k+1) = 2\) in \(\mathbb{Z}_3\).
• * If \(|X| \ge 2\) is even, then |X| = 2k = (k-1) + (k+1) for some positive integer k. Let \(\ell_1\) assign the label 2 to k+1 vertices of X and assign the label 1 to k-1 vertices of X, giving the sum \(\sum (\ell_1, X) = 1 \cdot (k-1) + 2(k+1) = 1\) in \(\mathbb{Z}_3\). Let \(\ell_2\) be the complementary labeling of \(\ell_1\), that is, let \(\ell_2\) assign the label 1 to k+1 vertices of X and assign the label 2 to k-1 vertices of X, giving the sum \(\sum (\ell_2, X) = 1 \cdot (k+1) + 2(k-1) = 2\) in \(\mathbb{Z}_3\).

Next, we verify (2). For \(|X| \geq 2\), let \(x_0 \in X\) and \(X' = X - \{x_0\}\). By (1), for each i = 1, 2, there is a labeling \(\ell_i : X' \to \{1, 2\}\) of X such that \(\sum (\ell_i, X') = i\) in \(\mathbb{Z}_3\). Define the labeling \(\ell_0 : X \to \{1, 2\}\) of X by \(\ell_0(x) = \ell_i(x)\) if \(x \in X'\) and \(\ell_0(x_0) = 3 - i\). Thus, \(\sum (\ell_0, X) = \sum (\ell_i, X') + \ell_0(x_0) = i + (3 - i) = 0\) in \(\mathbb{Z}_3\).

Let \(C \star K_2\) be the unicyclic graph obtained by adding exactly one pendant edge at some vertex of a cycle C. We are now prepared to present the following result.

Theorem 2.3. A unicyclic graph G is zonal if and only if \(G \neq C \star K_2\) for any cycle C.

Proof. Let G be a unicyclic graph containing the cycle C such that \(G \neq C \star K_2\). We show that G is zonal. By Theorem 1.4, we may assume that \(G \neq C\). Let G be embedded in the plane (resulting in two regions \(R_1\) and \(R_2\)) such that the boundary of \(R_1\) is C and that the boundary of \(R_2\) is G. By Theorem 1.4, there is a zonal labeling \(\ell_C\) of C. Let U = V(G) - V(C) be the set of vertices of G that do not belong to C. Then \(p = |U| \geq 2\). We now extend the labeling \(\ell_C\) of C to a labeling \(\ell\) of G. First, we define \(\ell(v) = \ell_C(v)\) for all \(v \in V(C)\). Thus, the sum of the labels of the vertices on C is \(\sum (\ell, C) = \sum (\ell_C, C) = 0\). Next, we define the labels of vertices in C as follows. If C is even, then we assign the label 1 to half of the vertices of C and the label 2 to the other half, giving us a sum of C in C in C is C is even, then we assign the label 1 to half of the vertices of C and the label 2 to the other half, giving us a sum of C in C in C is C is even, then we assign the label 1 to half of the vertices of C and the label 2 to the other half, giving us a sum of C in C in C in C is even, then C is C in C in C in C is even, then we assign the label 1 to half of the vertices of C is C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C in C

vertices of U, assign the label 2 to the other k-1 vertices of U, and add these labels, we have \(1 \cdot (k+2) + 2(k-1) = (k+2) + 2k - 2 = 3k = 0\) in \(\mathbb{Z}_3\). Consequently, the values of \(R_1\) and \(R_2\) are both 0 and so \(\ell\) is a zonal labeling of G. Therefore, G is zonal.

For the converse, suppose that \(G = C \star K_2\) for a cycle C, where u is the vertex of G that does not belong to C. Let there be given a planar embedding of G; that is, G is a plane graph. Assume, to the contrary, that G has a zonal labeling \(\ell\). Then \(\ell(u) \in \{1,2\}\). Since C is the boundary of some region \(R_1\) of G, the value of C is 0. However then, the value of the boundary of the other region \(R_2\) of G is the sum of the value of C and \(\ell(u)\), that is, \(0 + \ell(u) = \ell(u) \neq 0\) in \(\mathbb{Z}_3\), which is a contradiction.

Recall that a planar graph G is zonal if there exists a zonal planar embedding of G. It is possible that a planar graph has both a zonal planar embedding and a non-zonal planar embedding. For example, Figure 1 shows two distinct planar embeddings of a planar graph G. The planar embedding of G in Figure 1(a) is zonal and a zonal labeling is also shown in that figure, while the planar embedding of G in Figure 1(b) is not zonal. Next, we show that if G is a zonal graph of cycle rank 1 (namely, a unicyclic graph), then every planar embedding of G is zonal.

Figure 1. A graph with a zonal planar embedding and a non-zonal planar embedding

Proposition 2.4. Every planar embedding of a zonal graph of cycle rank 1 is zonal.

Proof. Since there is only one planar embedding of a cycle, the statement is true trivially. Next, let G be a zonal unicyclic graph containing the cycle C. We may assume that \(G \neq C\) and \(G \neq C \star K_2\) by Theorem 2.3. Let U = V(G) - V(C) be the set of vertices of G that do not belong to C. Then \(p = |U| \geq 2\). Let G be embedded in the plane resulting two regions \(R_1\) and \(R_2\). We show that the resulting plane graph G has a zonal labeling. For i = 1, 2, let G be the boundary of G and so G contains G. If G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G and so G an

3. Zonal Graphs of Cycle Rank 2

We next determine those graphs of cycle rank 2 that are zonal. A graph G has cycle rank 2 if G contains a subgraph F where

• (1) F is obtained from two cycles C and C' by identifying a vertex in C and a vertex in C', which is denoted by \(F = C \star C'\), as shown in Figure 2(a),
• (2) F is obtained from two disjoint cycles C and C' by adding a path P of length 1 or more and then by identifying an end-vertex of P with a vertex of C and identifying the other end-vertex of P with a vertex of C', which is denoted by \(F = C \star P \star C'\), as shown in Figure 2(b), or
• (3) F is a subdivision of \(K_4 e\), that is, G consists of three internally disjoint paths \(P_i\) (\(1 \le i \le 3\)), where at least two paths \(P_i\) (\(1 \le i \le 3\)) have length 2 or more, as shown in Figure 2(c).

Necessarily, every embedding of a graph of cycle rank 2 results in a plane graph with exactly three regions – namely one exterior region and two interior regions.

Figure 2. Three possible types of subgraphs

For i=1,2,3, a graph G is referred to as a graph of cycle rank 2 and type (i) if G contains a subgraph F satisfing the properties described in (i) above. Furthermore, a graph G of cycle rank 2 is minimal if G is one of the graphs F described in (1), (2), or (3). Consequently, every minimal graph G of cycle rank 2 has minimum degree 2. The graph \(K_4 - e\) is a minimal graph of cycle rank 2 and type 3 but it is not zonal. This gives rise to the more general question: Which graphs of cycle rank 2 are zonal?

First, we determine all zonal graphs of cycle rank 2 and type (1).

Theorem 3.1. Let G be a graph of cycle rank 2 and type (1). Then G is zonal if and only if G is not minimal.

Proof. Since G is a graph of cycle rank 2 and type (1), it follows that G contains a subgraph \(C \star C'\) obtained from two cycles C and C' by identifying a vertex in C and a vertex in C', denoting this identified vertex by u.

First, suppose that G is minimal and so \(G = C \star C'\). We show that G is not zonal. Assume, to the contrary, that G is zonal. Then there exists a planar embedding of G such that the resulting plane graph G has a zonal labeling \(\ell\). Since each of C and C' is the boundary of a region of G, it follows that \(\sum (\ell, C) = \sum_{v \in V(C)} \ell(v) = 0\) and \(\sum (\ell, C') = \sum_{v \in V(C')} \ell(v) = 0\). However then, the value of the boundary of the region \(R_3\) is \([\sum (\ell, C) + \sum (\ell, C')] - \ell(u) = 0 + 0 - \ell(u) \neq 0\) in \(\mathbb{Z}_3\), which is a contradiction.

For the converse, suppose that G is a graph of cycle rank 2 and type (1) such that \(G \neq C \star C'\) where u is the vertex belonging to both C and C'. We show that G is zonal. We embed G in the plane resulting in three regions \(R_1\), \(R_2\), and \(R_3\) such that the boundary of \(R_1\) is C, the boundary of \(R_2\) is C', and the boundary of \(R_3\) is G. Since C and C' are zonal by Theorem 1.4, there are zonal labelings \(\ell_C\) and \(\ell_{C'}\) of C and C', respectively. We may assume that \(\ell_C(u) = \ell_{C'}(u) = 1\) where u belongs to C and C'. Let \(U = V(G) - V(C \star C')\) be the set of vertices of G that do not belong to \(C \star C'\). Then \(|U| \geq 1\). We now define a labeling \(\ell\) of G. First, we define \(\ell(v) = \ell_C(v)\) for all \(v \in V(C)\) and \(\ell(v) = \ell_{C'}(v)\) for all \(v \in V(C')\). Thus, the value of the boundary C of \(R_1\) is \(\sum (\ell, C) = \sum (\ell_C, C) = 0\) and the value of the boundary C' of \(R_2\) is \(\sum (\ell, C') = \sum (\ell_{C'}, C') = 0\). Next, we can define the labels of vertices of U such that \(\sum (\ell, U) = 1\) in \(\mathbb{Z}_3\) by Lemma 2.2. Thus, the value of the boundary G of \(R_3\) is \(\sum (\ell, C) + \sum (\ell, C') - \ell(u) + \sum (\ell, U) = -1 + 1 = 0\) in \(\mathbb{Z}_3\). Consequently, the values of \(R_1\), \(R_2\), and \(R_3\) are all 0 and so \(\ell\) is a zonal labeling of G.

We now determine all zonal graphs of cycle rank 2 and type (2).

Theorem 3.2. Let G be a graph of cycle rank 2 and type (2). Then G is zonal if and only if either every vertex of G belongs to a cycle of G or at least two vertices of G belong to no cycle of G.

Proof. First, let G be a zonal graph of cycle rank 2 and type (2) such that exactly one vertex w of G belongs to no cycle of G. Therefore, either G is a minimal graph \(C \star P \star C'\) where C and C' are two cycles and P is a path of length 2 with interior vertex w or G is obtained from a minimal graph \(C \star P \star C'\) by adding a pendant edge e = wv where \(v \in V(C \star P \star C')\), C and C' are two cycles, and P is a path of length 1. Since G is zonal, there is a planar embedding of G, resulting in the three regions \(R_1\), \(R_2\), and \(R_3\), and a zonal labeling \(\ell\) of the resulting plane graph G.

• * If \(G = C \star P \star C'\), where P has length 2, then the boundaries of the three regions of G are C, C', and G. Thus, \(\sum (\ell, C) = \sum (\ell, C') = 0\) and \(\sum (\ell, G) = \sum (\ell, C) + \sum (\ell, C') + \ell(w) = \ell(w) = 0\) in \(\mathbb{Z}_3\), which is impossible since \(\ell(w) \in \{1, 2\}\).
• * If G consists of a minimal graph \(C \star P \star C'\) and a pendant edge e = wv, where P is a path of length 1, then we may assume that the boundary of one region \(R_1\) of G is C and so \(\sum (\ell,C)=0\) in \(\mathbb{Z}_3\). The boundaries of the other two regions are either (a) C' and G or (b) \(C \star P \star C'\) and C' with uv. If (a) occurs, then \(\sum (\ell,C')=0\) and \(\sum (\ell,G)=\sum (\ell,C)+\sum (\ell,C')+\ell(w)=\ell(w)=0\) in \(\mathbb{Z}_3\), which is impossible. If (b) occurs, then \(\sum (\ell,C\star P\star C')=\sum (\ell,C)+\sum (\ell,C')=0\) and \(\sum (\ell,C')+\ell(w)=0\). Since \(\sum (\ell,C)=0\), it follows that \(\sum (\ell,C')=0\). However then, \(\sum (\ell,C')+\ell(w)=0+\ell(w)=0\), which is impossible.

For the converse, suppose that either every vertex of G belongs to a cycle of G or at least two vertices of G belong to no cycle of G. Thus, p=0 or \(p\geq 2\). We show that G is zonal. Embed G in the plane resulting in three regions \(R_1\), \(R_2\), and \(R_3\) such that the boundary of \(R_1\) is C, the boundary of \(R_2\) is C', and the boundary of \(R_3\) is G. Since C and C' are zonal, there are zonal labelings \(\ell_C\) and \(\ell_{C'}\) of C and C', respectively. We define a labeling \(\ell\) of G as follows. First, we define \(\ell(v) = \ell_C(v)\) for all \(v \in V(C)\) and \(\ell(v) = \ell_{C'}(v)\) for all \(v \in V(C')\). Thus, the value of the boundary C of \(R_1\) is \(\sum (\ell, C) = \sum (\ell_C, C) = 0\) and the value of the boundary C' of \(R_2\) is \(\sum (\ell, C') = \sum (\ell_{C'}, C') = 0\). Next, we define the labels of vertices of U as follows.

If p=0, then \(\sum (\ell,U)=0\) vacuously. If \(p\geq 2\), then let \(\ell\) assign the labels 1 and 2 to the vertices of U such that \(\sum (\ell,U)=0\) by Lemma 2.2. Hence, the value of the boundary G of \(R_3\) is \(\sum (\ell,C)+\sum (\ell,C')+\sum (\ell,U)=0\) in \(\mathbb{Z}_3\). Consequently, the values of \(R_1,R_2\), and \(R_3\) are all 0 and so \(\ell\) is a zonal labeling of G.

By Theorem 3.1, no minimal graph of cycle rank 2 and type (1) is zonal; while by Theorem 3.2, every minimal graph of cycle rank 2 and type (2) is zonal. For minimal graphs of cycle rank 2 and type (3), the situation is different, as we show next.

Theorem 3.3. Let G be a minimal graph of cycle rank 2 and type (3) consisting of three internally disjoint u-v paths \(P_i\) of order \(n_i\) for i=1,2,3 where \(2 \le n_1 \le n_2 \le n_3\) and \(n_2 \ge 3\). Then G is zonal if and only if \((n_1,n_2) \ne (2,3)\).

Proof. First, suppose that \((n_1, n_2) = (2, 3)\). We show that G is not zonal. Assume, to the contrary, that G is zonal. Then there exists a planar embedding of G, resulting in three regions \(R_1\), \(R_2\), and \(R_3\), such that the resulting plane graph G has a zonal labeling \(\ell\). We may assume that the boundary of \(R_1\) consists of \(P_1\) and \(P_2\), the boundary of \(R_2\) consists of \(P_2\) and \(P_3\), and the boundary of \(R_3\) consists of \(P_1\) and \(P_3\). Let w be the interior vertex of \(P_2\). Since the value of the boundary of \(R_2\) is \(\sum (\ell, P_3) + \ell(w) = 0\) in \(\mathbb{Z}_3\) and the value of the boundary of \(R_3\) is \(\sum (\ell, P_3) = 0\) in \(\mathbb{Z}_3\), it follows that \(\ell(w) = 0\) in \(\mathbb{Z}_3\), which is impossible. Thus, G is not zonal.

For the converse, suppose that \((n_1, n_2) \neq (2, 3)\). Here, we show that G is zonal. We embed the graph G in the plane, resulting in three regions \(R_1, R_2\), and \(R_3\) where \(R_3\) is the exterior region of G, where u and v are the two vertices of degree 3 in G. We show that the resulting plane graph G has a zonal labeling. For i = 1, 2, 3, let \(Q_i = P_i - \{u, v\}\) and so \(Q_i\) is a path of order \(n_i - 2\) (where there is no path \(Q_1\) if \(n_1 = 2\)). We consider three cases, depending on whether \(n_1 \geq 4\), \(n_1 = 3\), or \(n_1 = 2\).

Case 1. \(n_1 \geq 4\). Since \(n_3 \geq n_2 \geq n_1 \geq 4\), it follows by Theorem 1.4 that each path \(Q_i\) (i=1,2,3) is zonal. For i=1,2,3, let \(\ell_i\) be a zonal labeling of \(Q_i\) and so \(\sum (\ell_i,Q_i)=0\) in \(\mathbb{Z}_3\). We define a labeling \(\ell\) of G by \(\ell(u)=2\), \(\ell(v)=1\), and \(\ell(x)=\ell_i(x)\) if \(x\in V(Q_i)\) for i=1,2,3. Since the boundary of a region of G is \(\sum (\ell_i,Q_i)+\sum (\ell_j,Q_j)+1+2=0\) in \(\mathbb{Z}_3\) for distinct integers \(i,j\in\{1,2,3\}\), it follows that \(\ell\) is a zonal labeling of G.

Case 2. \(n_1=3\). We define a labeling \(\ell\) of G such that \(\ell(u)=\ell(v)=2\) and \(\sum(\ell,Q_i)=1\) for i=1,2,3 by Lemma 2.2. Since the boundary of the region \(R_i\) of G is \(\sum(\ell,Q_i)+\sum(\ell,Q_j)+\ell(u)+\ell(v)=1+1+2+2=0\) in \(\mathbb{Z}_3\) for some \(j\in\{1,2,3\}-\{i\}\), it follows that \(\ell\) is a zonal labeling of G.

Case 3. \(n_1=2\). Thus, there is no path \(Q_1\). Since \((n_1,n_2)\neq (2,3)\), it follows that \(n_3\geq n_2\geq 4\). By Theorem 1.4, each path \(Q_i\) (i=2,3) is zonal and so has a zonal labeling \(\ell_i\). Thus, \(\sum (\ell_i,Q_i)=0\) in \(\mathbb{Z}_3\) for i=2,3. As we saw in Case 1, we can define the labeling \(\ell\) of G by \(\ell(u)=2\), \(\ell(v)=1\), and \(\ell(x)=\ell_i(x)\) if \(x\in V(Q_i)\) for i=2,3. Then \(\ell\) is a zonal labeling of G.

We now determine which graphs of cycle rank 2 are zonal if they contain a minimal non-zonal graph of cycle rank 2 and type (3) as a proper subgraph.

Theorem 3.4. Let F be a minimal non-zonal graph of cycle rank 2 and type (3) and let G be a graph of cycle rank 2. If G contains F as a proper subgraph, then G is zonal.

Proof. Let U=V(G)-V(F) be the set of vertices of G that do not belong to F. Then \(|U|\geq 1\). Since the subgraph F of G is non-zonal, it follows by Theorem 3.3 that F consists of three internally disjoint u-v paths \(P_i\) of order \(n_i\) for i=1,2,3 where \(n_1=2\) and \(3=n_2\leq n_3\). Let w be the interior vertex of \(P_2\) and let \(Q_3=P_3-\{u,v\}\) be a path of order \(q_3=n_3-2\geq 1\). We embed the graph G in the plane in such a way that the boundary of \(R_1\) is the triangle (u,w,v,u), the boundary of \(R_2\) is G-uv, and the boundary of \(R_3\) is \((u,Q_3,v,u)\), as shown in Figure 3, for example.

Figure 3. An embedding of the graph G

We define a labeling \(\ell\) of G such that \(\ell(u) = \ell(v) = \ell(w) = 1\), \(\sum (\ell, Q_3) = 1\) in \(\mathbb{Z}_3\), and \(\sum (\ell, U) = 2\) in \(\mathbb{Z}_3\). Then the value of the boundary of \(R_1\) is \(\ell(u) + \ell(w) + \ell(v) = 1 + 1 + 1 = 0\) in \(\mathbb{Z}_3\), the value of the boundary of \(R_2\) is \(\ell(u) + \ell(w) + \ell(v) + \sum (\ell, Q_3) + \sum (\ell, U) = 1 + 1 + 1 + 1 + 2 = 0\) in \(\mathbb{Z}_3\), and the value of the boundary of \(R_3\) is \(\ell(u) + \ell(v) + \sum (\ell, Q_3) = 1 + 1 + 1 = 0\) in \(\mathbb{Z}_3\). Consequently, \(\ell\) is a zonal labeling of G and so G is zonal.

Next, we consider graphs of cycle rank 2 containing a proper minimal zonal subgraph of cycle rank 2 and type (3). For a minimal graph F of cycle rank 2 and type (3), let \(F \star K_2\) be the graph obtained from F by adding a pendant edge at a vertex of F.

Theorem 3.5. If F is a minimal zonal graph of cycle rank 2 and type (3), then \(F \star K_2\) is zonal.

Proof. Let F consist of three internally disjoint u-v paths \(P_i\) of order \(n_i\) for i=1,2,3 where \(2 \le n_1 \le n_2 \le n_3\) and \(n_2 \ge 3\) and let \(G=F\star K_2\). We consider two cases, according to whether \(n_1 \ge 3\) or \(n_1=2\).

Case 1. \(n_1 \geq 3\). Then \(n_3 \geq n_2 \geq n_1 \geq 3\). For i=1,2,3, let \(Q_i=P_i-\{u,v\}\) be the path of order \(q_i \geq 1\). We may assume, without loss of generality, that G is obtained by adding a vertex w and joining w to a vertex z of \(P_3\) (where it is possible that z=u or z=v). Let G be embedded in the plane resulting in three regions \(R_1\), \(R_2\), and \(R_3\) such that w belongs to the boundary of \(R_3\). For i=1,2,3, let \(B_i\) be the boundary of \(R_i\). Define the labeling \(\ell\) of G such that (i) \(\ell(u)=\ell(w)=1\) and \(\ell(v)=2\) and (ii) \(\sum(\ell,Q_1)=\sum(\ell,Q_3)=1\) and \(\sum(\ell,Q_2)=2\). Then the value of \(B_1\) is \(\ell(u)+\ell(v)+\sum(\ell,Q_1)+\sum(\ell,Q_1)+\sum(\ell,Q_2)=1+2+1+2=0\) in \(\mathbb{Z}_3\), the value of \(B_2\) is \(\ell(u)+\ell(v)+\sum(\ell,Q_2)+\sum(\ell,Q_3)=1+2+2+1=0\) in \(\mathbb{Z}_3\), the value of \(B_3\) is \(\ell(u)+\ell(v)+\ell(w)+\sum(\ell,Q_1)+\sum(\ell,Q_3)=1+2+1+1=0\) in \(\mathbb{Z}_3\). Thus, \(\ell\) is a zonal labeling of G.

Case 2. \(n_1 = 2\). Since F is zonal, it follows by Theorem 3.3 that \(n_3 \ge n_2 \ge 4\). For i = 2, 3, let \(Q_i = P_i - \{u, v\}\) be the path of order \(q_i \ge 2\). We may assume, without loss of generality,

that G is obtained by adding a vertex w and joining w to a vertex z of \(P_3\) (where it is possible that z=u or z=v). Let G be embedded in the plane resulting in three regions \(R_1\), \(R_2\), and \(R_3\) such that w belongs to the boundary of \(R_3\). For i=1,2,3, let \(B_i\) be the boundary of \(R_i\). Define a labeling \(\ell\) of G such that (i) \(\ell(u)=\ell(v)=\ell(w)=1\) and (ii) \(\sum (\ell,Q_2)=1\) and \(\sum (\ell,Q_3)=0\). Hence, the value of \(B_1\) is \(\ell(u)+\ell(v)+\sum (\ell,Q_2)=1+1+1=0\) in \(\mathbb{Z}_3\), the value of \(B_2\) is \(\ell(u)+\ell(v)+\sum (\ell,Q_2)+\sum (\ell,Q_3)=1+1+1+0=0\) in \(\mathbb{Z}_3\), and the value of \(B_3\) is \(\ell(u)+\ell(v)+\ell(w)+\sum (\ell,Q_3)=1+1+1+0=0\) in \(\mathbb{Z}_3\). Consequently, \(\ell\) is a zonal labeling of G.

Theorem 3.6. Let F be a minimal zonal graph of cycle rank 2 and type (3) and let G be a graph of cycle rank 2. If G contains F as a proper subgraph and \(G \neq F \star K_2\), then G is zonal.

Proof. Since F is a minimal zonal graph of cycle rank 2 and type (3), it follows that F consists of three internally disjoint u-v paths \(P_i\) of order \(n_i\) for i=1,2,3 where \(2 \le n_1 \le n_2 \le n_3\), \(n_2 \ge 3\) and \((n_1,n_2) \ne (2,3)\) by Theorem 3.4. For i=1,2,3, let \(Q_i=P_i-\{u,v\}\) and so \(Q_i\) is a path of order \(q_i=n_i-2\) (where there is no path \(Q_1\) if \(n_1=2\)). Let U=V(G)-V(F) be the set of vertices of G that do not belong to F and let p=|U|. Since \(G \ne F \star K_2\), it follows that \(p\ge 2\). We consider two cases.

Case 1. There is some path \(P \in \{P_1, P_2, P_3\}\) such that every interior vertex of P has degree 2 in G. There are two subcases, according to whether \(n_1 = 2\) or \(n_1 \ge 3\).

Subcase 1.1. \(n_1 = 2\). Since \((n_1, n_2) \neq (2, 3)\), it follows that \(n_3 \geq n_2 \geq 4\) and so \(q_3 \geq q_2 \geq 2\). Let G be embedded in the plane in such a way that the boundary of \(R_1\) is \(P_2 + uv\), the boundary of \(R_2\) is G - uv, and the boundary of \(R_3\) is \(P_3 + uv\) (see Figure 4, for example).

Figure 4. An embedding of the graph G in Subcase 1.1

We define a labeling \(\ell\) of G such that \(\ell(u) = \ell(v) = 1\), \(\sum (\ell, Q_i) = 1\) in \(\mathbb{Z}_3\) for i = 2, 3, and \(\sum (\ell, U) = 2\) in \(\mathbb{Z}_3\). Then the value of the boundary of \(R_1\) is \(\ell(u) + \ell(v) + \sum (\ell, Q_2) = 1 + 1 + 1 = 0\) in \(\mathbb{Z}_3\), the value of the boundary of \(R_2\) is \(\ell(u) + \ell(v) + \sum (\ell, Q_2) + \sum (\ell, Q_3) + \sum (\ell, U) = 1 + 1 + 1 + 1 + 2 = 0\) in \(\mathbb{Z}_3\), and the value of the boundary of \(R_3\) is \(\ell(u) + \ell(v) + \sum (\ell, Q_3) = 1 + 1 + 1 = 0\) in \(\mathbb{Z}_3\). Consequently, \(\ell\) is a zonal labeling of G.

Subcase 1.2. \(n_1 \geq 3\). Thus, \(n_3 \geq n_2 \geq n_1 \geq 3\). We may assume that every interior vertex of \(P_1\) has degree 2. We embed the graph G in the plane in such a way that the boundary \(B_1\) of \(R_1\) consists of \(P_1\) and \(P_2\), the boundary \(B_2\) of \(R_2\) is \(G - V(Q_1)\), and the boundary \(B_3\) of \(R_3\) consists of \(P_1\) and \(P_3\) (see Figure 5, for example). Thus, all vertices of U belong to the boundary \(B_2\) of \(R_2\). The planar embedding of G Figure 5 gives rise to a planar embedding of F such that \(P_1\) is \(P_2\).

\(B_2^* = B_2 - U\), and \(B_3^* = B_3\) are the boundaries of the three regions \(R_1^* = R_1\), \(R_2^*\), and \(R_3^* = R_3\) of F. Since F = G - U is zonal, there is a zonal labeling \(\ell_F\) of F.

Figure 5. An embedding of the graph G in Subcase 1.2

We define a labeling \(\ell\) of G such that \(\ell(x) = \ell_F(x)\) if \(x \in V(F)\) and \(\sum (\ell, U) = 0\) in \(\mathbb{Z}_3\) (by Lemma 2.2). Since \(B_2^*\) is the boundary of the region \(R_2^*\) of F, it follows that

\[\sum (\ell_F, B_2^*) = \ell_F(u) + \ell_F(v) + \sum (\ell_F, Q_2) + \sum (\ell_F, Q_3)\]\[= \ell(u) + \ell(v) + \sum (\ell, Q_2) + \sum (\ell, Q_3) = 0 \text{ in } \mathbb{Z}_3.\]

In the graph G, the value of the boundary \(B_1\) of \(R_1\) is \(\sum (\ell, B_1) = \sum (\ell_F, B_1^*) = 0\) in \(\mathbb{Z}_3\), the value of the boundary of \(R_2\) is

\[\sum (\ell, B_2) = \ell(u) + \ell(v) + \sum (\ell, Q_2) + \sum (\ell, Q_3) + \sum (\ell, U)\]\[= \sum (\ell_F, B_2^*) + \sum (\ell, U) = 0 + 0 = 0 \text{ in } \mathbb{Z}_3,\]

and the value of the boundary of \(R_3\) is \(\sum (\ell, B_3) = \sum (\ell_F, B_3^*) = 0\) in \(\mathbb{Z}_3\). Consequently, \(\ell\) is a zonal labeling of G.

Case 2. There is no path \(P_i\), i=1,2,3, every interior vertex of which has degree 2 in G. Hence, \(n_i \geq 3\) for i=1,2,3. In this case, we don't need the condition that \(n_1 \leq n_2 \leq n_3\). Let U=V(G)-V(F). For each integer i with \(1 \leq i \leq 3\), let \(U_i \subseteq U\) consist of those vertices belonging to any branch at an interior vertex of \(P_i\). In addition, let \(U_0 \subseteq U\) consist of those vertices belonging to any branch at u or v. Thus, \(|U_i| \geq 1\) for i=1,2,3 and \(|U_0| \geq 0\). We consider two subcases.

Subcase 2.1. There is an integer \(i \in \{1,2,3\}\) such that \(|U_0 \cup U_i| \ge 2\). Since we don't use the condition that \(n_1 \le n_2 \le n_3\), we may assume that \(|U_0 \cup U_1| \ge 2\). We embed G in the plane in such a way that the boundary of \(R_1\) consists of \(P_1\) and \(P_2\), the boundary of \(R_2\) consists of \(P_2\), \(P_3\), and every branch at any interior vertex of \(P_2\) and \(P_3\), and the boundary of \(R_3\) consists of \(P_1\), \(P_3\), and every branch at any vertex of \(P_1\) (including U and U) (see Figure 6, for example, where \(|U_0| = 1\), \(|U_1| = 3\), \(|U_2| = 1\), and \(|U_3| = 4\)). Since \(u_i \ge 3\) for \(u_i = 1, 2, 3\), it follows that \(u_i = 1, 2, 3\)0 is a graph of cycle rank 2 and type (3) that satisfies the conditions of Subcase 1.2. Thus, \(u_i = 1, 2, 3, 3, 3\)1 is zonal. Let \(u_i = 1, 3, 3, 3, 3, 3\)2 and the labeling \(u_i = 1, 3, 3, 3, 3, 3\)3 and the labeling \(u_i = 1, 3, 3, 3, 3\)4 for \(u_i = 1, 3, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i = 1, 3\)5 for \(u_i\)

Figure 6. An embedding of the graph G in Subcase 2.1

Subcase 2.2. For each \(i \in \{1,2,3\}\), \(|U_0 \cup U_i| = 1\). Since \(|U_i| \ge 1\) for i=1,2,3, it follows that \(U_0 = \emptyset\) and \(|U_1| = |U_2| = |U_3| = 1\). For i=1,2,3, let \(U_i = \{w_i\}\) and so \(w_i\) is adjacent to an interior vertex of \(P_i\). We embed the graph G in the plane in such a way that \(w_i\) belongs to \(R_i\) for i=1,2,3. We now define a labeling \(\ell\) of G by letting \(\ell(u) = \ell(v) = 1\) and \(\ell(w_i) = 2\) for i=1,2,3 such that \(\sum (\ell,Q_i) = 1\) in \(\mathbb{Z}_3\) for i=1,2,3 by Lemma 2.2. The value of the boundary of \(R_i\) (i=1,2,3) is \(\ell(u) + \ell(v) + \ell(w_i) + \sum (\ell,Q_i) + \sum (\ell,Q_j) = 1 + 1 + 2 + 1 + 1 = 0\) in \(\mathbb{Z}_3\), where \(j \in \{1,2,3\} - \{i\}\). Consequently, \(\ell\) is a zonal labeling of G.

Combining the results on graphs of a cycle rank 2 and type (3), we have the following characterization of zonal graphs of a cycle rank 2 and type (3).

Corollary 3.7. Let G be a graph of a cycle rank 2 and type (3) containing three internally disjoint paths of order \(n_i\) for i=1,2,3 where \(2 \le n_1 \le n_2 \le n_3\) and \(n_2 \ge 3\). Then G is zonal if and only if G is not minimal or G is minimal and \((n_1, n_2) \ne (2, 3)\).

As a consequence of Theorem 3.1 and 3.2, and Corollary 3.7, we present the following characterization of those graphs of a cycle rank 2 that are zonal.

Theorem 3.8. Let G be a graph of a cycle rank 2.

• (1) If G is of type (1), then G is zonal if and only if G is not minimal.
• (2) If G is of type (2), then G is zonal if and only if either every vertex of G belongs to a cycle of G or at least two vertices of G belong to no cycle of G.
• (3) If G is of type (3) with three internally disjoint paths of order \(n_i\) for i = 1, 2, 3 where \(2 \le n_1 \le n_2 \le n_3\) and \(n_2 \ge 3\), then G is zonal if and only if G is not minimal or G is minimal and \((n_1, n_2) \ne (2, 3)\).

While every planar embedding of a zonal graph of cycle rank 0 or 1 is zonal, this is not case for zonal graphs of cycle rank 2. For example, consider the two zonal graphs \(H_1\) and \(H_2\) of cycle rank 2 in Figure 7. Each of \(H_1\) and \(H_2\) has exactly two distinct planar embeddings, as shown in Figure 7. Thus, every planar embedding of the zonal graph \(H_1\) is zonal (where a zonal labeling of each planar embedding of \(H_1\) is also shown in that figure); while this is not true for the zonal graph \(H_2\) (since one of the two planar embeddings of \(H_2\) is not zonal). Observe that each of \(H_1\) and \(H_2\) has the form \(F \star K_2\) for some minimal graph F of cycle rank 2. We close with the following result dealing with minimal graphs of cycle rank 2, which we state without proof.

Figure 7. Two planar embeddings of two zonal graphs

Theorem 3.9. Let F be a minimal graph of cycle rank 2.

• (1) If F is of type (1), then every planar embedding of \(F \star K_2\) is zonal.
• (2) If F is of type (2) such that at least one vertex of F belongs to no cycle in F, then every planar embedding of \(F \star K_2\) is zonal.
• (3) If F is of type (3), then the following hold:
  • (3.1) If F is zonal, then every planar embedding of \(F \star K_2\) is zonal.
  • (3.2) If F is not zonal and w is the only vertex of \(F \star K_2\) that does not belong to F, then every planar embedding of \(F \star K_2\) is zonal if and only if w is adjacent to a vertex not on any triangle of F.

4. Closing Remarks on Graphs of Cycle Rank 3

Recall for a connected graph G of order n and size m that the number m-n+1 is called the cycle rank of G. Since \(K_{3,3}\) is a graph of cycle rank 4 and \(K_5\) is a graph of cycle rank 6, it follows by Kuratowski's theorem [6] that every graph of cycle rank 3 is planar. Results that have been obtained on graphs of cycle rank 0, 1, 2 give rise to the following question: Which graphs of cycle rank k, \(k \ge 3\), are zonal? The following result was proved in [1].

Proposition 4.1. Every 2-connected bipartite plane graph is zonal.

We now present some observations on 2-connected graphs of cycle rank 3.

Proposition 4.2. There are infinitely many 2-connected zonal graphs of cycle rank 3.

Proof. Let H be a 2-connected bipartite graph of cycle rank 3 and let \(E_0\) be a set of edges of H. If G is a graph obtained by subdividing each edge of \(E_0\) an even number of times, then G is a 2-connected bipartite graph of cycle rank 3. Thus, G is zonal by Proposition 4.1. In fact, if H is any 2-connected zonal graph of cycle rank 3 and a set \(E_0\) be a set of edges of H, then the graph

obtained by subdividing each edge of \(E_0\) at least twice is a 2-connected zonal graph of cycle rank 3 by Lemma 2.2. Hence, there are infinitely many 2-connected zonal bipartite or non-bipartite graphs of cycle rank 3.

If all edges of a 2-connected bipartite graph of cycle rank 3 are subdivided a number of times of the same parity, then the resulting graph is a 2-connected bipartite graph of cycle rank 3 and so is zonal Proposition 4.1. Thus, we have the following result.

Proposition 4.3. Let H be a 2-connected bipartite graph of cycle rank 3. If all edges of H are subdivided a number of times of the same parity, then the resulting graph is zonal.

Proposition 4.4. There are infinitely many 2-connected non-zonal graphs of cycle rank 3.

Proof. The 2-connected graph G of Figure 8 has cycle rank 3 and is non-zonal.

Figure 8. A 2-connected non-zonal graph of cycle rank 3

Any graph obtaining by subdividing the edge xy of the graph G of Figure 8 any number of times is a 2-connected graph of cycle rank 3. We show that each such graph is non-zonal as well. To see this, let H be a graph obtained by subdividing the edge xy of G one or more times. Consequently, H is obtained from G by replacing the edge xy of G by an x-y path P of length 2 or more. Assume, to the contrary, that H has a zonal labeling \(\ell\). Since three vertices in a triangle of H must be labeled the same, we may assume \(\ell(x) = \ell(u) = \ell(v) = \ell(w) = \ell(y) = 1\) by Observation 2.1. Let X = V(H) - V(G). Since the 3-path (x, v, y) and P form the boundary of an interior region of H, it follows that \(\ell(x) + \ell(v) + \ell(y) + \sum (\ell, X) = 3 + \sum (\ell, X) = 0\) in \(\mathbb{Z}_3\) and so \(\sum (\ell, X) = 0\). On the other hand, the 5-path (x, u, v, w, y) and P form the boundary of the exterior region of H and so \(\ell(x) + \ell(u) + \ell(v) + \ell(w) + \ell(y) + \sum (\ell, X) = 5 + \sum (\ell, X) = 2 \neq 0\) in \(\mathbb{Z}_3\), which is impossible. Therefore, H is not zonal.

We conclude with the following problem.

Problem 4.5. Characterize the zonal planar graphs of cycle rank 3.

Acknowledgement

We thank the anonymous referee whose valuable suggestions resulted in an improved paper.

References

• [1] A. Bowling and P. Zhang, Absolutely and conditionally zonal graphs. Electron. J. Math. 4 (2022), 1–11.
• [2] A. Bowling and P. Zhang, Inner zonality in graphs Int. J. Comput. Math: Computer Systems Theory. 7 (2022), 192-206.
• [3] G. Chartrand, C. Egan, and P. Zhang, How to Label a Graph. Springer, New York (2019).
• [4] G. Chartrand, C. Egan, and P. Zhang, Zonal graphs revisited. Bull. Inst. Combin Appl. 99 (2023). To appear.
• [5] G. Chartrand and P. Zhang, Chromatic Graph Theory. Second Edition. Taylor & Francis/CRC Press, Boca Raton (2020).
• [6] K. Kuratowski, Sur le probleme des courbes gauches en topologie. ` Fund. Math. 15 (1930), 271–283.