Nội dung

For which graphs does every edge belong to exactly two chordless cycles? Uri N. Peled1 and Julin Wu2 Dept. of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago 851 S. Morgan Street Chicago, IL 60607-7045 Submitted: December 2, 1995; Accepted: April 15, 1996. Key Words: Chordless cycles, balanced graphs, balanced matrices Mathematical Reviews Subject Numbers: Primary 05C75; Secondary 05C3B, 05C50, 90C35 1 uripeled@uic.edu 2 jwu2@uic.edu Abstract A graph is 2-cycled if each edge is contained in exactly two of its chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices. The concept of balance of a {0, +1, −1}matrix or a signed bipartite graph has been studied by Truemper and by Conforti et al. The concept of α-balance is a generalization introduced by Truemper. Truemper exhibits a family F of planar graphs such that a graph G can be signed to be α-balanced if and only if each induced subgraph of G in F can. We show here that the graphs in F are exactly the 2-connected 2-cycled graphs. 1 Introduction A graph is said to be 2-cycled if each of its edges is contained in exactly two chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices by Truemper [3] and by Conforti et al. [2], as indicated in the next three paragraphs. A signed graph is a graph G = (V, E) together with a mapping f : E −→ {+1, −1}. Consider a mapping α : C −→ {0, 1, 2, 3}, where C is the set of chordless cycles of G. If Σe∈C f (e) ≡ α(C) (mod 4) for all C ∈ C, we say that the signed graph is α-balanced. A trivial necessary condition, which we assume throughout, is that |C| ≡ α(C) (mod 2) for all C ∈ C. When α = 0, this condition means that G is bipartite, in which case it can be specified by its adjacency matrix A, and A is balanced in the usual sense if and only if the signed graph consisting of G and the constant mapping f = 1 is 0-balanced. Similarly, a {0, +1, −1}-matrix A specifies a signed bipartite graph, and A is said to be balanced when the signed bipartite graph is 0-balanced. It is easy to check that each graph of the following types is 2-cycled (See Figure 1): Star-subdivision of K4 : The result of subdividing zero or more of the three edges incident to a single vertex of K4; Rim-subdivision of a wheel: The result of subdividing zero or more rim edges of the wheel Wk , k ≥ 3; Subdivision of K2,3 : The result of subdividing zero or more edges of K2,3 .; Triangles-joining: Two vertex-disjoint triangles with three vertex-disjoint paths joining them. Note that if two nonadjacent edges of K4 and possibly other edges are subdivided, the resulting graph is not 2-cycled. It is called a bad subdivision of K4. Truemper [3] showed that a graph G possesses a mapping f that makes it α-balanced if and only if each induced subgraph of G that is a starsubdivision of K4 , a rim-subdivision of a wheel, a subdivision of K2,3 or a triangles-joining enjoys the same property. Our main result is that these are all the 2-connected 2-cycled graphs (Clearly, a graph s 2-cycled if and only if all its 2-connected components are, so without loss of generality we may consider only 2-connected graphs): the electronic journal of combinatorics 3 (1996), #R14 r r r r r r r r r r r 2 r r r r r r r (a) r (b) r r r r r r r r r r (c) r r r r r r r (d) Figure 1: 2-cycled graphs. (a): Star-subdivision of K4 ; (b): Rim-subdivision of a wheel; (c): Subdivision of K2,3 ; (d): Triangles-joining. Theorem 1 (Main Theorem) A 2-connected graph is 2-cycled if and only if it is a star-subdivision of K4 , a rim-subdivision of a wheel, a subdivision of K2,3 or a triangles-joining. This paper is organized as follows. In Section 2 we give definitions of some new concepts. In Section 3 we define and characterize the upper and lower 2-cycled graphs; these graphs are defined so that a graph is 2-cycled if and only if it is both upper 2-cycled and lower 2-cycled. In Section 4 we study the structure of 2-cycled graphs and prove the Main Theorem. Early on (in Corollary 2) we show that the upper 2-cycled graphs are planar, and this planarity plays an important part in the proofs. 2 Preliminaries We discuss only finite simple graphs and use standard terminology and notation from [1], except as indicated. We denote by NG (u) or simply N(u) the set of vertices adjacent to a vertex u in a graph G, and by NG (S) or N(S) S the set u∈S NG (u) for a vertex subset S. A chord of a path or a cycle is an edge joining two non-consecutive vertices of the path or cycle. A chordless the electronic journal of combinatorics 3 (1996), #R14 3 path or cycle is one having no chord. For a path P = (x1, x2 , . . . , xk ), we use the notation P [xi , xj ] for the subpath (xi , . . . , xj ), where 1 ≤ i < j ≤ n. If e = ab is an edge of G, the contraction G/e of G with respect to e is the graph obtained from G by replacing a and b with a new vertex c and joining c to those vertices that are adjacent to a or b. The edge set of G/e may be regarded as a subset of the edge set of G. A minor of G is a graph that can be obtained from G by a sequence of vertex-deletions, edge-deletions and contractions. By subdividing an edge e we mean replacing e by a path P joining the ends of e, where P has length at least 2 and all of its internal vertices have degree 2. A subdivision of G is a graph obtained by subdividing zero or more of the edges of G. The intersection (union) G1 ∩G2 (G1 ∪G2) of graphs G1 = (V1 , E1 ) and G2 = (V2 , E2) is the graph with vertex set V1 ∩ V2 (V1 ∪ V2 ) and edge set E1 ∩ E2 (E1 ∪ E2 ). If C1 and C2 are cycles of a plane graph G, we say that C1 is within (surrounds) C2 if the area enclosed by C1 is contained in (contains) that enclosed by C2 . Two cycles C and C 0 are said to be harmonic if C ∩ C 0 is a path, as illustrated in Figure 2. If C and C 0 are harmonic cycles of a plane graph, we can find an appropriate plane drawing of the graph such that C 0 is within C, if it is not already the case, by selecting a face within C and making it the outer face. C ....................................... ............. ......... ......... ....... ....... ...... ...... ...... . . . . . ..... .... . ..... . . . ... ... . . . ... ... . ... . ... ... . ... . . . ... 0 ... ... . ... .. . ... .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......... ... ....... . . . . . . . . . . . .... ....... ... ...... . . . . . ... .. . . ...... ... . .. . .. . . . . .... ... ... . ... . . ... .. ... . ... . . ... ... ... . . ... ... ... .. .. . . ... .. ... . . . . . ... ... . .. . . . . ... ... .. ... ... .. ... ... .. ... ... .. ... ... .. ... .... . . . . . ... ... ... .... ... ... ... .. ... ... ...... .. .. .................................................................................................................................. C Figure 2: Harmonic cycles. Let C and C 0 be two cycles with a common edge e, and u a vertex of C 0 − C. Let P 0 be the maximal subpath of C 0 that contains u and does not have internal vertices on C, and let P be the subpath of C joining the two ends of P 0 and containing e. Then P 0 ∪ P is a cycle C 00 , as illustrated in Figure 3. The operation transforming C 0 into C 00 is called grafting C 0 with the electronic journal of combinatorics 3 (1996), #R14 4 respect to C, e and u. An important property of this operation is that the new cycle C 00 is harmonic with C. Furthermore, if the graph is a plane graph and u is within C (or C 0 surrounds C), then C 00 is within (surrounds) C. C0 ........................ ....... ..... .... ... ... ... .. . ... . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . .................... ........................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...... ............... .. .. ............ .... ..... . . . . . . . . . . . . . . . . . . ............ ... . .. .... . . . . . ............ . . . . . . .... ... ........... .... ...... ... ...... ......... ............... ............................ ........ ............ ..... .. .... ..... ..... .... . . . ... ... ... ... . ... ... . ... ... . ... . . ... .. ... .. ...... ... ... ..... ... . ... .. ..... . ... . .. . . ....... ... ... ... . . . . ........ .... ..... ..... ..... ..... ... .... ...... ....... ..... ..... ..... ... C • u =⇒ ..... .................. ......... .... ....... ... ... ........ ...... .. ....... ... ...... .. ...... . . ..... . . . . . . . . ...... ..... .. . . ..... . . . . . . . .... . . . . .................. .. .... . . . .... ... 00 . . ... .. . ... . .. ... . . ... ... . ... .. . ... .. ... . ... .... ... ... ... ... .. ... .. ... ... .... .... e C • u e Figure 3: Grafting. Let P = (x1 , x2, . . . , xk ) be a path in G. If P has a chord xi xj for some i < j −1, we can obtain another path P 0 = (x1 , . . . , xi , xj , . . . , xk ) by deleting the vertices between xi and xj and adding the edge xi xj to P . If P 0 still has chords, we can apply the same operation to P 0 , and so on until we obtain a chordless path P ∗ connecting x1 to xk . For a cycle C of G and an edge e of C, we can apply the above operation to C − e to obtain a chordless cycle C ∗ containing e. We call the operation transforming C into C ∗ chord-cutting C with respect to e. We note that if the graph is a plane graph and C surrounds b and e is a common edge of (is within, is harmonic with) a chordless cycle C b then the cycle obtained by chord-cutting C with respect to e again C and C, b surrounds (is within, is harmonic with) C. 0 Let C and C be cycles of G, where C is chordless, e a common edge of C and C 0, and u a vertex of C 0 − C. By grafting C 0 with respect to C, e and u, and then chord-cutting the resulting cycle with respect to C and e, we obtain a chordless cycle C ∗ . We call the operation transforming C 0 into C ∗ harmonizing C 0 to C with respect to e and u. Note that the new cycle C ∗ still contains e and is harmonic with C and chordless. Furthermore, if G is a plane graph and u is within C (C 0 surrounds C), then C ∗ is within (surrounds) C. After the harmonization operation we forget C 0 and rename C ∗ as C 0. the electronic journal of combinatorics 3 (1996), #R14 3 5 Upper and lower 2-cycled graphs We say that a graph is upper (lower) 2-cycled if each of its edges is contained in at most (at least) two of its chordless cycles. Clearly, a graph possesses this property if and only if each 2-connected component does, but in the rest of this section we do not assume 2-connectivity. The following lemma is crucial in characterizing upper 2-cycled graphs. Lemma 1 If G = (V, E) is upper 2-cycled, so are its minors. Proof. It suffices to show that if G0 results from G by deleting or contracting an edge uv and G0 is not upper 2-cycled, neither is G. Let e = ab be an edge of G0 that is contained in distinct chordless cycles C10 , C20 and C30 of G0 . Case 1: G0 = G − uv. Note that if uv is not a chord of Ci0, then Ci0 is also a chordless cycle of G; in this case, we put Ci = Ci0 . If uv is a chord of Ci0, then Ci0 ∪ uv is split into two chordless cycles of G, each consisting of uv and a subpath of C 0 connecting u to v; we call the one containing e Ci and the ei . If C1 , C2 and C3 are distinct, then they are distinct chordless other one C cycles of G containing e. If they are not, we may assume C1 = C2 . Then C10 e1 and C e2 are distinct chordless and C20 must have uv as a chord, and C1 , C cycles of G containing uv. Case 2: G0 = G/uv. The edge uv of G is contracted to a vertex w of G0. Because uv 6= ab, {a, b}∩{u, v} is empty or has one vertex. If it is nonempty, we assume u = a without loss of generality. If E(Ci0 ) forms a cycle of G, it must be a chordless cycle, and we let Ci be that cycle. If not, w must be a vertex of Ci0, and E(Ci0 ) forms a path Pi in G connecting u to v. Let u0i , vi0 be the neighbors of u, v on Pi , respectively. Then Pi ∪ uv forms a cycle Ci∗ of G, and its only possible chords are uvi0 and u0i v. By chord-cutting Ci∗ with respect to e, we find a chordless cycle Ci containing e. Note that if e and uv are not adjacent, or if the chord u0i v does not exist, then E(Ci ) is contracted to E(Ci0 ) when we contract the edge uv. Now we have three chordless cycles C1, C2 and C3 containing e. If they are not all distinct, say C1 = C2 , then C1 is the triangle {u = a, v, b = u01 = u02}, C1∗ and C2∗ both have bv as a chord, and bv is contained in three distinct chordless cycles of G, namely {a, v, b}, bv ∪ P10 − e, bv ∪ P20 − e.
We note that K3,3 − e and K2 ⊕ 3K1 (the graph obtained by joining every vertex of K2 to every vertex of 3K1 ) are not upper 2-cycled. These the electronic journal of combinatorics 3 (1996), #R14 6 graphs are illustrated in Figure 4. Therefore we have the following corollary of Lemma 1. s s s s s s s s s s K3,3 − e s K2 ⊕ 3K1 Figure 4: Forbidden minors of upper 2-cycled graphs. Corollary 1 An upper 2-cycled graph contains no K2 ⊕ 3K1 or K3,3 − e as a minor. Note that K2 ⊕ 3K1 is a minor of K5 and K3,3 − e is a minor of K3,3 . By Kuratowski’s Theorem, we have the following consequence of Corollary 1. Corollary 2 An upper 2-cycled graph must be planar. The next theorem characterizes the upper 2-cycled graphs. Although we only use its necessity part to prove the Main Theorem, it has an independent interest. Theorem 2 A graph is upper 2-cycled if and only if it contains no K2 ⊕ 3K1 or K3,3 − e as a minor. Proof. The necessity is Corollary 1 above. Now we prove the sufficiency. By the argument leading to Corollary 2, G must be planar. Assume that, if possible, G is not upper 2-cycled. We assert that G has three cycles C1, C2 and C3 and an edge e such that the following properties hold for an appropriate plane drawing of G: 1. C1, C2 and C3 are distinct chordless cycles containing e; 2. C2 is within C1 and C3 is within C2; the electronic journal of combinatorics 3 (1996), #R14 7 3. C1, C2 and C3 are harmonic with each other. In proving the assertion, we make use of a weaker version of Property 3, namely, 4. C2 is harmonic with C1 and C3. By the assumption that G is not upper 2-cycled, it has three cycles C1, C2 and C3 and an edge e satisfying Property 1. If two of the cycles are harmonic, we rename them as C1 and C3 . If not, we harmonize C3 to C1 with respect to e, and the new C3 is still different from C1 and C2 . In any case, we may assume C3 is within C1 . For the new C1 , C2 and C3 , Property 1 still holds, but now C3 is within and harmonic with C1 . Next, let us consider three cases about C2 . Case 1: C2 has a vertex u inside C3 . We harmonize C2 to C3 with respect to u and e, and switch the names of C3 and C2 . The cycles C1 , C2 and C3 now satisfy Properties 1, 2 and 4. Case 2: C2 has a vertex u outside C1 . We select a face within C3 , make it the outer face, and switch the names of C1 and C3, and we are back to Case 1. Case 3: C2 is between C1 and C3 . We harmonize C1 to C2 and C3 to C2 with respect to e. The cycles C1 , C2 and C3 now satisfy Properties 1, 2 and 4. Thus in all cases, Properties 1, 2 and 4 hold for C1 , C2, C3 and e. By planarity and Property 2 we have C1 ∩ C3 ⊂ C2 , hence C1 ∩ C3 = (C1 ∩ C2 ) ∩ (C2 ∩ C3 ). Since each of C1 ∩ C2 and C2 ∩ C3 is a subpath of C2 , C1 ∩ C3 must be a path or the union of two disjoint paths. In the former case, C1 is harmonic with C3, as required. In the latter case, illustrated in Figure 5, the symmetric difference of E(C2 ) and E(C3) forms a cycle C 0 , and we can find an edge e0 in C1 ∩ C2 such that e0 is also on C 0 . Renaming C 0 as C3 and e0 as e and chord-cutting C3 with respect to the new edge e, we achieve Property 3 for the new C1 , C2 , C3 and e while Properties 1 and 2 remain valid. This completes the proof of the assertion. It follows from the assertion that P13 = C1 ∩ C3 is a path contained in C2 0 0 and containing e. Let P13 (P31 ) be the subpath of C1 − e (C3 − e) between the ends a and b of P13. 0 0 Suppose no internal vertex of P31 is on C2 . Let P13 = (a = x0, x1 , . . . , xk = b), and let i (j) be the largest (smallest) index such that x0, . . . , xi (xj , . . . , xk ) 0 are on C2, as illustrated in Figure 6. Since C1 and C2 are chordless, P31 and 0 P13 [xi , xj ] are not single edges, i.e., each has an internal vertex. For the same reason, the subpath of C2 from xi to xj that does not contain e has the electronic journal of combinatorics 3 (1996), #R14 8 C1 ............................................................ ........... ......... ........ ....... ....... ...... ...... ...... . . . . . ...... .... . . . ..... . .... .... . . . ... .. . . .... . .. . ... . . ... 2 .. . . ... .. . ... . . . . . . . . . . . . . . . . . . . . . .............................................................................. . . . ... . . ... . . . . . . . . .................. ... ..................... . . .. . . . . . . . . . . . . ............. ... .............. . . . .. . . . . . . . . . . ... ............ ............ . . . . ... . . . . .... . . ......... ........... . ... . . . . . ... . ...... .. ......... ....... . ... . .. ... . ...... . . .... .. . . 3 ...... ...... .. . . . .. . ...... ... . . . . . . . . . . . . . . . ....... . . . . . . . . ... . . . . . . . . ........ ...... ... ..... . . ..... . . .. . . . . . . . . . ...... ...... ..... ..... . . .... . . . . ... . . .... ...... .... ... .. . .. . . . . ...... ... .. ... .. ..... . . . . . . . . ... ...... ... . .... . . . . . . . ... .... ... .. . .. .... .. ... ....... ... .... .... .. ... ..... .. ..... .. .. ... ..... .. ..... ...... ... ... ..... . . . . . . ... ... ..... ...... ... ... ... ... ...... ... ....... .... .... .. C C e0 e Figure 5: An illustration for the proof of the assertion. an internal vertex. We contract x0 , . . . , xi into one vertex and xj , . . . , xk into another vertex, and now C1 ∪ C2 ∪ C3 is a subdivision of K2 ⊕ 3K1 , which has K2 ⊕ 3K1 as a minor, contrary to the hypothesis. A similar argument 0 holds if no internal vertex of P13 is on C2 . C1 • .................................................... ............ ......... ......... ....... ....... ...... ...... ...... . . . . . ..... .... . ..... . . . .... ... . . .... ... . ... . .. ... . . ... .. . . ... 2 ... ... . . .. . ....... i ...... ...... ........ ...... . . ...... . . . ...... ........ ..... ..... ................................. . . . ...... . . . .... . . . . . ........ ...... ....... . ..... . . . . . . . ...... .... . . . ....... . . . ...... . ..... .... . ...... .... . 3 . . . .... ...... .. .... . . . . . ... .... .... . ... . . ...... . ... ..... ... ...... ... ...... ... ... ...... ...... ... .... ... ...... ...... . . . . . . . ....... .. .. .. ...... ...... .. ..... .. ...... ... .......... ...... ... ...... .. . ........ . . . ........ .. . ......... .............. .. ... x C • xj • C a = x0 xk = b e Figure 6: An illustration for the proof of Theorem 2. 0 0 If both P13 and P31 have an internal vertex on C2 , there is a subpath P of 0 0 C2 connecting an internal vertex d of P13 to an internal vertex c of P31 such that P has no internal vertex on C1 or C3 . Without loss of generality, we assume that the cycle C2 passes through the vertices a, b, c, d in this order. Then, since C2 is harmonic with both C1 and C3 , C2 must be P13[a, b] ∪