IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1148 ISSN 2232-2094 CHARACTERIZING ALMOST-MEDIAN GRAPHS II Sandi Klavzar Sergey Shpectorov Ljubljana, April 28, 2011 (n Characterizing almost-median graphs II • $H a Sandi Klavzar* Faculty of Mathematics and Physics University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia and Faculty of Natural Sciences and Mathematics University of Maribor Koroska 160, 2000 Maribor, Slovenia < 00 r Sergey Shpectorov School of Mathematics University of Birmingham Edgbaston, Birmingham B15 2TT United Kingdom s.shpectorov@bham.ac.uk 00 £ co co Abstract Let M, A, S, and P, be the sets of median graphs, almost-median graphs, semi-median graphs and partial cubes, respectively. Then M C A C S C P. It is proved that a partial cube is almost-median if and only if it contains no convex cycle of length greater that four. This extends the result of Bresar [2] who proved that the same property characterizes almost-median graphs within the class of semi-median graphs. Key words: partial cube; median graph; convex cycle; almost-median graph HH AMS subject classification (2000): 05C12, 05C75, 05C38 CO CD 1 Introduction CD Median graphs, one of the central classes in metric graph theory, can be characterized as partial cubes for which all sets Uuv are convex. (See Section 2 for the definition of Uuv.) Motivated by this fact, almost-median graphs were introduced in [7] as those partial cubes for which the sets Uuv are isometric. Another reason for this definition a was to better understand the structure of partial cubes and to find faster recognition CD * Supported in part by the Ministry of Science of Slovenia under the grant P1-0297. The author cu is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana. algorithms for partial cubes. Along these lines, it was shown in [3] that prism-free almost-median graphs and some related classes of graphs can be recognized in time O(mlogn), where n is the number of vertices and m the number of edges of a given graph. An algorithm of the same time complexity has bee developed in [8] for an additional class of almost-median graphs that in particular includes all planar almost-median graphs. The fastest recognition algorithm for the general partial cube is due to Eppstein [6]. It is also known that median graphs are the almost-median graphs that contain no convex vertex-deleted Q3, see [7]. For the position of almost-median graphs in the hierarchy of classes of partial cubes see [4]. Several characterizations of almost-median graphs are known. They are precisely the graphs that can be obtained from a single vertex by a sequence of isometric expansions, where in each expansion covering sets induce almost-median graphs [3]. In addition, they can be characterized among partial cubes with the so-called almost-quadrangle property [10]. Our main motivation is the following characterization due to Bresar [2]: A graph G is an almost-median graph if and only if G is a semi-median graphs that contains no convex cycle of length greater that four. Using a closer inspection of convex cycles in partial cubes we prove in this note that an absence of long convex cycles characterizes almost-median among all partial cubes. At least two related results involving forbidden convex subgraphs should be mentioned here. Polat [12] proved that nontrivial netlike partial cubes (the class of graphs introduced in [11]) that contain at most one convex cycle of length greater than four can be characterized with the so-called prism-retractable property. On the other hand, Bandelt and Chepoi [1] proved that graphs of acyclic cubical complexes are precisely median graphs not containing any convex bipartite wheels. co We proceed as follows. In the next section the necessary definitions are collected, co while Section 3 contains a key lemma about convex cycles in partial cubes. In the final section the main result (Theorem 4.1) is obtained in two ways and a short proof of the characterization of almost-median graphs using the almost-quadrangle property is given. fc 2 Preliminaries A subgraph H of a graph G is isometric if dH(u, v) = dG(u, v) holds for any vertices u,v 1 its vertices can be labeled with strings {0,1}d such the distance function of G coincides with the Hamming distance between the strings. A graph G is a median graph if to every triple u, v, w of its vertices there is a o i CSI 00 CSI CSI 00 o I CSI 00 CSI CSI £ co co unique vertex x such that d(u, x) + d(x, v) = d(u, v), d(v, x) + d(x, w) = d(v, w) and d(u,x) + d(x, w) = d(u,w). Median graphs are partial cubes. For an edge uv of a graph G let Wuv = {w | d(u,w) < d(v,w)}. Let Fuv be the set of edges between Wuv and Wvu, and let Uuv be the set of those vertices of Wuv than have a neighbor in Wvu. If G is a partial cube, then the sets Wuv and Wvu partition V(G). Moreover, the sets Fuv, uv £ E(G), partition E(G). The sets Fuv are also known as 0-classes of G since they coincide with the partition of E(G) induced by the Djokovic-Winkler relation 0. A partial cube G is called almost-median if for any uv £ E(G) the set Uuv is isometric and is called semi-median if for any uv £ E(G) the set Uuv is connected. Nonempty isometric subgraphs Gi and G2 form an isometric cover of a graph G provided that V(G) = V(Gi) U V(G2) and E(G) = E(Gi) U E(G2). If G is connected then G1 n G2 = 0 for every isometric cover G1, G2. Suppose G1,G2 is an isometric cover of G. For i = 1, 2, let Gi be an isomorphic copy of Gi, and for a vertex u £ G1 n G2, let ui be the corresponding vertex in Gi. The expansion of G with respect to G1,G2 is the graph G obtained from the disjoint union of G1 and G2, where for each u £ G1 n G2 the vertices u1 and u2 are joined by a new edge in G. We say that the expansion is isometric provided that G1 n G2 is an isometric graph. Chepoi [5] proved that a graph is a partial cube if and only if it can be obtained from K1 by a sequence of expansions. Let F be a 0-class of a partial cube G. Then the contraction of G with respect to F is the graph G' obtained from G by contraction every edge of F. This operation reverses the expansion, in particular G' is also a partial cube. 3 Convex cycles Here is our key lemma: Lemma 3.1 Let G be a partial cube and F a 0-class of G containing edges e and f. Then either (a) there exists an edge g £ F, g = e, f, such that dG(e, f) = dG(e,g) + dG(g, f), or (b) e and f are contained in a unique shortest cycle, and this cycle is convex in G. Proof. Assume that there is no edge g £ F satisfying (a). Let e = e1e2 and f = f1f2, where dG(e1,f1) = dG(e, f) = dG(e2,f2). Consider a shortest cycle C containing e and f. Then C consists of e, a shortest path A from e1 to f1, f, and a shortest path CD B from f2 to e2. We first prove the following: Claim: If a £ A and b £ B then every shortest path between a and b passes through e or through f. Every shortest path T between a and b contains an edge g from F. Suppose that g = e, f and consider I(e1, f2). By the way C is selected, a,b £ I(e1, f2). As intervals in partial cubes are convex, it follows that g1 £ I(e1, f2) as well. But then, having 00 c^ u a < 00 o CSI I w in mind that Weie2 is isometric, d(ei,fi) + 1 = d(ei,f2) = d(ei,gi) + d(gi, f2) = d(ei,gi) + d(gi,fi) + 1 and hence d(ei, fi) = d(ei,gi) + d(gi, fi). As we have assumed that there is no edge g satisfying (a), the claim is proved. As a consequence of the claim, we now have that C is first isometric and then also convex. Indeed, suppose this is not the case and select a shortest geodesic R between vertices of C that is not contained in C. Let a and b be the endpoints of R. By the assumption, none of the edges (or intermediate vertices) of R lie on C. Hence it follows from the claim that a and b are both on A or both on B. Without loss of generality assume a,b £ A. Since A is a geodesic, R cannot be shorter that the path between a and b along A. This shows that C is isometric. To show convexity, consider the cycle C obtained from C where the part between a and b is substituted by R. Then C has the same property as C, in particular it is also isometric. Let ac be the first edge on R. The edge t opposite to ac on C lies on B which is common for C and C. In particular, t is opposite on C to an edge ac'. Since ac and t are opposite in an isometric cycle, they are in the same ©-class. Similarly, ac' and t are in the same ©-class. It follows that ac and ac! are in the same ©-class, a contradiction. Note that since we have proved that C is convex, A is the only shortest path between ei and fi and similarly B is the only shortest path between e2 and f2. Hence C is the unique shortest cycle containing e and f. Note also that the claims (a) and (b) exclude each other. Indeed, if we have an intermediate edge g £ F, then there is a shortest path from ei to fi via gi and similarly from e2 to f2 via g2. This produces a shortest cycle which is not convex. □ The structure of convex cycles was in [9] encoded as follows. Let F be a ©-class of a partial cube G. Then the F-zone graph, Zp, is the graph with V(Zp) = F, vertices f and f being adjacent in Zp if they belong to a common convex cycle of G. We now extend the concept of the zone graph to its weighted version as follows. To every such edge ZF we assign the weight ^-r, where k = \C\ and C is the convex cycle representing the edge. Note that this weight is exactly the distance in G between the two edges of F lying on C. Moreover, Lemma 3.1 immediately implies the following: • Jh Corollary 3.2 The weighted distance in Zp between e, f £ F coincides with dG(e, f). Furthermore, if there is an edge connecting e and f, then this is the unique shortest weighted path between e and f. 4 The main result CD We are now ready for the main result of this note. CSI •rH a < 00 Theorem 4.1 Let G be a partial cube. Then G is almost-median if and only if G contains no convex cycles of length more than four. Proof. It was proven in [2] that every almost-median graph has no convex cycle of length more than four. Hence we just need to show the converse. Suppose G is a partial cube without convex cycles of length more than four. According to the definition of almost-median graphs we need to verify that Uab is isometric for every edge ab. Let F be the ©-class containing ab. Suppose that there are edges e, f £ F such that da(e\, fi) < dUab(ei, fi), where ei and f1 are endpoints of e and f lying in Uab. We may assume that e and f are selected so that dc(e1,f1) is minimal. This condition forces that there is no intermediate edge g £ F as in case (a) of Lemma 3.1. By this lemma it follows that e and f lie in a unique shortest cycle which is convex. By our assumption, this cycle cannot be of length more than four, which means that e1 and f1 are adjacent, a contradiction. □ Another way to deduce Theorem 4.1 is to apply Corollary 3.2. Indeed, the theorem follows from the lemma since in the zone graph all the edge-weights are 1 in the absence of long convex cycles. Therefore, the weighted distance in ZF is the same as the path distance. We conclude this note with a short proof (based on Theorem 4.1) of the characterization of almost-median graphs due to Peterin [10]. For it we need the following definition. A graph G satisfies the almost-quadrangle property if for any vertices u, w, x, y such that d(u, x) = d(u, y) = k = d(u, w) — 1 and w is adjacent to x and y, there exists an edge ab such that axwb is an induced C4 of G and d(u, a) = k — 1. i CSI 00 CSI CSI Corollary 4.2 ([10, Corollary 6]) Let G be a partial cube. Then G is almost-median if and only if G satisfies the almost-quadrangle property. Proof. Suppose G is almost-median and let u,w,x,y be vertices of G such that d(u, x) = d(u, y) = k = d(u, w) — 1 and w is adjacent to x and y. Let P be a shortest x, u-path and Q a shortest y, u-path. Let F be the ©-class of G containing xw. Then Q contains an edge x'w' £ F, where d(x',x) < d(x',w). Note that x' £ I(u, x). Since G is almost-median, Uxw contains a geodesic P' between x and x'. Let a be the neighbor of x on P' and let b be the neighbor of a in Uwx. Then ab is the required edge, hence G satisfies the almost-quadrangle property. CO Conversely, suppose G satisfies the almost-quadrangle property. If G contained a convex cycle of length more that four, then we could choose u and w to be opposite vertices on the cycle and then by the convexity a must be on the cycle and hence CD CD b must also be on the cycle, a contradiction. We conclude that G is almost-median by Theorem 4.1. □ References [1] H.-J. Bandelt, V. Chepoi, Graphs of acyclic cubical complexes, European J. Combin. 17 (1996) 113-120. 00 CO CD u CD CO a CD U [2] B. Bresar, Characterizing almost-median graphs, European J. Combin. 28 (2007) 916-920. [3] B. Bresar, W. Imrich, S. Klavzar, Fast recognition algorithms for classes of partial cubes, Discrete Appl. Math. 131 (2003) 51-61. J-i a [4] B. Bresar, W. Imrich, S. Klavzar, H. M. Mulder, R. Skrekovski, Tiled partial cubes, J. Graph Theory 40 (2002) 91-103. [5] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 1 (1988) 6-9. i—l [6] D. Eppstein, Recognizing partial cubes in quadratic time, in: Proc. 19th Annual ACM-SIAM Symp. Discrete Alg., 1258-1266, ACM, New York, 2008. o [7] W. Imrich, S. Klavzar, A convexity lemma and expansion procedures for bipartite graphs, European J. Combin. 19 (1998) 677-685. [8] W. Imrich, A. Lipovec, I. Peterin, P. Zigert, Fast recognition of classes of almost-median graphs, Discrete Math. 307 (2007) 464-471. [9] S. Klavzar, S. Shpectorov, Convex excess in partial cubes, to appear in J. Graph Theory, DOI: 10.1002/jgt.20589. CO [10] I. Peterin, Quasi-almostmedian graphs, to appear in Ars Combin. [11] N. Polat, Netlike partial cubes. I. General properties, Discrete Math. 307 (2007) 2704-2722. co [12] N. Polat, Netlike partial cubes. II. Retracts and netlike subgraphs, Discrete Math. 309 (2009) 1986-1998.