Printer Friendly

The complexity of [P.sub.4]-decomposition of regular graphs and multigraphs.

Let G denote a multigraph with edge set E(G), let [mu](G) denote the maximum edge multiplicity in G, and let [P.sub. k] denote the path on k vertices. Heinrich et al.(1999) showed that [P.sub. 4] decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. We show that [P.sub. 4] decomposes a connected 4-regular multigraph G with [mu](G) [less than or equal to] 2 if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Oksimets (2003) proved that for all integers k [greater than or equal to] 3, [P.sub. 4] decomposes a connected 2k-regular graph G if and only if |E(G)| is divisible by 3. We prove that for all integers k [greater than or equal to] 2, the problem of determining if [P.sub. 4] decomposes a (2k + 1)-regular graph is NP-Complete. El-Zanati et al.(2014) showed that for all integers k [greater than or equal to] 1, every 6k-regular multigraph with [mu](G) [less than or equal to] 2k has a [P.sub. 4]-decomposition. We show that unless P = NP, this result is best possible with respect to [mu](G) by proving that for all integers k [greater than or equal to] 3 the problem of determining if [P.sub. 4] decomposes a 2k-regular multigraph with [??] is NP-Complete.

Keywords: [P.sub. 4]-decomposition, multigraphs, NP-complete

1 Introduction

For integers i and j with i [less than or equal to] j, let [i,j] denote the set {i, i + 1,..., j}. A graph has no multiple edges or loops while a multigraph is allowed to have multiple edges but has no loops. Let G be a multigraph with vertex set V(G) and edge set E(G). The multiplicity of an edge (u, [nu]) [member of] E(G) is defined to be the number of edges joining u and v and is denoted by [mu](u[nu], G) and the maximum edge-multiplicity of G is denoted by [mu](G). We denote by [.sup.[lambda]]G the multigraph obtained from G by replacing each edge of G by [lambda] parallel edges. A path consisting of 3 edges (x, y), (y, z),and (z, w) is denoted by [P.sub. 4] and the edge (y, z) is called the central edge of [P.sub.4]. A decomposition of a multigraph G is a partition of its edge set into edge disjoint subgraphs [H.sub.1],[H.sub.2],..., [H.sub.k] of G; if each [H.sub.i], i [member of] [1, k] is isomorphic to a graph H then we have an H-decomposition of G and we say that H decomposes G. It is well known that every connected multigraph G with the degree of each of its vertices being even has an Euler tour; we say that such a multigraph is Eulerian. We will denote an Euler tour in G by the sequence of vertices visited by the tour. An Euler tour in a multigraph G is said to be a triangle-free Euler tour if no three consecutive edges in the Euler tour form a triangle in G. A ([C.sub.2], [C.sub.3])-free Euler tour in a multigraph G is a triangle-free Euler tour in which no two consecutive edges are a parallel pair in G.

We refer the reader to [2] for all terminology and notation that is not defined in this paper.

The following conjecture by Graham and Haggkvist [8] is the genesis of much of what we discuss in this paper.

Conjecture 1 [8] Every tree on m edges decomposes every 2m-regular graph.

In [8] Haggkvist described a method to prove the above conjecture for m = 3, i.e. that [P.sub.4] decomposes every 6-regular graph. M. Kouider and Z. Lonc [11] obtained a generalization of this result by showing that any path on m edges decomposes every 2m-regular graph G of girth g with m [less than or equal to] 2g - 3.

The following theorem independently due to Kotzig [10] and Bouchet and Fouquet [3] gives a necessary and sufficient condition for a cubic graph to have a [P.sub.4]-decomposition.

Theorem 1 [3] A cubic graph G has a [P.sub.4]-decomposition if and only if G has a 1-factor.

Heinrich et al. [9] proved the following theorem as a corollary of a theorem on triangle-free Euler tours in connected 4-regular graphs.

Theorem 2 [9] A connected 4-regular graph G has a [P.sub.4]-decomposition if and only if |E(G) | is divisible by 3.

In Section 2 of this paper we extend Theorem 2 by proving that a connected 4-regular multigraph G with [mu](G) [less than or equal to] 2 has a [P.sub.4]-decomposition if and only if no 3 vertices of G induce more than 4 edges and |E(G) | is divisible by 3.

Bondy [1] proved that if we double the edges of a cubic graph then [P.sub.4] decomposes the resulting multigraph.

Theorem 3 [1] Let G be a cubic graph. Then [.sup.2G] has a [P.sub.4]-decomposition.

The following generalization of Theorem 3 was obtained in [6].

Theorem 4 [6] Every 6-regular multigraph with [mu](G) [less than or equal to] 2 has a [P.sub.4]-decomposition.

Theorem 4 was further generalized to multigraphs with higher multiplicity in [6].

Theorem 5 [6] For all integers k [greater than or equal to] 1, every 6k-regular multigraph G with [mu](G) [less than or equal to] 2k has a [P.sub.4]-decomposition.

In section 3 of this paper we prove the NP-Completeness of some [P.sub.4]-decomposition problems. Dor and Tarsi [5] proved the following classic NP-Completeness theorem about decompositions of graphs

Theorem 6 [5] For a fixed graph H that has at least one component with at least 3 edges, the problem of determining if there exists an H-decomposition of an arbitrary graph G is NP-Complete.

Brys and Lonc [4] proved that if every component of H has at most 2 edges, then there is a polynomial time algorithm to determine if a graph G has an H-decomposition.

Theorem 7 [4] For a fixed graph H with each component having at most 2 edges, the problem of determining if there exists an H -decomposition of an arbitrary graph G can be solved in polynomial time.

Theorem 6 implies that the problem of determining if [P.sub.4] decomposes an arbitrary graph G is NP-Complete. Teypaz and Rapine [13] proved that this remains true even under the restricted case where G is bipartite.

Theorem 8 [13] The problem of determining if there exists a [P.sub.4]-decomposition of an arbitrary bipartite graph G is NP-Complete.

Oksimets [12] obtained the following theorem as a corollary of a result on triangle-free Euler tours in even-regular graphs.

Theorem 9 [12] For all integers k [greater than or equal to] 3, every connected 2k-regular graph G with |E(G) | being divisible by 3 has a [P.sub.4]-decomposition.

In section 3 of this paper we use a construction similar to the one used in the proof of Theorem 8 to prove that for all integers k [greater than or equal to] 2, the problem of determining if [P.sub.4] decomposes a (2k + 1)-regular graph is NP-Complete. We also prove that for all integers k [greater than or equal to] 3, the problem of determining if [P.sub.4] decomposes a 2k-regular multigraph G with [??] is NP-Complete. This shows that with respect to the maximum multiplicity of the multigraph, unless P = NP, Theorems 4 and 5 are best possible. In particular, in contrast to Theorem 4, this shows that the problem of determining if [P.sub.4] decomposes a 6-regular multigraph with maximum multiplicity 3 is NP-Complete.

2 [P.sub.4]-decomposition of 4-regular multigraphs of maximum multiplicity 2

A (2,4)-multigraph is a multigraph whose vertices have degree 2 or 4. Let G be the family of connected (2,4)-graphs shown in Figure 1 where H is any graph with appropriate degrees. Heinrich et al.[9] proved that the graphs in G are the only connected (2,4)-graphs that do not admit a triangle-free Euler tour.

Theorem 10 [9] A connected (2,4)-graph G admits a triangle-free Euler tour if and only if G [??] G.

[FIGURE 1 OMITTED]

Clearly, if G [??] G is a connected, (2,4)-graph with |E(G)| divisible by 3 then we can obtain a [P.sub.4]-decomposition of G by properly segmenting a triangle-free Euler tour in G. More significantly, Heinrich et al. [9] proved Theorem 2 mentioned in the Introduction as a consequence of Theorem 10.

We now prove extensions of these results by Heinrich et al. [9] to multigraphs G with [mu](G) [less than or equal to] 2. Let F be the family of connected (2,4)-multigraphs shown in Figure 2 where H is any multigraph with appropriate degrees.

Theorem 11 A connected (2,4)-multigraph G with [mu](G) [less than or equal to] 2 admits a ([C.sub.2], [C.sub.3])-free Euler tour if and only if G [??] F.

Proof: If G [member of] F, it is easy to check that G does not admit a ([C.sub.2], [C.sub.3])-free Euler tour. Let G [??] F be a connected (2,4)-multigraph with [mu](G) [less than or equal to] 2 and let p(G) be the number of parallel edge pairs in G. We prove the theorem by induction on p(G). The base case p(G) = 0 follows from Theorem 10 because in that case G has no multiple edges and the family G of graphs in Figure 1 is contained in the family F in Figure 2. Suppose inductively that the theorem is true for 0 [less than or equal to] p(G) [less than or equal to] k. Let G [??] F be a connected (2,4)-multigraph with [mu](G) [less than or equal to] 2 andp(G) = k + 1.

[FIGURE 2 OMITTED]

Let u and [nu] be adjacent vertices of G with [mu](u, [NU]) = 2, and let G* be the graph obtained from G by subdividing one of the edges (u, [nu]) by inserting a new vertex w. Clearly, G* is a connected (2,4)-multigraph with p(G*) = k. We claim that G* [??] F. If G* [member of] F then the inserted vertex w of degree two must be a depicted vertex of one of the multigraphs in Figure 2. But note that the multigraph obtained by deleting any depicted vertex x of degree two from any of the multigraphs in Figure 2 and joining the neighbors of x by an edge results in a multigraph in F or an edge of multiplicity three or a loop. For example, performing this operation on the multigraph XIII in Figure 2 results in multigraph X. Hence, since G [??] F, we have that G* [??] F as claimed.

By the induction hypothesis we have that G* has ([C.sub.2], [C.sub.3])-free Euler tour E* and we may assume without loss of generality that u, w, v is a subsequence of E*. Let E be the Euler tour of G obtained from E* by replacing its subsequence u, w, v by u, v. Since E* is ([C.sub.2], [C.sub.3])-free, E is [C.sub.2]-free and we are done if in addition E is [C.sub.3]-free. So, assume that some 3 consecutive vertices in E form a triangle in G which must clearly contain the edge (u, v) and hence we can assume that E starts with the subsequence u, v, t, u for some vertex t [not equal to] u,v. Because E is [C.sub.2]-free, it cannot end with the subsequence v, u, and hence we can further assume that E starts with the subsequence u, v, t, u, v. But then, E* must contain either the subsequence u, w, v, t, u, v or u, v, t, u, w, v. In either case, this implies that E* contains a [C.sub.3]-subsequence which is a contradiction. The result follows.

Theorem 11 directly yields the corollary below by appropriately segmenting a ([C.sub.2], [C.sub.3]) -free Euler tour into 3-edge segments.

Corollary 1 Let G be a connected (2,4)-multigraph with [mu](G) [less than or equal to] 2. If G [??] F and |E(G)| is divisible by 3 then G admits a [P.sub.4] decomposition.

We are now ready to prove the main result of this section.

Theorem 12 A connected 4-regular multigraph G with [mu](G) [less than or equal to] 2 admits a [P.sub.4] decomposition if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3.

Proof: Clearly, if G has a [P.sub.4]-decomposition then |E(G)| is divisible by 3 and no three vertices of G induce more than 4 edges.

Let G be a connected 4-regular multigraph with [mu](G) [less than or equal to] 2, with |E(G) | divisible by 3, and such that no three vertices of G induce more than 4 edges. If G [??] F, the result follows from Corollary 1. So assume G [member of] F. Clearly, G must be a type IX, X, or XIV graph (and perhaps, all three) in F.

We will construct from G a connected (2,4)-multigraph G* [??] F and with |E(G*)| divisible by 3. Theorem 11 will then imply that G* admits a ([C.sub.2], [C.sub.3])-free Euler tour, and hence a [P.sub.4] decomposition. We will then show how this [P.sub.4] decomposition of G* yields a [P.sub.4] decomposition of G.

We construct G* by replacing the subgraph induced by the 4 vertices shown in Figure 2 in type IX or type X structures in G by paths of length 4, and, the subgraph induced by the 5 vertices shown in Figure 2 in type XIV structures in G by paths of length 3. Note that the lengths of these paths mod 3 is equal to the number of edges mod 3 in the induced subgraphs that they replace.

Clearly, G* [??] F is a connected (2,4)-multigraph with [mu](G*) [less than or equal to] 2, and |E(G*)| divisible by 3, and hence by Theorem 11 has a ([C.sub.2], [C.sub.3])-free Euler tour, T*. We now use T* to construct an Euler tour, T, in G which will provide a [P.sub.4]-decomposition of G.

Begin by traversing T* until the next vertex to be reached is contained in a replacement path. Let m be the number of edges traversed until now reduced modulo 3. Remove the replacement path added in the construction of G*, and reinstate the original induced subgraph on 4 or 5 vertices that was replaced by it. In Figures 3, 4, and 5, the directions in which these edges should be traversed are indicated with arrows, and the order in which the edges are to be traversed have been indicated by labels that occur in sets of three, which also indicate which edges will be partitioned together in the final [P.sub.4]-decomposition of G. Note that we lose no generality by assuming that the reinstated subgraph is entered from the left-hand side in Figures 3, 4, and 5. Even in the case of a type IX graph in F, which is not strictly symmetric, it is easy to confirm a symmetry between the labelings given in Figures 3(a), (b), and (c), 4(a), (b), and (c), and 5(a), (b), and (c). For each reinstated subgraph, the labeling of the edges chosen depends on m, as well as the type of structure replaced. If m is equivalent to 0 modulo 3, the labeling is given by Figure 3(a), 4(a), or 5(a), if m is equivalent to 1 modulo 3, the labeling is given by Figure 3(b), 4(b), or 5(b), and, if m is equivalent to 2 modulo 3, the labeling is given by Figure 3(c), 4(c), or 5(c). Note that in all cases, no edges with equal labels induce a [C.sub.3] or a [C.sub.2].

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Continue traversing the edges of T* after leaving the reinstated subgraph and iterate this process until all subgraphs that were replaced by paths when G* was constructed have been reinstated, and all edges of G have been traversed.

This completes the construction of T, which is not necessarily ([C.sub.2], [C.sub.3])-free but such that for i [member of] [1, |E(G)|] if we label the i th edge encountered in T by [e.sup.i], then the edges [e.sub.3j]-2, [e.sub.3j]-1, [e.sub.3j] form a [P.sub.4] for [??], thus providing a [P.sub.4]-decomposition of G.

3 NP-Completeness of some regular graph/multigraph decomposition problems

For an integer m [greater than or equal to] 3, X3C(m) is the following exact 3-cover problem.

X3C(m)

Given: A finite ground set X and a collection of subsets S = [{[S.sub.i]}.sup.k.sub.i=1] of X with |[S.sub.i]| = 3 for each i[member of] [1,k] and each element of X contained in exactly m sets in S.

Question: Is there a subcollection Q [??] S such that each element of X is contained in exactly one set in Q?

If for some instance I of X3C(m), the subcollection Q in the above question exists, we say that I has an exact cover consisting of Q.

Gonzalez [7] proved that Exact 3-cover is NP-complete if each element of the ground set is contained in exactly 3 subsets.

Theorem 13 [7] X3C(3) is NP-complete.

We first prove the following more general form of Theorem 13.

Theorem 14 For every integer m [greater than or equal to] 3, X3C(m) is NP-complete.

Proof: Clearly, the problem is in NP. Theorem 13 verifies the case m = 3. Suppose we have an instance I of X3C(n) with ground set X and a collection of subsets S of X, for some integer n [greater than or equal to] 3. We will construct an instance I' of X3C(n + 1) with ground set X' and a collection of subsets S' of X' such that I has an exact cover if and only if I' has an exact cover.

Without loss of generality suppose that |X| = 3q, otherwise trivially, no exact cover exists for instance I. Partition the elements in X arbitrarily into q sets Xs = {[x.sup.(s).sub(1)],[x.sup.(s).sub(2)],[x.sup.(s).sub(3)] }, for each s [member of] [1,q]. Let X' = X [union]( [[union].sup.q.sub.s=1]{[a sup.(s).sub(1)],[a.sup.(s).sub(2)],...,[a.sup.(s).sub(n+1)], where ai is a new element not contained in X for each i [member of] [1,3(n+ 1)] and s [member of] [1, q]. The collection of subsets S' of X' is better described by first constructing a collection of subsets S" and then amending S" to get S'. Let S" = S X [union]( [[union].sup.q.sub.s=1]{{[a.sup.(s).sub.3i+1], [a.sup.(s).sub.3i+2], [a.sup.(s).sub.3j+3]} : 0 [less than or equal to] i,j [less than or equal to] n}). Note that for each i [member of] [1,3(n + 1)] and s [member of] [1, q], [a.sup.(s).sub.i] is contained in exactly (n + 1) subsets of S". Now, to construct the collection of subsets S' we amend S" as follows: Delete the 3q sets {[a.sup.(s).sub.3n+1], [a.sup.(s).sub.3n+2], a[a.sup.(s).sub.3j+3]} for each 0 [less than or equal to] j < 3 and each s [member of] [1, q], add the sets {[a.sup.(s).sub.3], [a.sup.(s).sub.6], [a.sup.(s).sub.9] } for each s [member of] [1, q], and, replace the element [a.sup.(s).sub.3n+3] in the sets {[a.sup.(s).sub.3i+1], [a.sup.(s).sub.3i+2], [a.sup.(s).sub.3n+3]} for 0 [less than or equal to] i < 3 by the element [a.sup.(s).sub.3n+1] for each s [member of] [1, q]. Now all new elements except [a.sup.(s).sub.3n+2] and [a.sup.(s).sub.3n+3] for each s [member of] [1, q] are contained in (n + 1) sets and these are contained in exactly (n - 2) sets. Finally, add the sets {[x.sup.(s).sub.i], [a.sup.(s).sub.3n+2], [a.sup.(s).sub.3n+3]} for each i [member of] [1,3] and each s [member of] [1, q]. We now have the collection of subsets S' of X' of cardinality 3 each and such that each element of X' is contained in exactly (n + 1) sets in S'. Now if I has an exact cover Q then Q' = Q [union]([[union].sup.q.sub.s=1]{{[a.sup.(s).sub.3i+1], [a.sup.(s).sub.3i+2], [a.sup.(s).sub.3i+3]} : i [member of] [0, n]}) is an exact cover for I'. Conversely, if Q' is an exact cover of I', then no set of the form {[ax.sup.(s).sub.i], [a.sup.(s).sub.3n+2], [a.sup.(s).sub.3n+3]} for i [member of] [1, 3] and s [member of] [1, q] can be Q', since if so, it is impossible to cover the elements [a.sup.(s).sub.i] for i [member of] [1,3(n +1)] \ {3n + 2, 3(n +1)} and s [member of] [1, q]. Hence, in I', the elements of the ground set X of I must be covered by sets in S which gives an exact cover for I.

We now use Theorem 13 to prove that the problem of determining if [P.sub.4] decomposes a 5-regular graph is NP-complete, and point out that Theorem 14 can be used to prove more generally that for all integers k [greater than or equal to] 2, the problem of determining if [P.sub.4] decomposes a (2k + 1)-regular graph is NP-complete.

Theorem 15 Given a 5-regular graph G, the problem of determining if [P.sub.4] decomposes G is NP-Complete.

Proof: Clearly the problem is in NP. We will prove the theorem by reduction from the NP-Complete problem X3C(3). Consider an arbitrary instance I of X3C(3) with ground set X and a collection of subsets S = [{[S.sub.i]}.sup.k.sub.i=1] of X with |[S.sub.i]| = 3 for each i [member of] [1,k] and each element of X contained in exactly 3 sets in S. Without loss of generality assume that |X| = |S| = 3q and let X = {[x.sub.1], [x.sub.2],..., [x.sub.3q]}. We will construct a 5-regular graph G such that [P.sub.4] decomposes G if and only if I has an exact cover. For each element [x.sub.i] [member of] X, we have a vertex [v.sub.i] [member of] V(G), i [member of] [1,3q]. For each set [S.sub.i] [member of] S, we will construct a set-gadget graph [G.sub.i],i [member of] [1, 3q]. If [S.sub.i] = {[x.sub.j], [x.sub.k], [x.sub.l]} then [G.sub.i] has 3 vertices [w.sup.(i).sub.j], [w.sup.(i).sub.k], and [w.sup.(i).sub.l] of degree 4 each and 6 vertices [a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i], [e.sub.i], and [f.sub.i] of degree 5 each, so that |E([G.sub.i])| = 21 = 0 (mod 3). In addition we choose [G.sub.i] and [G.sub.i] \ T to be [P.sub.4]-decomposable, where T is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree 4. Figure 6 shows an example of Gi with these properties. The letters by the edges indicate a [P.sub.4]-decomposition of the gadget. Also note that if you remove the edges ([w.sup.i.sub.j.], [d.sub.i]), ([d.sub.i], [b.sub.i]), ([w.sup.i.sub.k.], [f.sub.i]), ([w.sup.i.sub.j.],[f.sub.i]) ([f.sub.i], [d.sub.i]), ([w.sup.i.sub.k.], [a.sub.i]), and ([a.sub.i], [d.sub.i]) the letters on the edges continue to indicate a [P.sub.4]-decomposition of the remaining edges

[FIGURE 6 OMITTED]

In G, if [x.sub.i] [member of] [S.sub.j], vertex [v.sub.j] is joined to vertices [S.sup.(j).sub.i], for each i, j [member of] [1,3q]. For each element [x.sub.i] [member of] X, we construct two disjoint copies [H.sup.(1).sub.i], [H.sup.(2).sub.i] of an element-gadget graph, i [member of] [1, 3q]. For j = 1 and 2, graph [H.sup.(j).sub.i] has one vertex [u.sup.(j).sub.i] of degree 4 and 8 vertices of degree 5, so that |E[H.sup.(j).sub.i] )| = 22 = 1 (mod 3). In addition, we choose [H.sup.(j).sub.i] such that [H.sup.(j).sub.i] - e is [P.sub.4] decomposable, where e is an edge incident on the vertex of degree 4. Figure 7 shows an example of [H.sup.(1).sub.i] with these properties. The letters to the right or above the edges indicate a [P.sub.4]-decomposition of the gadget with the exception of one edge incident on the vertex of degree 4. In G, for each i [member of] [1, 3q], vertex [v.sub.i] is joined by an edge to vertices [u.sup.(1).sub.i] and [u.sup.(2).sub.i] This completes the construction of the graph G.

Suppose that the instance I of X3C(3) has an exact cover Q. If for i [member of] [1, 3q] set [S.sub.i] = {[x.sub.j],[x.sub.k],[x.sub.l]} [member of] Q, we use 3 edge-disjoint paths of length 2 in [G.sub.i] starting at [w.sup.(i).sub.j],[w.sup.(i).sub.k] and [w.sup.(i).sub.l] together with the edges [v.sub.jw.sup.(i).sub.j], [v.sub.kw.sup.(i).sub.k] and [v.sub.lw.sup.(i).sub.l] that are external to [G.sub.i] as 3 [P.sub.4] s in a decomposition of G. The rest of the 15 edges in [G.sub.i] decompose internally into [P.sub.4] s. For [S.sub.i] [??] Q we decompose all the 21 edges in [G.sub.i] internally into [P.sub.4] s. Since Q is an exact cover of I, for each i [member of] [1, 3q], this leaves uncovered exactly 2 edges joining [v.sub.i] to vertices corresponding to 2 sets in S \ Q. We use these 2 uncovered edges together with the edges [v.sub.iu.sup.(1).sub.i],[v.sub.iu.sup.(2).sub.i] and two internal edges in [H.sup.(1).sub.i]i and [H.sup.(2).sub.i] incident on [u.sup.(1).sub.i] and [u.sup.(2).sub.i] as 2 [P.sub.4] s in the decomposition of G. The remaining 21 edges in each of [H.sup.(1).sub.i] and [H.sup.(2).sub.i] decompose internally into [P.sub.4] s for each i [member of] [1,3q].

Conversely suppose that G has a [P.sub.4]-decomposition. For i [member of] [1,3q], the [P.sub.4] s that are internal to [H.sup.(1).sub.i] and [H.sup.(2).sub.i] in the decomposition leave exactly one internal edge uncovered incident on each of [u.sup.(1).sub.i] and [H.sup.(2).sub.i]. In any [P.sub.4]-decomposition of G these uncovered edges must be covered by [P.sub.4] s that include the edges [u.sup.(1).sub.i] [v.sub.i] and [u.sup.(2).sub.i] [v.sub.i] together with 2 edges joining [v.sub.i] to corresponding vertices [w.sup.(j).sub.i] and [w.sup.(k).sub.i] for some j, k [member of] [1, 3q]. For each i [member of] [1, 3q], this leaves exactly one edge incident on [v.sub.i] uncovered that joins [v.sub.i] to a corresponding vertex [w.sup.(l).sub.i] for some l [member of] [1, 3q].

[FIGURE 7 OMITTED]

Foreach i [member of] [1,3q], let [X.sub.i] = {[v.sub.j][w.sup.(i).sub.j],[v.sub.k][w.sup.(i).sub.k],[v.sub.l][w.sup.(i).sub.l] } be the set of edges that have exactly one endpoint in V([Gsub.i]). We claim that in any [P.sub.4]-decomposition of G, for each i [member of] [1, 3q] the [P.sub.4] s that cover the edges in [G.sub.i] include all three or none of the edges in [X.sub.i]. To see this, note that if exactly one of the edges in [X.sub.i] is included in the [P.sub.4] s that cover the edges in [G.sub.i], then that edge must be in a [P.sub.4] that includes 2 edges in E([G.sub.i]) and that leaves the remaining 19 edges in E([G.sub.i]) to be covered internally, which is impossible. If exactly two of the edges in [X.sub.i] are included in the [P.sub.4] s that cover the edges in [G.sub.i], then, clearly, this leaves either 17 or 20 edges in E([G.sub.i]) to be covered internally, which is impossible.

Now, it is easy to see that the sets corresponding to those set-gadget graphs [G.sub.i], i [member of] [1, 3q], for which the [P.sub.4] s that cover the edges in [G.sub.i] include all three edges in [X.sub.i] form an exact cover of I.

We point out that by using the more general Theorem 14, a proof similar to that of Theorem 15 yields the NP-Completeness of the problem of determining if a (2k + 1)-regular graph has a [P.sub.4]-decomposition for all k [greater than or equal to] 2.

Theorem 16 For all k [greater than or equal to] 2, given a (2k + 1)-regular graph G, the problem of determining if [P.sub.4] decomposes G is NP-Complete.

Proof: Clearly the problem is in NP. Theorem 14 gives that X3C(k + 1) is NP-Complete for all k [greater than or equal to] 2. We prove the theorem by reduction from X3C(k + 1) for k [greater than or equal to] 2. Given an arbitrary instance I of X3C(k + 1) for k [greater than or equal to] 2, we will only describe the set-gadget graphs, the element-gadget graphs, and the graph G which is (2k + 1)-regular and such that I has an exact cover if and only if [P.sub.4] decomposes G. As in the proof of Theorem 15 we have a set-gadget graph for each subset of the ground set. The set-gadget graph [G.sub.i] has 3 vertices of degree 2k each, all other vertices of [G.sub.i] have degree (2k + 1) each, |E([G.sub.i]) | = 0 (mod 3), [G.sub.i] is [P.sub.4] decomposable, and [G.sub.i] \ T is decomposable where T is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree 2k. Corresponding to each element [x.sub.i] of the ground set we have a vertex [v.sub.i] and k copies of an element gadget graph [H.sup.(j).sub.i], j [member of] [1,k]. Each element-gadget graph [H.sup.(j).sub.i] has one vertex of degree 2k, all other vertices of [H.sup.(j).sub.i] have degree (2k + 1) each, |E([H.sup.(j).sub.i]) | = 1 (mod 3), and [H.sup.(j).sub.i] - e is [P.sub.4] decomposable, where e is an edge incident on the vertex of degree 2k. For each element [x.sub.i] in the ground set, the corresponding vertex [v.sub.i] is joined to the k vertices of degree 2k in each of the associated element-gadget graphs [H.sup.(j).sub.i], j [member of] [1, k], and [v.sub.i] is joined to one of the 3 vertices of degree 2k in each of the associated set-gadget graphs that correspond to the (k + 1) subsets that contain [x.sub.i]. Now, an argument similar to that in the proof of Theorem 15 shows that I has an exact cover if and only if [P.sub.4] decomposes G.

We will now use Theorem 16 to prove the NP-Completeness of the problem of determining if [P.sub.4] decomposes certain regular multigraphs.

Theorem 17 For all integers k [greater than or equal to] 1, the problem of determining if [P.sub.4] decomposes a 6k-regular multigraph G with [mu](G) [less than or equal to] (2k + 1) is NP-Complete.

Proof: Clearly, the problem is in NP. Theorem 16 gives that the problem of determining if [P.sub.4] decomposes a (6k - 1)-regular graph is NP-Complete for all integers k [greater than or equal to] 1. We will prove our theorem by reduction from this NP-Complete problem.

For k [greater than or equal to] 1, given a (6k - 1)-regular graph G, we will construct a 6k-regular multigraph G' with [mu](G") [less than or equal to] (2k + 1) such that [P.sub.4] decomposes G if and only if [P.sub.4] decomposes G'. If | V(G) | = n, we will use n copies of the following gadget graph H in our construction of G'. To construct the gadget H, take 3 disjoint cliques [Q.sub.1], [Q.sub.2], and [Q.sub.3] on 2k vertices each and remove a perfect matching from [Q.sub.1] and [Q.sub.2]. Add 2k disjoint triangles, each containing one vertex from each of the 3 cliques. The edges of these triangles joining a vertex in [Q.sub.1] to a vertex in [Q.sub.2] have multiplicity (2k + 1), and all other edges of these triangles have multiplicity 2k. This completes the construction of the gadget graph H which is (6k - 1)-regular and has [mu](H) [less than or equal to] (2k + 1). In the construction of G' we will add one edge between each vertex of a copy of H and the rest of G'.

Now, given a (6k - 1)-regular graph G on n vertices [v.sub.i], i G [1, n], make 6k disjoint copies [G.sub.i], i [member of] [1,6k] of G, and n disjoint copies [H.sub.i], i [member of] [1, n] of H. Join each vertex of [H.sub.i] to a different copy of [v.sub.i] [member of] [[union].sup.6k.sub.j=1] V([G.sub.j]) for i [member of] [1, n]. This completes the construction of the graph G'.

Suppose [P.sub.4] decomposes G. We decompose each [G.sub.i], i [member of] [1, 6k] separately. It is easy to check that each [H.sub.i], i [member of] [1, n] together with the 6k edges between a vertex of [H.sub.i] and a vertex not in V([H.sub.i]) can be decomposed into [P.sub.4] s separately. This yields a [P.sub.4]-decomposition of G'.

Conversely, suppose [P.sub.4] decomposes G'. We claim that the edges in each [H.sub.i], i [member of] [1, n] together with the 6k edges between a vertex of [H.sub.i] and a vertex not in V([H.sub.i]) must be decomposed into [P.sub.4] s without using any other edges. To prove this claim note that the total number of edges contained in the 2k disjoint triangles added to the 3 cliques in [H.sub.i] is (2k)(6k + 1). Any [P.sub.4] can contain at most 2 edges from these triangles and hence in any decomposition of G' there are at least (k)(6k + 1) = ([6k.sup.2] + k) [P.sub.4]'s that contain edges from these triangles. In addition, any of these ([6k.sup.2] + k) [P.sub.4]'s must use an edge from one of the cliques [Q.sub.i], i [member of] [1,3] or an edge joining a clique vertex to the rest of the graph G'. Since there are exactly ([6k.sup.2] + k) such edges, the claim follows. Now, the [P.sub.4]-decomposition of any [G.sub.i], i G [1, 6k] in the decomposition of G' gives a [P.sub.4]-decomposition of G.

We now prove a strengthening of Theorem 17 above.

Theorem 18 For all integers k [greater than or equal to] 3, the problem of determining if [P.sub.4] decomposes a 2k-regular multigraph G with [??] is NP-Complete.

Proof: Clearly, the problem is in NP. If k is a multiple of 3 then the theorem follows from Theorem 17 above.

So, suppose that k = 3m + 1 for some integer m [greater than or equal to] 1. For m [greater than or equal to] 1, given a (6m + 1)-regular graph G, we will construct a (6m + 2)-regular multigraph G' with [mu](G') [less than or equal to] (2m + 1) such that [P.sub.4] decomposes G if and only if [P.sub.4] decomposes G'. This will prove the theorem for this case because by Theorem 16 the problem of determining if [P.sub.4] decomposes a (6m + 1)-regular graph is NP-Complete for all m [greater than or equal to] 1. If | V(G) | = n, we will use n copies of the following gadget graph H in our construction of G'. To construct the gadget H, take 3 disjoint copies of the clique [K.sub.2m] and add 2m disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of each edge of these triangles being (2m +1). This completes the construction of the gadget graph H which is (6m + 1)-regular and has [mu](H) [less than or equal to] (2m + 1). In the construction of G' we will add one edge between each vertex of a copy of H and the rest of G'.

Now, given a (6m + 1)-regular graph G on n vertices [v.sub.i], i [member of] [1, n], make 6m disjoint copies [G.sub.i], i [member of] [1, 6m] of G, and n disjoint copies [H.sub.i], i [member of] [1, n] of H. Join each vertex of [H.sub.i] to a different copy of [v.sub.i] [member of] [[union].sup.6m.sub.j=1] V([G.sub.j]) for i [member of] [1, n]. This completes the construction of the graph G'. Now, as in the proof of Theorem 17, we can argue that the edges in each [H.sub.i], i [member of] [1, n] together with the 6m edges between a vertex of [H.sub.i] and a vertex not in V([H.sub.i]) must be decomposed into [P.sub.4] s without using any other edges. The rest of the proof is similar to that of Theorem 17.

To complete the proof, suppose that k = 3m + 2 for some integer m [greater than or equal to] 1. For m [greater than or equal to] 1, given a (6m + 3)-regular graph G, we will construct a (6m + 4)-regular multigraph G' with [mu](G') [less than or equal to] (2m + 2) such that [P.sub.4] decomposes G if and only if [P.sub.4] decomposes G'. This will prove the theorem for this case because by Theorem 16 the problem of determining if [P.sub.4] decomposes a (6m + 3)-regular graph is NP-Complete for all m [greater than or equal to] 1. If |V(G)| = n, we will use n copies of the following gadget graphH in our construction of G'. To construct the gadget H, take 3 disjoint copies [Q.sub.1],[Q.sub.2], and [Q.sub.3] of the clique [K.sub.2m] and add 2m disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of the edges between a vertex of [Q.sub.1] and a vertex of [Q.sub.2] being (2m + 1) and the multiplicity of all other edges of the added triangles being (2m + 2). Now, add a perfect matching with 2m edges between cliques [Q.sub.1] and [Q.sub.2] making sure that none of the edges in the matching are parallel to any edge of the triangles added earlier. This completes the construction of the gadget graph H which is (6m + 3)-regular and has [mu](H) [less than or equal to] (2m + 2). In the construction of G' we will add one edge between each vertex of a copy of H and the rest of G'.

Now, given a (6m + 3)-regular graph G on n vertices [v.sub.i], i [member of] [1, n], make 6m disjoint copies [G.sub.i], i [member of] [1, 6m] of G, and n disjoint copies [H.sub.i], i [member of] [1, n] of H. Join each vertex of [H.sub.i] to a different copy of [v.sub.i] [member of] [[union].sup.6m.sub.j=1] V([G.sub.j]) for i [member of] [1, n]. This completes the construction of the graph G'. The rest of the proof is similar to the proof of Theorem 17.

We note that the proof of Theorem 18 used gadgets for a 2k-regular multigraph G that contain triangles with (2k + 1) edges. In [v.sub.i]ew of this we offer the following conjecture which is verified by Theorem 12 in the case when k = 2 and which implies Theorem 5 when k is a multiple of 3.

Conjecture 2 Let G be a connected 2k-regular multigraph G with [??] and such that any three vertices in G induce at most 2k edges. Then [P.sub.4] decomposes G if and only if|E(G) | is divisible by 3.

Acknowledgements

We would like to thank the anonymous referee for a careful reading of our paper and in particular for pointing out an error in our original proof of Theorem 11.

References

[1] J.A. Bondy. Perfect path double covers of graphs. J. Graph Theory, 14:259-272, 1990.

[2] J.A. Bondy andU.S.R. Murty. Graph Theory. Springer, 2008.

[3] A. Bouchet and J. L. Fouquet. Trois types de decompositions d'un graphe en chaines. Ann. Discrete Math., 17:131-141, 1983.

[4] K. Brys and Z. Lonc. Polynomial cases of graph decomposition: A complete solution of holyer's problem. Discrete Mathematics, 309:1294-1326, 2009.

[5] D. Dor and M. Tarsi. Graph decomposition is np-complete: A complete proof of holyer's conjecture. SIAM Journal on Computing, 26:1166-1187, 1997.

[6] Saad El-Zanati, Michael Plantholt, and Shailesh Tipnis. On decomposing even regular multigraphs into small isomorphic trees. Discrete Mathematics, 325:47-51, 2014.

[7] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985.

[8] R. Haggkvist. Decompositions of complete bipartite graphs. London Math. Soc. Lecture Note Ser. C. U. P., 141:115-147, 1989.

[9] K. Heinrich, J. Liu, andM. Yu. [P.sub.4]-decompositions of regular graphs. J. Graph Theory, 31:135-143, 1999.

[10] A. Kotzig. Aus der Theorie der endlichen regularen Graphen dritten und vierten Grades. Casopis Pest. Mat., 82:76-92, 1957.

[11] M. Kouider and Z. Lonc. Path decompositions and perfect path double covers. Australas. J. Combin., 19:261-274, 1999.

[12] Natalia Oksimets. A characterization of Eulerian graphs with trianglefree Euler tours. Technical Report 1, Department of Mathematics, Umea University, 2003.

[13] N. Teypaz and C. Rapine. Graph decomposition into paths under length constraints. Technical Report 165, Les Cahiers Leibniz, 2008.

Ajit A. Diwan (1*)

Justine E. Dion (2[dagger])

David J. Mendell (2[double dagger])

Michael J. Plantholt (2[section])

Shailesh K. Tipnis (2[paragraph])

(1) Department of Computer Science and Engineering, Indian Institute of Technology, Mumbai, India

(2) Department of Mathematics, Illinois State University, USA

received 27th Aug. 2014, revised 15th May 2015, accepted 25th Aug. 2015.

(*) Email: aad@cse.iitb.ac.in

([dagger]) Email: jlessen@ilstu.edu

([double dagger]) Email: djmende@ilstu.edu

([section]) Email: mikep@ilstu.edu

([paragraph]) Email: tipnis@ilstu.edu
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Diwan, Ajit A.; Dion, Justine E.; Mendell, David J.; Plantholt, Michael J.; Tipnis, Shailesh K.
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jul 1, 2015
Words:7562
Previous Article:The game chromatic number of trees and forests.
Next Article:Improving vertex cover as a graph parameter.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters