Peter Recht^a , Stefan Stehling^b

^aTechnische Universitt Dortmund Operations Research und Wirtschaftsinformatik Vogelpothsweg 87 44221 Dortmund Germany ^bRWE Supply & Trading GmbH Risk Supply and Capacity Altenessener Str. 27 45141 Essen Germany

peter.recht@tu-dortmund.de, stefan.stehling@rwe.com

This paper addresses upper and lower bounds for the cardinality of a maximum vertex-/edgedisjoint cycle packing in a polyhedral graph G. Bounds on the cardinality of such packings are provided, that depend on the size, the order or the number of faces of G, respectively. Polyhedral graphs are constructed, that attain these bounds.

Keywords: Maximum cycle packing, polyhedral graphs, vertex-disjoint cycles, edge-disjoint cycle

1. Introduction

Packing vertex- or edge-disjoint cycles in graphs is also a widely studied graph-theoretical problem. A large amount of literature can be found concerning conditions that are sufficient for the existence of some number of disjoint cycles which may satisfy further restrictive conditions.

Received: 10 October 2013, Revised: 5 January 2014, Accepted: 14 January 2014.

For examples, we refer to publications [6], [9], [10], [12], [15], [16], [18], [20], [21], [23], [24]. The algorithmic problems concerning cycle packings are typically hard ([5], [11], [20]) and approximation algorithms are described ([11], [17]). Several authors mention practical applications in computational biology ([3], [8], [13]) or the design of optical networks ([1]). In this paper, we investigate maximum cycle packings in polyhedral graphs G. We derive different bounds on the cardinality of such packings depending on the size of G, the order of G and the number of faces of G, respectively. As our main result we show that the bounds are sharp in the sense that we construct corresponding polyhedral graphs attaining these bounds.

2. Preliminaries and basic definitions

In the sequel all graphs G will be finite and undirected with vertex set V(G) and edge set E(G) that contains no loops or multiple edges. We recall some basic notions. If an edge \(e \in E(G)\) has two incident vertices u and v we write e = (u, v). For finite sequence \((v_{i_0}, e_0, v_{i_1}, e_1, \ldots, e_{r-1}, v_{i_r})\) of vertices \(v_{i_j} \in V(G)\) and pairwise disjoint edges \(e_j = (v_{i_j}, v_{i_{j+1}}) \in E(G)\) the subgraph W of G with vertex set V(W) and edge set E(W) is called a walk of length r with start vertex \(v_{i_0}\) and end vertex \(v_{i_r}\). A path \(P(v_{i_0}, v_{i_r})\) is a walk in which all vertices v have degree \(\delta_W(v) \leq 2\). If \(P(v_{i_0}, v_{i_r})\) is closed, i.e. \(v_{i_0} = v_{i_r}\), it is called a cycle. A graph G is k-vertex-connected if for each pair \(u, v \in V(G)\) there are k paths \(P_i(u, v)\) in G that mutually have no common vertices, except u and v. In addition, G is called Eulerian if it is connected and all vertices have even degree. An independent set in G is a subset of V(G) without edges between them. A vertex-disjoint (edge-disjoint) cycle packing \(C(G) = \{C_1, C_2, \ldots, C_q\}\) of G is a collection of cycles \(C_i\) of G such that all \(C_i\) are mutually vertex-disjoint (edge-disjoint). The maximum cardinality of a vertex-disjoint (edge-disjoint) cycle packing of G is denoted by v(G) or v'(G), respectively. A related packing is called maximum vertex-disjoint (edge-disjoint) cycle packing is

A planar graph is a graph G which can be drawn in a plane without any mutual crossings of edges. In a plane drawing an area F that is surrounded by edges of G is called a face of G. E(F) are the surrounding edges. The set of faces is denoted by F(G). If G is planar and connected Euler formula holds (see [19]), i.e. n-m+f=2, where n=|V(G)| denotes the order of G, m=|E(G)| its size and f=|F(G)| the number of faces, respectively. It is well known (see [2], [22]) that every planar graph has a 4-coloring of its vertices, and in consequence, every planar graph G has an independent set of size at least |V(G)|/4.

A graph G, resulting from a stereographic projection of vertices and edges of a convex polyhedron \(P \subset \mathbb{R}^3\) into the plane \(\mathbb{R}^2\) is called a polyhedral graph. The set of polyhedral graphs will be denoted by \(\mathcal{P}\). Due to the Theorem of Steinitz (see [4]) G is a polyhedral graph if and only if G is planar and 3-connected. The class of polyhedral graphs is a well investigated field in graph theory. The fundamental relation between geometry and graph theory in the class \(\mathcal{P}\) has generated a large variety of results concerning different topics. For a comprehensive overview we refer to [14] and [25].

3. Vertex-disjoint cycle packings in polyhedral graphs

In this section we give bounds on the cardinality of maximum vertex-disjoint cycle packings. These bounds depend on n, m or f. It turns out that the provided bounds are sharp, in the sense

that there exist polyhedral graphs that attain the bounds. For \(n, f \geq 4, m = 6\) or \(m \geq 8\) let \(\mathcal{PV}_n := \{G \in \mathcal{P} \mid |V(G)| = n\}\) denote the set of polyhedral graphs of size \(n, \mathcal{PE}_m := \{G \in \mathcal{P} \mid |E(G)| = m\}\) the set of these graphs of order m and \(\mathcal{PF}_f := \{G \in \mathcal{P} \mid |F(G)| = f\}\) the set of polyhedral graphs with f faces, respectively. First, we make the following observation

Lemma 3.1. For a polyhedral graph G the following holds:

\[1 \le \nu(G) \le \left| \frac{n}{3} \right| \le \left| \frac{2m}{9} \right| \le \left| \frac{2(f-2)}{3} \right|.\]

Proof. Obviously, \(1 \le \nu(G)\) holds since \(f \ge 1\) for \(G \in \mathcal{P}\). By the fact that all cycles in G have length greater or equal to 3, immediately \(\nu(G) \le \left\lfloor \frac{n}{3} \right\rfloor\) follows. Using Euler formula and the property that \(3n \le 2m\) is true for \(G \in \mathcal{P}\) we get

\[\frac{n}{3} \le \frac{2m}{9} = \frac{6m - 4m}{9} \le \frac{2(m-n)}{3} = \frac{2(f-2)}{3}.\]

In the following we want to examine, whether these bounds are sharp in the classes \(\mathcal{PV}_n, \mathcal{PE}_m\) and \(\mathcal{PF}_f\), respectively. In Figure 1 polyhedral graphs \(G_1, \ldots, G_{10}\) are drawn, which belong to \(\mathcal{PE}_m, m = 6\) or \(8 \le m \le 16\), to \(\mathcal{PV}_n, n \in \{4, 5, 6, 7, 8, 9\}\) and to \(\mathcal{PF}_f, f \in \{4, 5, 6, 7\}\). Obviously, \(\nu(G_i) = \left\lfloor \frac{n}{3} \right\rfloor = \left\lfloor \frac{2m}{9} \right\rfloor, i \in \{1, \ldots, 10\}\) and \(\nu(G_i) = \left\lfloor \frac{2(f-2)}{3} \right\rfloor, i \in \{1, 3, 4, 5, 6, 8, 9\}\).

Figure 1. Graphs \(G_i\), \(i \in \{1, 2, ..., 10\}\), used for induction in Proposition 3.1.

A vertex-disjoint cycle packing in \(G_i\) is indicated by bold edges. Moreover, each of the graphs \(G_2, G_3, \ldots, G_{10}\) has a face F such that \(|E(F)| \geq 4\) (shaded area) and for which two of the edges \(e_1, e_2 \in E(F)\) (dotted edges) do not belong to the maximum cycle packing. These graphs are used in order to show

Proposition 3.1. The following is true:

• (i) for \(n \geq 4\), there is \(G \in \mathcal{PV}_n\) such that \(\nu(G) = \lfloor \frac{n}{3} \rfloor\),
• (ii) for m = 6 or \(m \ge 8\), there is \(G \in \mathcal{PE}_m\) such that \(\nu(G) = \left\lfloor \frac{2m}{9} \right\rfloor\),
• (iii) for \(f \geq 4\), there is \(G \in \mathcal{PF}_f\) with \(\nu(G) = \left| \frac{2(f-2)}{3} \right|\).

Proof. Let us use the planar graph T, drawn in Figure 2.

Figure 2. Graph T used for the iterative step in Proposition 3.1.

Now, consider \(G \in \mathcal{P}\) such that G contains a face F with \(|E(F)| \geq 4\). Let \(e_1, e_2\) denote two non-adjacent edges of F. Thus, we define \(G'(e_1, e_2) := G \oplus T\) by identifying the edges \(e_1 = (u_1, v_1)\) with the path \((u_1, s_1, t_1, v_1)\) and \(e_2 = (u_2, v_2)\) with \((u_2, s_2, t_2, v_2)\), respectively, and embedding T into the interior of the face F. Then, \(|V(G'(e_1, e_2))| = |V(G)| + 6\), \(|E(G'(e_1, e_2))| = |E(G)| + 9\) and \(|F(G'(e_1, e_2))| = |F(G)| + 3\). Clearly, \(G'(e_1, e_2) \in \mathcal{P}\), since it is planar and 3-connected. We show not only that \(\nu(G) = \left\lfloor \frac{2m}{9} \right\rfloor\), but also that there is always a face F in G such that \(|E(F)| \geq 4\) and for which two non adjacent edges \(e_1, e_2 \in E(F)\) do not belong to a maximum cycle packing of G.

(i) This assertion is true for \(8 \le m \le 16\), since each of the graphs \(G_2, \ldots, G_{10}\) has a face F such that \(|E(F)| \ge 4\) (shaded area) and for which two non adjacent edges \(e_1, e_2 \in E(F)\) (dotted edges) do not belong to a maximum cycle packing of G (bold edges). In order to use induction arguments, we assume, that it is true for some \(G \in \mathcal{PE}_m\). Let \(\nu(G) = \left\lfloor \frac{2m}{9} \right\rfloor\) and \(\mathcal{C}(G)\) be a corresponding vertex-disjoint cycle packing. Clearly, \(G'(e_1, e_2) \in \mathcal{PE}_{m+9}\), since it is planar and 3-connected. For \(C_1 = (s_1, t_1, w_1, s_1)\) and \(C_2 = (s_2, t_2, w_2, s_2)\) the set \(\mathcal{C}(G'(e_1, e_2)) = \mathcal{C}(G) \cup \{C_1, C_2\}\) is a vertex-disjoint cycle packing of \(G'(e_1, e_2)\) with \(|\mathcal{C}(G'(e_1, e_2))| = \nu(G) + 2\) which is maximal, since

\[|\mathcal{C}(G'(e_1, e_2))| \le \nu(G'(e_1, e_2)) \le \left\lfloor \frac{2(m+9)}{9} \right\rfloor = \nu(G) + 2.\]

Moreover, \(e'_1 = (u_1, s_1)\) and \(e'_2 = (u_2, s_2)\) are two non adjacent edges of the boundary of the same face \(F' \in G'\). Since \(\{e'_1, (s_1, w_1), (w_1, w_2), (w_2, s_2), e'_2\} \in E(F')\).

(ii) Using the graphs \(G_i\) with \(i \in \{2, 3, 5, 6, 8, 9\}\) from Figure 1 the assertion holds for graphs \(G \in \mathcal{PV}_n\), \(5 \le n \le 10\). Performing the same induction arguments as in (i), we get (ii).

(iii) The graphs \(G_i\) with \(i \in \{2, 4, 7\}\) show that the assertion is true for \(G \in \mathcal{PV}_f\), \(5 \le f \le 7\). Again, we perform the same induction arguments as in (i) to get (iii).

With respect to the lower bound \(\nu(G) > 1\) of a polyhedral graph G we remark

Remark 3.1. A wheel \(W_n\) on \(n \ge 4\) vertices is a graph with n vertices \(v_1, \ldots, v_n\) with \(v_1\) having degree n-1 and all the other vertices having degree 3. The vertex \(v_1\) is adjacent to vertices, and for \(i \in \{2, \ldots, n-1\}\), \(v_i\) is adjacent to \(v_{i+1}\), and \(v_n\) is adjacent to \(v_2\).

• Obviously, \(\nu(W_n) = 1\). In [7] it is shown that for 3-connected planar graphs with more than 5 vertices wheels are the only graphs with \(\nu(G) = 1\).
• Since \(W_n\) is self-dual, \(W_n \in \mathcal{PV}_n \cap \mathcal{PF}_n\), \(n \geq 4\), i.e. wheel graphs \(W_n\) attain the minimum cardinality of a maximum cycle packing in the classes \(\mathcal{PV}_n\) and \(\mathcal{PF}_f\), \(n, f \geq 4\), respectively.
• As \(|E(W_n)| = 2(n-1)\), \(W_n\) is also the graph that minimizes the cardinality of a maximum cycle packing in the set \(\mathcal{PE}_m\), \(m \geq 6\) and even m.
• To investigate \(\mathcal{PE}_m\), \(m \geq 11\) and odd m we observe, that \(W_{\frac{m+1}{2}} \in \mathcal{PE}_{m-1}\). Since \(v_2, v_3\) are adjacent in \(W_{\frac{m+1}{2}}\), there are two nonadjacent vertices \(v_i, v_j\), different from \(v_2, v_3\) and a path \(P(v_i, v_j) \in W_{\frac{m+1}{2}}\) not containing \(\{v_1, v_2, v_3\}\). We now define \(G \in \mathcal{PE}_m\) by

\[G = W_{\frac{m+1}{2}} \cup \{(v_i, v_j)\}.\]

Then \(C_1 = (v_1, v_2, v_3, v_1)\) and \(C_2 = P(v_i, v_j) \cup \{(v_i, v_j)\}\) are two vertex-disjoint cycles in G, i.e. the minimal cardinality in this class is 2.

• In addition, \(\nu(G) = 1\) holds for \(G \in \mathcal{PE}_9 \cap \mathcal{PV}_5\) with Lemma 3.1.

4. Edge-disjoint cycle packings in polyhedral graphs

In the following section upper and lower bounds for the cardinality of maximum edge-disjoint cycle packings are established. It is shown that in almost all cases they are sharp.

Lemma 4.1. For \(G \in \mathcal{P}\) the following holds:

\[(i) \quad \max\left\{\left\lceil \frac{f}{4}\right\rceil, \left\lceil \frac{m+6}{12}\right\rceil, \left\lceil \frac{n+4}{8}\right\rceil\right\} \le \nu'(G),\]

(ii) \[1 \le \nu'(G) \le \min\left\{n-2, \left\lfloor \frac{m}{3} \right\rfloor, \left\lfloor \frac{2(f-2)}{3} \right\rfloor\right\}.\]

Proof. (i) Let \(G^*\) be the dual graph of a plane drawing of G. \(G^*\) is the graph drawn by placing a new vertex inside each face of G and connecting these vertices in \(G^*\) whenever the corresponding two faces share an edge in G. As G is 3-connected, \(G^*\) is simple and planar and therefore, has an independent set S of vertices of size \(|S| \geq \frac{f}{4}\). Hence, \(\nu'(G) \geq \left\lceil \frac{|F(G)|}{4} \right\rceil\). Moreover, \(f \geq \frac{n+4}{2}\) and \(f \geq \frac{m+6}{3}\). By this immediately (i) follows.

(ii) Obviously, 1 ≤ ν 0 (G) holds, since f ≥ 4 for G ∈ P. Now, let cⁱ = |{v ∈ G|δG(v) = i}|, i ∈ {3, 4, 5, . . .} and ∆ := max{δG(v)|v ∈ V }. By c we denote the number of vertices of odd degree. By the two facts that all cycles in G have at least a length of 3 and there are at least ¹ 2 c edges that cannot belong to any maximum cycle packing it follows

\[\nu'(G) \le \left\lfloor \frac{m - \frac{1}{2}c}{3} \right\rfloor \le \left\lfloor \frac{m}{3} \right\rfloor \le n - 2.\]

More sophisticated, we get

\[m - \frac{1}{2}c = \frac{1}{2} \left( \sum_{i=3, i \text{ odd}}^{\Delta} ic_i + \sum_{i=3, i \text{ odd}}^{\Delta} ic_i - \sum_{i=3, i \text{ odd}}^{\Delta} c_i \right)\] \[= \frac{1}{2} \left( \sum_{j=1}^{\Delta} (2j+1)c_{2j+1} + \sum_{j=2}^{\Delta} 2jc_{2j} - \sum_{j=1}^{\Delta} c_{2j+1} \right)\] \[= \frac{1}{2} \left( \sum_{j=1}^{\Delta} 2jc_{2j+1} + \sum_{j=2}^{\Delta} 2jc_{2j} \right) = \sum_{j=1}^{\Delta} jc_{2j+1} + \sum_{j=2}^{\Delta} jc_{2j}\] \[\leq \sum_{i=1}^{\Delta} (i-2)c_i = 2m - 2n = 2(f-2)\]

from which we conclude ν 0 (G) ≤ j 2(f−2) 3 k .

Remark 4.1. The graphs ^G ∈ PF^f attaining the upper bound ^ν(G) = ^j 2(f−2) 3 k according to Proposition 3.1, of course, attain the upper bound ν 0 (G) = j 2(f−2) 3 k . This follows, since every vertex-disjoint cycle packing of G induces an edge-disjoint cycle packing.

Again, we show that also the two other bounds in Lemma 4.1 are sharp for graphs in PE^m and PVn, respectively. More precisely we prove

Proposition 4.1. The following is true:

• (i) for n = 6 or n ≥ 8 there is G ∈ PVⁿ with ν 0 (G) = n − 2,
• (ii) for m ∈ {8, 11, 12, 13, 14} or m ≥ 16 there is G ∈ PE^m with ν 0 (G) = ^m 3 .

Proof. For the proof induction arguments are used. For this we first consider the planar graph D, drawn in Figure 3. Obviously, δD(u) = δD(v) = δD(w) = 2. For a planar graph G that contains a triangle C = (¯u, v, ¯ w, ¯ u¯), which is also a face F of G, we define G⁰ (¯u, v, ¯ w¯) := G ⊕ D by identifying the vertices {u, ¯ v, ¯ w¯} with the vertices {u, v, w}, and embedding D into the interior of the face F.

Figure 3. Graph D used for the iterative step in Proposition 4.1.

(i) We will show not only that \(\nu'(G) = |V(G)| - 2\), but it also has a maximum edgedisjoint cycle packing C, that contains a cycle \(C = (\bar{u}, \bar{v}, \bar{w}, \bar{u})\), which is also a face F of G. The assertion is true for \(n \in \{6, 8, 10\}\). The corresponding graphs \(G_i\) with \(i \in \{3, 7, 9\}\) are listed in Figure 4. In order to use induction arguments, let us assume that it is true for

Figure 4. Plane drawings with \(\nu'(G) = \min\left\{n-2, \left\lfloor \frac{m}{3} \right\rfloor, \left\lfloor \frac{2(f-2)}{3} \right\rfloor\right\}\).

some \(G \in \mathcal{FV}_n, n \geq 11\), i.e. \(\nu'(G) = n-2\), and there is a maximum edge-disjoint cycle packing \(\mathcal{C}\) of G such that it contains a cycle \(G = (\bar{u}, \bar{v}, \bar{w}, \bar{u})\), which is also a face F of G. Define \(G' := G'(\bar{u}, \bar{v}, \bar{w}) = G \oplus D\). Clearly, \(G' \in \mathcal{PV}_{n+3}\), since it is planar and 3-connected. Moreover, there is an edge-disjoint cycle packing \(\mathcal{C}'\) of G', given by

\[C' = C \cup \{u, s, t, u\} \cup \{v, s, r, v\} \cup \{w, r, t, w\},\]

i.e. \[\nu'(G') \ge \nu'(G) + 3 = (|V(G)| - 2) + 3 = |V(G')| - 2\]. With Lemma 4.1 \(\nu'(G') =\)

|V(G')| - 2 follows. Moreover, each of the three additional cycles is the boundary of a face of G'.

(ii) As before, we show not only that \(\nu'(G) = \left\lfloor \frac{|E(G)|}{3} \right\rfloor\), but it also has a maximum edge-disjoint cycle packing \(\mathcal{C}\), that contains a cycle \(C = (\bar{u}, \bar{v}, \bar{w}, \bar{u})\), which is also a face F of G. This is true for \(m \in \{8, 11, 12, 13, 14, 16, 18, 19, 24\}\). Corresponding graphs are listed in Figure 4. In order to use induction arguments, let us assume that it is true for some \(G \in \mathcal{PE}_m, m \geq 16\), i.e. \(\nu'(G) = \left\lfloor \frac{m}{3} \right\rfloor\), and there is a maximum edge-disjoint cycle packing \(\mathcal{C}\) of G such that it contains a cycle \(C = (\bar{u}, \bar{v}, \bar{w}, \bar{u})\), which is also a face F of G. Again, set \(G' = G'(\bar{u}, \bar{v}, \bar{w}) = G \oplus D\). Clearly, \(G' \in \mathcal{PE}_{n+9}\), since it is planar and 3-connected. Moreover, there is a maximum edge-disjoint cycle packing \(\mathcal{C}'\) of G', given by

\[C' = C \cup \{u, s, t, u\} \cup \{v, s, r, v\} \cup \{w, r, t, w\},\\]

i.e. \(\nu'(G') \ge \nu'(G) + 3 = \left\lfloor \frac{|E(G)|}{3} \right\rfloor + 3 = \left\lfloor \frac{|E(G)|+9}{3} \right\rfloor = \left\lfloor \frac{|E(G')|}{3} \right\rfloor\). Again, \(\nu'(G') = \left\lfloor \frac{|E(G')|}{3} \right\rfloor\) follows. Moreover, each of the three additional cycles is the boundary of a face of G'.

Immediately we deduce

Corollary 4.1. There are infinitely many \(n \in \mathbb{N}\) for which there is \(G \in \mathcal{PV}_n\) such that

\[\nu'(G) = n - 2 = \left| \frac{m}{3} \right| = \left| \frac{2(f-2)}{3} \right|.\] (1)

Proof. An easy calculation shows, that (1) is true for the octahedron \(G \in \mathcal{PV}_6 \cap \mathcal{PE}_{12} \cap \mathcal{PF}_8\). Using the construction scheme of the last proposition for induction we get that \(G' \in \mathcal{PV}_{|V(G)|+3} \cap \mathcal{PE}_{|E(G)|+9} \cap \mathcal{PF}_{|F(G)|+6}\), from which

\[\nu'(G') = |V(G')| - 2 = \left\lfloor \frac{|E(G')|}{3} \right\rfloor = \left\lfloor \frac{2(|F(G')| - 2)}{3} \right\rfloor\]

follows. \(\Box\)

Remark 4.2. The upper bounds in Proposition 4.1 with respect to m and n are not sharp in the cases \(G \in \mathcal{PE}_m, m \in \{6,9,10,15\}\) and \(G \in \mathcal{PV}_n, n \in \{4,5,7\}\). This is true for \(m \in \{6,9,10,15\}\), because according to Lemma 4.1 a necessary condition for graphs \(G \in \mathcal{PE}_m, m \in \{6,9,15\}\) to attain \(\nu'(G) = \left\lfloor \frac{m}{3} \right\rfloor\) is to be Eulerian. A necessary condition for \(G \in \mathcal{PE}_{10}\) to attain \(\nu'(G) = 3\) is that it has most two vertices of odd degree. But these conditions are not satisfied: to realize this, we first observe that \(G \in \mathcal{PE}_6\) implies |V(G)| = 4 and \(G \in \mathcal{PE}_9\) implies \(|V(G)| \in \{5,6\}\), respectively. If \(G \in \mathcal{PE}_{10}\) |V(G)| = 6 and for \(G \in \mathcal{PE}_{15}\) implies \(|V(G)| \in \{7,\dots,10\}\). Investigation of all cases show that

• a graph \(G \in \mathcal{PE}_{10}\) has at least 4 vertices of odd degree,

• a 3-connected Eulerian graph G with |V(G)| = 7, |E(G)| = 15 contains \(K_{3,3}\), hence it is not planar,
• all remaining cases lead to graphs which are non-Eulerian.

A similar consideration shows that for the cases \(n \in \{4,5,7\}\) the bound n-2 cannot be attained by graphs \(G \in \mathcal{PV}_n\). Graphs \(G \in \mathcal{PE}_m, m \in \{6,9,10,15\}\) satisfying \(\nu'(G) = \left\lfloor \frac{m}{3} \right\rfloor - 1\) and graphs \(G \in \mathcal{PV}_n, n \in \{4,5,7\}\) satisfying \(\nu'(G) = n-3\) are listed in Figure 5.

Figure 5. Plane drawings of \(G_i \in \mathcal{PE}_m\) for \(m \in \{6, 9, 10, 15\}\) with the property \(\nu'(G) = \lfloor \frac{m}{3} \rfloor - 1\).

For the lower bounds of the cardinality of maximum cycle packings we proof the following result

Proposition 4.2. The following is true:

• (i) for \(n \geq 4\) there is \(G \in \mathcal{PV}_n\), such that \(\nu'(G) = \left\lceil \frac{n+4}{8} \right\rceil\),
• (ii) for m = 6 or \(m \ge 8\) there is \(G \in \mathcal{PE}_m\), such that \(\nu'(G) = \left\lceil \frac{m+6}{12} \right\rceil\),
• (iii) for \(f \geq 4\) there is \(G \in \mathcal{PF}_f\), such that \(\nu'(G) = \left\lceil \frac{f}{4} \right\rceil\).

Proof. We first consider the planar graph S, drawn in the Figure 6. For a planar graph G that

Figure 6. Graph S used for the iterative step in Proposition 4.2.

contains a cycle \(C = (e_1, e_2, e_3, e_4)\), which is also a face F of G we define \(G'(e_1, e_2, e_3, e_4) := G \oplus S\) by subdividing each of the four edges \(e_i\), identifying the additional vertices with the vertices \(\{v_1, v_2, v_3, v_4\}\), and embedding S into the interior of F.

Figure 7. Plane drawings with \(\nu'(G) = \max\left\{\left\lceil\frac{n+4}{8}\right\rceil, \left\lceil\frac{m+6}{12}\right\rceil, \left\lceil\frac{f}{4}\right\rceil\right\}\).

(i) We show not only that \(\nu'(G)\) attains the bound, but also that in G exists at least one face which is bounded by four edges. The assertion is true for \(n \in \{4, 5, ..., 12\}\). The corresponding graphs \(G_i\) with \(i \in \{1, 2, 3, 5, 6, 9, 10, 12\}\) are listed in Figure 7.

In order to use induction arguments, let us assume that \(\nu'(G) = \left\lceil \frac{n+4}{8} \right\rceil\) is true for some \(G \in \mathcal{FV}_n, n \geq 4\), and there is a maximum edge-disjoint cycle packing \(\mathcal{C}\) of G such that it contains a cycle G of length 4 which is also a face F of G. Let \((e_1, e_2, e_3, e_4)\) be the boundary of F and set \(G' = G'(e_1, e_2, e_3, e_4) = G \oplus S\). Clearly, \(G' \in \mathcal{PV}_{n+8}\), since it is planar and 3-connected.

Moreover, there is an edge-disjoint cycle packing C' of G', given by

\[C' = C \cup \{(u_1, u_2, u_3, u_4)\},\\]

i.e. \(\nu'(G') \ge \nu'(G) + 1 = \left\lceil \frac{|V(G)| + 4}{8} \right\rceil + 1 = \left\lceil \frac{|V(G')| + 4}{8} \right\rceil\). The additional cycle is, of course, the boundary of a face F' of G'. It remains to show, that \(\nu'(G') = \nu'(G) + 1\).

Assume that is not the case. Then \(\nu'(G') \geq \nu'(G) + 2\). Let \(\mathcal{C}'\) be a corresponding maximum cycle packing. At least two of the cycles in \(\mathcal{C}'\) must contain edges of S. By the structure of S exactly two cycles, say \(C_1, C_2 \in \mathcal{C}'\), must have this property. Let \(v_1, v_2 \in V(C_1)\) and \(v_3, v_4 \in V(C_2)\), respectively. With \(\delta_S(v_i) = 3, i \in \{1, \ldots, 4\}\),

\[E(C) \cap (E(C') \setminus \{E(C_1), E(C_2)\}) = \emptyset,\]

i.e. \(C' \setminus \{C_1, C_2\} \cup C\) is an edge-disjoint cycle packing of G with cardinality of at least \(\nu'(G) + 1\), which contradicts \(\nu'(G)\) as cardinality of a maximum cycle packing of G. The embedding of G guarantees that G' has at least one face that is bounded by four edges.

• (ii) The proof is similar to (i). In this case we start with graphs G ∈ PEm, m ≥ 8 (the first thirteen graphs are drawn in Figure 7) and observe that G⁰ ∈ PEm+12.
• (iii) The proof is analogous to (i). We start with graphs G ∈ PF^f , f ≥ 4 (the first four graphs Gⁱ with i ∈ {1, 2, 4, 7} are drawn in Figure 7) and observe that G⁰ ∈ PFf+4.

The following proposition shows that the number of graphs G ∈ P with predefined ν(G) is in general large.

Proposition 4.3. Let k ≥ 1.

• (i) For n satisfying k + 3 ≤ n ≤ 8k − 4 there is a non-Eulerian G ∈ PVⁿ such that ν 0 (G) = k,
• (ii) for m satisfying 3k + 3 ≤ m ≤ 12k − 6 there is a non-Eulerian G ∈ PE^m such that ν 0 (G) = k,
• (iii) for f satisfying 3k 2 + 2 ≤ f ≤ 4k there is a non-Eulerian G ∈ PF^f such that ν 0 (G) = k.

Proof. The proof is done by induction. For k = 1 the assertion holds with graph G¹ from Figure 7 for (i), (ii) and (iii).

• (i) Assume that the assertion holds for k ≥ 1. We have to show that it is also true for k + 1, i.e. that for all n with (k + 1) + 3 ≤ n ≤ 8(k + 1) − 4 there is non-Eulerian G ∈ PVn, with ν 0 (G) = k + 1. We distinguish between two cases:
  • (a) Let k + 4 ≤ n ≤ 8k − 4: Then, for n 0 := n − 1, we get k + 3 ≤ n ⁰ ≤ 8n − 5. Hence, there is a non-Eulerian G⁰ ∈ PVn⁰ and ν 0 (G⁰ ) = k. Let C be a maximum cycle packing. There must be e = (u, v) ∈ E(G⁰ ) such that e /∈ E(C 0 ). Let F be the face of G⁰ such that e ∈ E(F). Define G := G⁰⊕K1,³ by embedding K1,³ into the interior of F in such a way, that u, v is identified with two of the vertices in K1,³ and the third vertex of K1,³ is identified with an arbitrary vertex w ∈ V (F) \ {u, v}. Obviously G ∈ PVn, G is non-Eulerian and ν 0 (G) = k + 1.
  • (b) Let 8k − 4 < n ≤ 8k − 4 + 8:

\[k = \frac{8k}{8} < \frac{n+4}{8} \le \frac{8k+8}{8} = k+1,\]

i.e. in these cases n+4 8 = k + 1. With Proposition 4.2, there is G ∈ PVⁿ with ν 0 (G) = k + 1. Moreover, by construction of G in Proposition 4.2, G is non-Eulerian.

(ii) The proof is performed analogously to (i), but instead of n ⁰ = n − 1 we here have to consider m⁰ = m−3 and have to distinguish between the cases (a) 3k + 3 ≤ m ≤ 6(2k −1) and (b) 6(2k − 1) ≤ m ≤ 6(2(k + 1) − 1), respectively.

(iii) We have to show that for l 3(k+1) 2 m + 2 ≤ f ≤ 4(k + 1) the assertion holds. First, let k be even, i.e. k + 1 ≥ 3 and l 3(k+1) 2 m + 2 = l 3k 2 m + 4. Again, we distinguish between (a) l 3k 2 m + 4 ≤ f ≤ 4k and (b) 4k < f ≤ 4k + 4. The same considerations as in (i) with f ⁰ = f − 2 instead of n ⁰ = n − 1 then proves the assertion. Secondly, if k is odd, we get l 3(k+1) 2 m + 2 = l 3k 2 m + 3. Here, we distinguish between the following two cases: (a) f = l 3k 2 m + 3, i.e. f = 3k ² + 1 ² + 3, from which k = 2(f−3) ³ − ³ = j 2(f−3) 3 k follows. Using Remark 4.1 there exists a non-Eulerian G ∈ PF^f such that ν 0 (G) = k. For the remaining cases (b) 3k 2 + 4 ≤ f ≤ 4k ≤ 4k + 4 the proof is performed as for the even case.

Remark 4.3. According to Remark 4.2, for the cases k = 4 or k ≥ 6 in Proposition 4.3

• in (i) even the sharper inequality k + 2 ≤ n ≤ 8k − 4 holds,
• in (ii) even the sharper inequality 3k ≤ m ≤ 6(2k − 1) holds.

Using G⁴ and G¹ from Figure 4, the construction scheme from Proposition 4.3, moreover, yields that

• for k ≥ 4 there is G ∈ PE ³k+1 such that ν 0 (G) = k,
• for k ≥ 2 there is G ∈ PE ³k+2 such that ν 0 (G) = k.

References

• [1] S. Antonakopulos and L. Zhang, Approximation algorithms for grooming in optical network design, Theor. Comp. Sci. 412(29) (2011), 3783–3751.
• [2] K. Appel and W. Haken, Every planar map is four colorable, Illinois Journal of Mathematics 21(3) (1977), 429–490,
• [3] V. Bafna and P.A. Pevzner, Genome rearrangements and sorting by reversals, Siam J. Comput. 25(2) (1996), 272–289.
• [4] D.W. Barnette and B. Grnbaum, On Steinitz's theorem concerning convex 3-polytopes and on some properties of planar graphs, 'The Many Facets of Graph Theory', G. Chartrand and S. F. Kapoor, eds. Lecture Notes in Math, Springer, Berlin-heidelberg-New York 110 (1969), 27–40.
• [5] A. Caprara, A. Panconesi and R. Rizzi, Packing cycles in undirected graphs, Journal of Algorithms 48 (2003) 239–256.

• [6] K.Corradi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hung, 14 (1963), 423–439.
• [7] G.A. Dirac, Some results concerning the structure of graphs, Can. Math. Bulltin, 6(2) (1963), 183–210.
• [8] N. El-Mabrouk, Genome rearrangement by reversals and insertion/deletions of contiguous segments, Combinatorial Pattern Matching, 1848 (2000), 222–234.
• [9] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica, 18 (1998), 487–492.
• [10] P. Erdos and L. P ˝ osa, On the maximal number of disjoint circuits of a graph, ´ Publ. Math. Debrecen, 9 (1962), 3–12.
• [11] Z. Friggstad and M.R. Salavatipour, Approximability of packing disjoint cycles, Proceedings of ISAAC 2007, Lecture Notes in Comput. Sci., 4835 (2007), 304–315.
• [12] S. Fujita, Recent results on disjoint cycles in graphs, Electronic Notes Discrete Math., 22 (2005), 409–412.
• [13] G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, Combinatorics of genome rearragements, MIT Press, Cambridge, Ma, (2009).
• [14] B. Grnbaum, Convex polytopes. Springer, 2nd ed., New York, 2003.
• [15] J. Harant, D. Rautenbach, P. Recht, and F. Regen, Packing edge-disjoint cycles in graphs and the cyclomatic number, Discrete Math. 310(9) (2010), 1456–1462.
• [16] J. Harant, D. Rautenbach, P. Recht, I. Schiermeyer and E.-M. Sprengel, Packing disjoint cycles over vertex cuts, Discrete Math. 310(13–14) (2010), 1974–1978.
• [17] M. Krivelevich, Z. Nutov, M.R. Salavatipour, J. Verstraete and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithms. 3(4) (2007), Art 48, 1–21.
• [18] J.W. Moon, On edge-disjoint cycles in a graph, Can. Math. Bull. 7 (1964), 519–523.
• [19] T. Nishizeki and N. Chiba, Planar graphs: theory and algorithms, Dover Publications, Inc., USA, 2008.
• [20] D. Rautenbach and F. Regen, On packing shortest cycles in graphs, Inf. Process. Lett. 109 (2009), 816–821.
• [21] P. Recht and E.-M. Sprengel, Packing Euler graphs with traces, Operations Research Proceedings 2011, (2011), 53–58.

• [22] N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem, Journal of Combinatorial Theory, Series B 70 (1997), 2–44.
• [23] M. Simonovits, A new proof and generalizations of a theorem of Erdos and P ˝ osa on graphs ´ without k + 1 independent circuits, Acta Math. Acad. Sci. Hung. 18 (1967), 191–206.
• [24] H. Wang, Maximal total length of k disjoint cycles in bipartite graphs, Combinatorica 25 (2005), 367–377.
• [25] G.M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics. Springer-Verlag, New York 152 (1994).