nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

当前位置：首页 >> >> Avant--propos

Cellular bipartite graphs

Hans{Jurgen Bandelt and Victor Chepoi 1

Mathematisches Seminar Universitat Hamburg Bundesstr. 55 D-20146 Hamburg, Germany

In this paper we investigate the graphs that are obtained from single edges and even cycles by successive gated amalgamations. These "cellular" graphs are characterized among bipartite graphs by having a totally decomposable shortest{path metric, and can be recognized by a quadratic time algorithm.

1

Research supported by the Alexander von Humboldt Stiftung, on leave from the Universitatea de stat din Moldova, Chisinau

Avant{propos

Graphs with their shortest{path metrics are particular instances of nite metric spaces, and may thus be investigated from the metric point of view. Although the theory of nite metric spaces is not yet fully developed, some facets are already well studied; cf. 4,10]. The l1 {embeddability question for metric spaces prompted the investigation of l1 {graphs 9,13]. A particular class of nite l1 {spaces, possessing a rich theory, are formed by the totally decomposable spaces, in which the summands in a (canonical) l1 {decomposition would obey a certain compatibility rule 4]. It is the purpose of this note to demonstrate that the bipartite graphs with totally decomposable metric have a convenient decomposition scheme, the ingredients of which are gated amalgamation as a fundamental operation and even cycles and single edges as building stones.

Total decomposability

The simplest (pseudo{) metrics on a nite set X are the "split" alias "cut" metrics S associated with the splits S = fA; B g of X; i.e., partitions of X into two nonempty subsets A; B : ( 0 if x; y 2 A or x; y 2 B; S (x; y) = 1 otherwise.

By de nition, an l1 {metric d on X is any positive linear combination of split metrics: P ( ) d = S 2Z S S with S > 0 for all S from a collection Z of splits. A totally decomposable metric d on X is a particular l1 {metric, which admits a "feasible" representation ( ) with a collection Z consisting of triplewise "weakly compatible" splits. Three splits fAi ; Bi g (i = 1; 2; 3) are said to be weakly compatible if A1 \ A2 \ A3 6= ; implies B1 \ B2 \ B3 = Bi \ Bj for some i; j ; or equivalently, there is no 4{subset Y of X such that the three splits fAi ; Bi g would induce the three distinct splits on Y separating two from two points. The weight S of a split S = fA; B g participating in a feasible representation ( ) is then determined as the isolation index 1 min A;B = 2 a;a A (maxfd(a; b) + d(a0 ; b0 ); d(a; b0 ) + d(a0 ; b);

b;b B

02 02

see 4]. The metrics obtained from trees or cycles are simple instances of totally decomposable metrics. Two facts concerning totally decomposable metrics are needed here. First, recall that a subset A of a metric space (X; d) is convex if the (metric) interval I (u; v) = fx 2 X : d(u; x) + d(x; v) = d(u; v)g between any two points u and v of A lies entirely in A: The convex hull conv(Y ) of a subset Y is the smallest convex set containing Y:

Fact 1 ( 4, Proposition 3 and its proof]). If d is a totally decomposable metric on X; then

d(a; a0 ) + d(b; b0 )g ? d(a; a0 ) ? d(b; b0 ));

conv(Y ) =

u;v2Y

I (u; v)

1

for every set Y

X:

A condition on subspaces stronger than "convex" is the following. A subset Y of X is gated if for every point x 2 X there exists a (unique) point x0 2 Y (the gate for x in Y ) such that x0 2 I (x; y) for all y 2 Y ; cf. 12].

Fact 2 ( 4, Proposition 2]). If X is covered by two intersecting proper gated subsets Y and

Z such that the restrictions of the metric d to Y and Z are totally decomposable, then d is

totally decomposable. In the preceding situation we say that X is a gated amalgam of Y and Z (along Y \ Z ). Gated amalgamations play an important role in structure theories of classes of graphs generalizing median graphs; see 6, 7, 14].

Main results

We can now state the characterization of bipartite graphs with totally decomposable metrics. Since they are built up from cycles (their "cells"), we dub them cellular graphs. All graphs considered here are assumed to be nite.

Theorem 1. For a bipartite graph G = (V; E ) with at least two vertices the following

conditions are equivalent:

(1) the metric d of G is totally decomposable; (2) conv(u; v; w) = I (u; v) I (v; w) I (w; u) for all u; v; w 2 V ; (2') conv(X ) = x;y2X I (x; y) for all X

V;

(3) every isometric cycle of G is gated, and G does not contain any three isometric cycles C1 ; C2 ; C3 and three distinct edges e1 ; e2 ; e3 sharing a common vertex such that ei belongs to Cj exactly when i 6= j (see Figure 1); (4) G can be obtained from a collection of single edges and even cycles by successive gated amalgamations; (5) the splits S (u; v) = fW (u; v); W (v; u)g for uv 2 E are triplewise weakly compatible, where W (u; v) = fx 2 V : d(u; x) < d(v; x)g = fx 2 V : u 2 I (v; x)g and W (v; u) = V ? W (u; v):

2

x2

. .

x3

u

.

.

"b " b

u

.

.

.

y1

e

C2

H H

.

.

e y3

Z Z

H H

u

C3

x0

.

C1

.

.

u

b b

. . . y2 . . .

Z Z

e

D D " "

x1

Figure 1. An obstruction to total decomposability.

Condition (2') entails the Peano property ("join{hull commutativity", cf. 14]), stating that the convex hull of the union of a convex set Y with a vertex x equals the union of all intervals I (x; y) with y from Y: According to 8], a bipartite graph G having the Peano property also enjoys the Pasch property 14], which then guarantees that any two disjoint convex sets A and B are separated by some "convex" split S (u; v); that is, there exists an edge uv in G such that W (u; v) and W (v; u) are convex and include A and B; respectively. Summarizing, a cellular bipartite graph G is a Pasch{Peano graph sensu 14] (alias "join space"). As a simple consequence of this in conjunction with condition (5) note that for any four vertices x1 ; x2 ; x3 ; x4 at least one intersection I (x1 ; xi ) \ I (xj ; xk ) with fi; j; kg = f2; 3; 4g is nonempty. In particular, the Radon number (as de ned in 14]) is at most 3. The graphical representation of a totally decomposable metric by a network as described in 4,5] would recover a cellular bipartite graph from its metric. In general, however, not every network corresponding to a totally decomposable metric would yield a cellular bipartite graph (after disregarding edge lengths): the obstruction shown in Figure 1 would often arise; cf. 5, Figures 0,1,3]. We say (by slight abuse of language) that a gated cycle of length k is pendant in G if it 1 includes a path of length 2 k ? 2; all vertices of which have degree 2 in G: Removing this path from G then results in an isometric subgraph and hence again a cellular bipartite graph. The structural information on cellular bipartite graphs that is gathered in the proof of Theorem 1 allows to immediately derive the following fact, which establishes an elimination scheme for cellular bipartite graphs.

Theorem 2. Every cellular bipartite graph with at least two vertices has either two pendant

vertices or a pendant gated cycle.

In each step the number of edges is decreased by at most twice the number of deleted vertices until one reaches a path with three vertices. Therefore the number m of edges of a cellular bipartite graph with n 3 vertices is bounded above by m 2n ? 4: We p conjecture that actually b2(n ? n)c is an upper bound for m; which is sharp for every n 3

(being attained in a subclass of cubefree median graphs). Cubefree median graphs 3] are built up by gated amalgamations from single edges and 4{cycles exclusively, that is, they are the cellular bipartite graphs in which all gated cycles have length 4. In particular, Theorem 2 generalizes the vertex elimination scheme for cubefree median graphs, established in 1, Corollary 2]. We can actually further specify the gated amalgamations needed to build up all cellular bipartite graphs. A cutset R of a connected graph G is any subset (or subgraph) for which G ? R is disconnected. It is evident that every gated cutset R induces a representation of G as a gated amalgam of two gated subgraphs G1 and G2 along R (and vice versa): the union of R and any component of G ? R may serve as G1 ; while R together with the other component(s) of G ? R then gives G2 :

Theorem 3. Every cellular bipartite graph either is indecomposable (i.e., comprises a single vertex, or a single edge, or an even cycle) or possesses a gated cutset that is a tree.

The proof of Theorem 3 (being rather constructive) entails a polynomial time algorithm for nding a gated tree cutset. Figure 2 illustrates a gated amalgam of two cellular bipartite graphs along a tree.

u u u u u u u u

"

u

@ @ @

u

u u u u u

# # #

u

" "

@ @

@ ,

u u

u u

" "

u u u u

u u

, ,

,

u

"

u u u

u u u u

Figure 2. A cellular bipartite graph and (in bold) a gated cutset.

The Cartesian product of a 3{star with itself (being a cubefree median graph) is a cellular graph which is not planar (since it contains a homeomorph of K3;3 ): Nevertheless, we have a kind of Euler formula when one considers gated cycles instead of "faces":

4

Corollary 1. Let G be a cellular bipartite graph with n vertices, m edges, and g gated

cycles. Then

n ? m + g = 1:

Proof. We proceed by induction. If G is indecomposable, then the equality trivially holds. So, let G be a gated amalgam of two gated subgraphs G1 and G2 along a tree G0 (= G1 \ G2): Let ni ; mi ; gi be the numbers of vertices, edges, and gated cycles, respectively, of Gi (i = 0; 1; 2): Then, by the induction hypothesis, we obtain

n ? m + g = n1 + n2 ? n0 ? m1 ? m2 + n0 ? 1 + g1 + g2 = 1;

using the fact that g0 = 0 and m0 = n0 ? 1: 2 The cycle space of any graph G is the linear space over GF(2) having all Eulerian subgraphs (in which the vertices have even degrees) as its elements, with symmetric di erence as (Boolean) addition. A simple fact is that every cycle is a Boolean sum of isometric cycles ({ proof by induction on the length). Therefore one would always nd a basis of the cycle space comprising only isometric cycles. It is well known that m ? n + 1 is the dimension of this space. For a cellular bipartite graph G; this number equals g; whence we obtain the following fact. cycle space of G:

Corollary 2. The gated cycles of a cellular bipartite graph G constitute a basis of the

Proof of Theorems 1 and 2

The implication (20 ) ) (2) is trivial, while (1) ) (20 ) and (4) ) (1) are covered by Facts 1 and 2. (2) ) (3) : We claim that every isometric cycle C is gated. Suppose the contrary: then there is a vertex x outside C having no gate in C; that is, a vertex w of C at minimum distance to x cannot lie in the interval between x and the vertex w0 opposite to w on C: Let v and y be the two neighbours of w on C: Since w belongs to I (v; x); we have

y 2 C conv(v; w0 ; x) = I (v; w0 ) I (w0 ; x) I (x; v)

by the hypothesis (2). Since w 2 I (v; y) \ I (x; y) ? I (w0 ; x); we cannot allocate y to any of the three intervals in question. This con ict settles the claim. Next suppose we could nd three gated cycles C1 ; C2 ; C3 sharing a common vertex x0 such that each pair Ci ; Cj intersects in an edge x0 yk for fi; j; kg = f1; 2; 3g with y1 ; y2 ; y3 being distinct; see Figure 1. Let xi be the vertex opposite to x0 on Ci (i = 1; 2; 3): Then the union I (x1 ; x2 ) I (x2 ; x3 ) I (x3 ; x1 ) contains y1 ; y2 ; y3 but not x0 : This, however, violates (2) as x0 2 I (yj ; yk ) for j 6= k; thus nally establishing (3). To prove that (3) implies (4), we need an auxiliary result concerning the Djokovic relation of a bipartite graph G = (V; E ): De ne for any edges uv and xy of G;

uv

xy , either x 2 W (u; v) and y 2 W (v; u);

5

or y 2 W (u; v) and x 2 W (v; u); which is, of course, equivalent to either u 2 W (x; y) and v 2 W (y; x); or v 2 W (x; y) and u 2 W (y; x): The relation is transitive (and hence an equivalence relation on E ) if and only if G can be represented as an isometric subgraph of some hypercube 11]. We may compare to the following relation : First say that two edges uv and xy are in relation if they either are equal or constitute opposite edges on some gated cycle C of G: Then let be the transitive closure of on the edge set E:

Lemma 1. Let G be a bipartite graph in which every isometric cycle is gated. Then the relations and on the edge set of G coincide. In particular, G is isometrically embeddable into a hypercube. Proof. We rst claim that : Let xy and y0x0 be opposite edges of some gated 0 being opposite on C ), and assume uv xy for some edge uv of G; cycle C (with x and x say x 2 I (u; y) and y 2 I (v; x): Then the gate of u in C belongs to the path I (x; y0 ); whence y0 2 W (u; v): Similarly, we infer x0 2 W (v; u); and therefore uv y0 x0 ; which settles the

claim. A trivial induction yields

k = k?1

;

k k

and hence

=

:

In order to show that includes ; proceed by induction on the distance k between two distinct edges uv and xy in the relation :

k = min(d(u; x); d(u; y); d(v; x); d(v; y)) 1; say, d(u; x) = d(v; y) = k: Select any shortest paths P and Q joining the pairs u; x and v; y; respectively. If the cycle C formed by P; Q together with the edges uv; xy is isometric (and hence gated), then trivially uv xy: Otherwise, some vertex w of P is connected by a path R to some vertex z of Q such that R is shorter than both paths connecting w and z along C: Necessarily, R includes some edge rs with r 2 W (u; v) and s 2 W (v; u); so that rs uv: By the choice of R we obtain d(u; r) < d(u; x); and therefore uv rs by the induction hypothesis. In view of symmetry we have xy rs as well. Then as is an equivalence relation we conclude uv xy: This yields ; and in conjunction with

2

establishes the desired equality. According to the theorem of Djokovic 11] transitivity of ensures isometric embeddability into a hypercube. This completes the proof of the lemma.

Lemma 2. Assuming condition (3) of Theorem 1, let D be a non{trivial block of the equiv-

alence relation = ; and let F be the union of all gated cycles containing edges from D: Then for any edge uv of D; both

F1 = F \ W (u; v) and F2 = F ? F1 = F \ W (v; u) are convex trees in G: Moreover, F1 is gated in the convex subgraph W (u; v) and F2 is gated in W (v; u):

6

Proof. Each gated cycle containing an edge of D shares exactly two opposite edges with D; and thus attributes a path to F1 and F2 each. Therefore F1 and F2 constitute connected subgraphs of G: Suppose that F1 is not a convex tree in G : choose a path P in F1 of smallest

length k which is not convex in G: Then necessarily, there is a shortest path R in G of length k intersecting P only in the end vertices y and z: We claim that the cycle C1 formed by P and R is isometric and hence gated. Indeed, otherwise we could nd interior vertices p of P and r of R that are connected by a shortest path having no interior vertex in common with P and R: Let q be the neighbour of p on this path. Since G is an isometric subgraph of a hypercube, all intervals are convex. Consequently, q 2 I (p; r) I (y; z ); and thus q belongs to either I (p; y) or I (p; z ): As these two intervals constitute (convex) subpaths of P; we arrive at a contradiction. This proves the claim that C1 is gated. Then C1 does not contain any edge from D because P is included in F1 : On the other hand, P is composed of subpaths of gated cycles that share edges with D: Therefore there must exist an interior vertex x of P such that the two edges xx2 and xx3 from P incident with x belong to gated cycles C3 and C2 ; respectively, that also have edges with D in common. If C2 and C3 share yet another vertex x1 ; then the three cycles C1 ; C2 ; C3 and edges xx1 ; xx2 ; xx3 would contradict the hypothesis (3). Hence x (being the unique common vertex of C2 and C3 ) is the gate in C2 of each vertex of C3 ; and vice versa. This, however, con icts with the fact that some edge of C2 is in relation to another edge of C3 : This contradiction nally proves that F1 and (analogously) F2 are convex trees in G: Suppose that F1 is not gated in W (u; v): Choose a vertex z 2 W (u; v) at minimum distance to F1 having no gate in F1 : Let r be a vertex of F1 closest to z; and let t be a vertex of F1 such that the interval I (z; t) does not contain r; where d(r; t) is as small as possible. Then the neighbour s of t on the path I (r; t) satis es r 2 I (z; s): By minimality of d(r; z ); any neighbour y of z in I (r; z ) is closer to s than to t: Therefore the edges st and yz are in relation : Applying the rst part of the proof to the block of containing these two edges, we infer that the intervals I (s; y) and I (t; z ) are (disjoint) convex paths. Then the cycle C1 formed by these two paths together with yz and st must be induced, for otherwise, either I (r; t) could not be a convex path, or the intersection of I (z; r) and I (z; t) would contain a vertex di erent from z; thus violating minimality of d(r; z ): If C1 is not isometric, then there exists a shortest path of length at least 2 between a vertex p 6= y of I (s; y) and a vertex w of I (t; z ) which intersects C1 only in p and w: Since intervals in G are convex and G is bipartite, the neighbour q of p on this path would necessarily belong to I (s; z ): Then, as p 6= y and I (s; y) is a convex path, it follows that q 2 I (p; z ) ? I (p; y): Therefore pq yz: Since then pq st and I (r; t) is a convex path, we must have p 2 I (r; z); whence q 2 I (r; z) \ I (t; z); contradicting the minimality choice of z: So, C1 is indeed a gated cycle (included in the convex subgraph W (u; v) by construction). Since I (r; t) is a path of length at least 2 shared by F1 and C1 ; there must be a subpath x2 ; x; x3 of I (r; t) such that the edges x2 x and xx3 belong to some gated cycles C3 and C2 ; respectively, which each have two edges in common with D: Then, as in the rst part of the proof, we eventually obtain a forbidden con guration (Figure 1). We nally conclude that F1 and F2 are gated subgraphs of W (u; v) and W (v; u); respectively. 2 Now, we have the essential prerequisites at hand to accomplish the proof of (3) ) (4): Assume that G is neither a single edge nor an even cycle. We may further assume that G is 2{connected (i.e., without cut vertex), for otherwise, G could be decomposed via gated amalgamation along a single vertex. In particular, every edge of G lies on some cycle { 7

actually on some gated cycle because cycles in G:

=

: Hence there are at least two distinct gated

Case 1: There exist two disjoint gated cycles C1 and C2 : Take an edge uv of a path joining a vertex from C1 with one from C2 which has smallest length. Then W (u; v) includes C1 ; say, while W (v; u) includes C2 : Let F1 and F2 be de ned for the {block containing uv as

in the previous lemma. Since Ci is not included in the tree Fi (i = 1; 2); Fi (i = 1; 2) is a cutset. Then, by virtue of Lemma 2, both W (u; v) F2 and W (v; u) F1 are proper gated subgraphs of G amalgamated along F = F1 F2 :

We may therefore assume that the gated cycles of G pairwise intersect. Then necessarily, they all have some vertex v in common (cf. 2, Proposition 2.4]). Note that G is covered by its gated cycles since every edge lies on a gated cycle.

Case 2: All gated cycles intersect in a single edge. Then G is the gated amalgam of any

gated cycle and the union of the other gated cycles (along that common edge).

Case 3: The gated cycles intersect in the vertex v but do not share a common edge. Since G is 2{connected, two distinct gated cycles C1 and C2 of G intersect in an edge, which is necessarily incident with v; say, uv: Let C1 ; : : : ; Ck (k 2) be the gated cycles containing uv;

and let wi be the neighbour of v on Ci di erent from u (i = 1; : : : ; k): Consider the {block D containing uv; and de ne F; F1 ; F2 as in Lemma 2. Then the union C1 : : : Ck coincides with the gated subgraph F: The union F 0 of all other gated cycles of G intersects F in v and a subset of fw1 ; : : : ; wk g: Evidently, F \ F 0 is a cutset of G; and induces a star. Since F2 is gated in W (v; u); it easily follows that F \ F 0 is a gated cutset of G; whence G is the gated amalgam of F and F 0 in this case. Therefore the implication (3) ) (4) is settled. It remains to prove that (5) is equivalent to (1), say. This can actually be derived from 9, Proposition 3.1 and its proof]. Alternatively, one could verify the implications (1) ) (5) ) (3) directly as follows. Assuming (1), for every edge uv of G; any d{split fA; B g with u 2 A and v 2 B must coincide with S (u; v) because its parts A and B are necessarily convex. This establishes (5) since d{splits are weakly compatible. Finally, assume that (5) holds. We will show that G satis es condition (3). Suppose that there exists an isometric cycle C which is not gated. Then we select vertices x; w; w0 ; v; y as in the proof of the implication (2) ) (3): Choose a neighbour x0 of x in I (w; x): Then the three splits S (v; w); S (w; y); S (x; x0 ) and the four vertices v; w0 ; x; y constitute an obstruction to weak compatibility. We conclude that all isometric cycles in G are gated. Next suppose that three gated cycles C1 ; C2 ; C3 pairwise intersect in edges x0 y1 ; x0 y2 ; x0 y3 as indicated in Figure 1. Let xi be the vertex opposite to x0 on Ci (i = 1; 2; 3): Then the splits S (x0 ; y1 ); S (x0 ; y2 ); S (x0 ; y3 ) and the vertices x0 ; x1 ; x2 ; x3 yield an obstruction. The proof of Theorem 1 is now complete. It remains to verify Theorem 2. Take any edge yz of G and select edges uv and u0 v0 with W (u; v) W (y; z) and W (v0 ; u0 ) W (z; y) such that W (u; v) and W (v0 ; u0) have as fewest vertices as possible. Let F comprise the edge uv and (if there are any) the gated cycles containing edges {equivalent to uv (cf. Lemma 2). In a similar way, the edge u0 v0 gives rise to a gated subgraph F 0 : In case F1 = F \ W (u; v) would not equal W (u; v); we could nd a neighbour s of some vertex t 2 F1 outside F: Then W (s; t) W (u; v) ? fug; contrary to the choice of W (u; v): Therefore G = F W (v; u); and analogously, G = W (u0 ; v0 ) F 0 : 8

If G has at most one pendant vertex, at least one of the disjoint sets F1 and F 0 \ W (v0 ; u0 ) does not include any pendant vertex of G; say, the former. Then F1 is a tree with at least two vertices. Any pendant vertex of this tree lies on a unique gated cycle of G; which is necessarily pendant in G: This concludes the proof.

Proof of Theorem 3

Two auxiliary results are established rst.

Lemma 3. Let u; v and w be vertices of a cellular bipartite graph G such that the intervals I (u; v); I (v; w); I (w; u) intersect each other only in the common end vertices. Then the union C = I (u; v) I (v; w) I (w; u) constitutes a gated cycle of G: Proof. We already know from Theorem 1 that C is a convex subset. Suppose that x and

y are adjacent vertices of C which do not together lie in any one of the three constituent intervals, say, x 2 I (u; v) and y 2 I (u; w) with x; y 6= u: Then, as G is bipartite, either x or y would belong to I (u; v) \ I (u; w); contrary to the hypothesis of the lemma. It follows that any shortest path between two vertices x and y from di erent constituent intervals I (u; v); I (u; w); I (v; w) of C passes through either the common end vertex of the two intervals containing x and y or the other two end vertices. Therefore any cycle formed by three shortest paths from u to v; from v to w; and w to u; respectively, is necessarily isometric and thus gated, whence it must coincide with C: 2

The following result, being of independent interest, expresses that the gated cycles determine the system of all gated sets in a cellular bipartite graph (just as the 4{cycles do in the case of median graphs).

Proposition 1. A connected subgraph A of a cellular bipartite graph G is gated if and only Proof. Necessity is evident: if a gated cycle C intersects a gated subgraph A in at least two

if every gated cycle of G intersecting A either is included in A or intersects A in a single vertex or edge.

non{adjacent vertices, then C must entirely be included in A: As to the converse, we will rst show that A is convex. Suppose the contrary: then there are vertices v and x of A such that A does not include I (v; x); where v and x are chosen so that their distance in the connected graph A is as small as possible. Then there exists a shortest path Q between v and x which is not included in A: Let P be any path of minimal length joining v and x within A; and let u be the neighbour of v on P: By the choice of v; x the paths P and Q only intersect in the end vertices. If P were longer than Q; then, by virtue of the minimality assumption, both the subpath of P from u to x and the path composed of uv and Q would be shortest paths lying entirely in A: Therefore P must have the same length as Q: By the choice of v and x; the neighbour w of v on Q does not belong to A; and the intervals I (u; x) and I (w; x) have no other vertex in common than x: If x is adjacent to u and w; then P Q (comprising u; v; w; x) would be a gated 4{cycle. Otherwise, 9

I (u; w) \ I (u; x) = fug and I (u; w) \ I (w; x) = fwg: Hence, by Lemma 3, P Q is a gated

cycle (of length at least 6). Thus in either case, we obtain a gated cycle which properly intersects A in more than two vertices. Therefore A is indeed convex. Finally suppose that A is not gated. Choose a vertex z at minimum distance to A having no gate in A: Let x be a vertex of A closest to z; and let y be a vertex of A such that the interval I (y; z ) does not contain x; where d(x; y) is as small as possible. Then the intervals I (x; y); I (y; z); and I (z; x) intersect each other only in the common end vertices. By Lemma 3 the union of these intervals is a gated cycle. The intersection of this cycle with A is the path connecting x and y in A: Since x and y are not adjacent, we obtain a contradiction to the initial hypothesis. 2 We next record an immediate consequence of Proposition 1 to be used below. We say that a graph G is a convex amalgam of two convex subgraphs G1 and G2 if G = G1 G2 and G1 \ G2 6= ;: Note that the convex amalgam of cellular bipartite graphs need not be cellular since the obstruction constituted by three cycles as displayed in Figure 1 can be generated from two cellular graphs by a single convex amalgamation (as long as one of the three cycles has length larger than 4).

Corollary 3. Let G1 and G2 be convex subgraphs of a cellular bipartite graph G such that G is the convex amalgam of G1 and G2 : If T1 and T2 are gated cutsets of G1 and G2 ; respectively, such that G1 \ T2 = G2 \ T1 6= ;; then T = T1 T2 is a gated cutset of G: Proof. T is evidently a connected cutset of G: Since every gated cycle in G is entirely included in either G1 or G2 ; we infer from Proposition 1 that T is gated. 2

In order to accomplish the proof of Theorem 3 we will actually verify a stronger assertion. Note that G contains at least one edge belonging to two distinct gated cycles whenever G is 2{connected.

Claim. Every edge xy that belongs to at least two gated cycles extends to a gated tree cutset

of G:

We proceed by induction on the number of vertices. If G has a cut vertex, then the claim is settled by virtue of the induction hypothesis. Therefore we can assume that G is 2{connected. If all gated cycles intersect in a common vertex, then the proof of Theorem 1 (Cases 2 and 3) shows that the given edge xy extends to a gated star cutset. Hence (by Case 1 of that proof) we can nd an edge uv (not necessarily distinct from xy) such that G is a gated amalgam of the subgraphs G1 = W (u; v) F and G2 = W (v; u) F; where F consists of uv and the union of all gated cycles containing edges {equivalent to uv (cf. Lemma 2). We may assume without loss of generality that the edge xy is included in G2 but not in F1 = W (u; v) \ F: Then the gated cycles containing xy necessarily lie entirely in G2 ; and thus by the induction hypothesis, we can extend xy to a gated tree cutset T2 of G2 : If T2 is disjoint from F1 ; then T2 is also a gated cutset of G; as required. So assume that T2 shares some vertex s with F1 : Then T2 (being connected) must contain some vertex t of the cutset F2 = W (v; u) \ F as well. Since T2 is a gated tree in G2 ; it follows that st is an edge constituting the intersection of T2 with F: If s is a pendant vertex of F1 ; then s has at most one neighbour in G2 ? T2 ; whence T2 ? fsg would be a gated tree cutset of G2 avoiding 10

F1 and thus constituting a cutset of G: Otherwise, st lies on at least two gated cycles (from G1 ): By the induction hypothesis, st is included in some gated tree cutset T1 of G1 : Clearly T1 \ F = T2 \ F holds, and therefore T = T1 T2 is the desired tree cutset of G (according

to Corollary 3).

Quadratic time recognition

Polynomial time algorithms for testing cellularity could employ conditions (1),(2) and (5) of Theorem 1. A more e cient approach is based on the elimination scheme set up by Theorem 2. Quadratic time complexity can be guaranteed since the total length of all gated cycles is bounded linearly in the number of vertices.

Lemma 4. Let G be a cellular bipartite graph with n

cycles. Then m exceed 4n ? 12.

2n ? 4 and g

3 vertices, m edges, and g gated n ? 3: The sum of lengths of all gated cycles does not

the total length of the gated cycles, proceed by induction. For n = 3 the assertion holds. So let n 4: If G has a pendant vertex, the conclusion is trivial. Otherwise, select a pendant cycle C of length k and remove a maximal subpath consisting of p k ? 1 vertices of degree 2 2 in G: We have then erased exactly one gated cycle having at most 2p + 2 4p edges. This concludes the induction. 2 Now, the algorithm proceeds as follows. Given a graph G with n 3 vertices, we rst check whether the number of edges is at most 2n ? 4: If so, we continue to compute the distance matrix d of G in quadratic time, and further test whether G is bipartite. With the distance matrix in hand, we can compute for each pair u; v of vertices the number of neighbours of v in I (u; v); this can be achieved in quadratic time. Then we start a recursion with G0 = G in order to dismantle G; thereby determining all gated cycles. Assume the (isometric) subgraph Gi is under processing. Check whether Gi has a pendant vertex x: If so, put Gi+1 = Gi ? fxg and continue. Otherwise, we search for maximal paths all vertices of which have degree 2 in G: This search can be organized so that no vertex is visited more than once. We accept such a path P with p vertices if for the neighbours u and v in Gi ? P of the end vertices x and y of P; either d(u; v) p ? 1 (so that P is not a shortest path), or v has a second neighbour in I (u; v) (that is, P is a shortest path but not the unique one). Select any shortest path Q joining u and v in Gi disjoint from P: Then P; Q together with the edges ux and vy constitute a cycle C: For each vertex v of G determine a vertex v of C at minimum distance to v; and check whether v serves as the gate of v in C: If C is found and proven to be gated (otherwise, G would not be cellular), C enters the list of gated cycles, and Gi+1 is set equal to Gi ? P: This recursive step has a complexity of order n times the length of C: The recursion eventually stops when the number of vertices of Gi+1 has reached 3. The total number of steps is of the order n times the total length of the gated cycles, and hence of quadratic order in view of Lemma 4. Finally, for each vertex x0 of a gated cycle C1 check whether x0 has a neighbour y0 such that x0 y0 belongs to two distinct gated cycles C2 and C3 ; which share with C1 the two neighbours y3 and y2 ; respectively, of x: Again this search requires a number of steps bound by a quadratic polynomial in n (by Lemma 4). 11

Proof. We already know that the rst two inequalities must hold. To verify the bound on

Thus, with the help of the elimination scheme of Theorem 2, we can test condition (3) of Theorem 1 in quadratic time.

Median vertices and cycles

The cellular structure of a cellular bipartite graph G is also re ected by a median property for triplets of vertices. Recall that any three vertices u; v; w in a median graph admit a unique median vertex x (thence the name "median graph"), that is,

I (u; v) \ I (v; w) \ I (w; u) = fxg:

For cellular bipartite graphs which have constituent gated cycles other than 4{cycles, gated cycles serve as substitutes for median vertices: we say that a gated cycle C of length k is a median cycle for a triplet u; v; w of vertices if the gates x; y; z of u; v; w; respectively, satisfy

x; y 2 I (u; v); y; z 2 I (v; w); z; x 2 I (w; u); see Figure 3. The cycle C is the union of the three intervals I (x; y); I (y; z ); and I (z; x): It is determined by the pairwise intersections of the intervals I (u; v); I (v; w); I (w; u); giving rise to the gates x; y; z rst, according to the next proposition. ue

maxfd(x; y); d(y; z ); d(z; x)g < k ; 2

.. ..

u

x

Q Q

.

z

..

..

Q

..

C

.. . ..

..

.

y

u

Q Q Q

. ..

w

e

Q Q Q

u

..

.

Q Q Q

e

v

Figure 3. The median cycle C of three vertices u; v; w:

12

Proposition 2. For any three vertices u; v; w of a cellular bipartite graph G; there exists a (necessarily unique) vertex x such that

I (u; v) \ I (u; w) = I (u; x): In other words, the vertex set of G is a semilattice with respect to the base{point order de ned by y u z if and only if y 2 I (u; z ):

u

proposition such that d(u; v) + d(u; w) is as small as possible. Then we can nd two distinct vertices x and y such that both I (u; x) and I (u; y) are properly contained in I (u; v) \ I (u; w); while I (x; v) \ I (x; w) = fxg and I (y; v) \ I (y; w) = fyg: We claim that

Proof. Suppose the contrary: then select a triplet u; v; w violating the assertion of the

I (x; v) \ I (x; y) = fxg and I (y; v) \ I (y; x) = fyg: Indeed, if the rst equality were not true, then we could nd a vertex z in I (x; v) di erent from x; which would also belong to I (x; y) I (u; w) (as intervals are convex in G) and hence to I (x; w); thus contradicting the choice of x: Similarly, we obtain the second equality and

the analogous pair of equalities

I (x; w) \ I (x; y) = fxg and I (y; w) \ I (y; x) = fyg: The minimality of d(u; v) + d(u; w) guarantees that I (v; x) \ I (v; y) = fvg and I (w; x) \ I (w; y) = fwg:

In view of the above six equalities, we infer from Lemma 3 that the unions I (v; x) I (x; y) I (y; v) and I (w; x) I (x; y) I (y; w) constitute two distinct gated cycles, which intersect in two non{adjacent vertices, viz., x and y; thus yielding the desired contradiction. 2

Proposition 3. Every triplet u; v; w of vertices of a cellular bipartite graph G admits either

a unique median vertex or a unique median cycle.

Proof. Let x; y; z be the vertices successively determined by

I (u; v) \ I (u; w) = I (u; x); I (v; x) \ I (v; w) = I (v; y); I (w; x) \ I (w; y) = I (w; z); according to Proposition 1. If x = y = z; then this vertex is the unique median vertex. Otherwise, the three vertices are di erent, and the intervals I (x; y); I (y; z ); I (z; x) pairwise intersect only in the common end vertices. Thus, by Lemma 3, C = I (x; y) I (y; z ) I (z; x) is a gated cycle with x; y 2 I (u; v); y; z 2 I (v; w); and z; x 2 I (w; u); as required.

In order to prove uniqueness of the median cycle, we rst show that

I (u; v) \ I (v; w) = I (v; y) and I (u; w) \ I (v; w) = I (w; z): As to the former, suppose that there exists a neighbour t of y in I (u; y) \ I (w; y): Then u and w belong to the convex subgraph W (t; y): Since x; z 2 I (u; w) W (t; y); it follows that

13

t 2 I (x; y) \ I (y; z) = fyg; yielding a contradiction. This settles the rst equality, and the second one is proved analogously. Finally, assume that C 0 is any median cycle for u; v; w: Let x0 ; y0 ; z 0 be the gates of u; v; w; respectively, in C 0: Then necessarily C 0 = I (x0 ; y0 ) I (y0 ; z 0 ) I (z 0 ; x0 )

contains x; y; z and thus includes C; that is, C 0 = C: 2 It would be interesting to characterize the bipartite graphs in which every vertex triplet admits a unique median vertex or cycle.

Conclusion

We have established a number of characterizations and features of cellular bipartite graphs, the most important of which are the decomposition along gated trees and the elimination scheme of pendant edges and pendant gated cycles. In view of this one may expect that the class of cellular bipartite graphs has many nice algorithmic properties. For a cellular bipartite graph G with metric d the isolation indices of the splits S (u; v) separating edges uv equal 1, so that the canonical decomposition of d into split metrics immediately yields an isometric embedding of G into a hypercube. If the requirement that G be bipartite is dropped, then total decomposability of d ensures that all positive isolation 1 indices equal 2 or 1, so that 2d would be a restriction of a hypercube metric, i.e., G would be "scale 2 embeddable" 13] into a hypercube.

u

J J J J J

u

J J J

u

J

u

S S S S S

J

u

J J J J

u

u

u

Figure 4. A non{bipartite graph with totally decomposable metric.

Each condition of Theorem 1 lends itself to a generalization of cellularity to the non{ bipartite case. The feasible amalgamations would then be those performed along special convex sets { but not necessarily gated sets if one wishes to capture graphs such as the one displayed in Figure 4. Another possible generalization of cellular bipartite graphs would incorporate the median graphs as well by departing from cycles and hypercubes and using gated amalgamations. 14

References

1] H.-J. Bandelt, Hereditary modular graphs, Combinatorica 8 (1988), 149{157. 2] H.-J. Bandelt, Graphs with intrinsic S3 convexities, J. Graph Theory 13 (1989), 215{218. 3] H.-J. Bandelt and J.P. Barthelemy, Medians in median graphs, Discr. Appl. Math. 8 (1984), 131{142. 4] H.-J. Bandelt and A.W.M. Dress, A canonical decomposition theory for metrics on a nite set, Advances Math. 92 (1992), 47{105. 5] H.-J. Bandelt and A.W.M. Dress, Split decomposition: a new and useful approach to phylogenetic analysis of distance data, Mol. Phylogen. Evol. 1 (1992), 242{252. 6] H.-J. Bandelt and H.M. Mulder, Pseudo{median graphs: decomposition via amalgamation and Cartesian multiplication, Discr. Math. 94 (1991), 161{180. 7] H.-J. Bandelt, H.M. Mulder, E. Wilkeit, Quasi{median graphs and algebras, J. Graph Theory 18 (1994), 681{703. 8] V. Chepoi, Geometric properties of d{convexity in bipartite graphs (in Russian), Modelirovanie informacionnych sistem, Chisinau, Stiinta (1986), 88{100. 9] M. Deza and M. Laurent, l1 {Rigid graphs, J. Alg. Combin. 3 (1994), 153{175. 10] M. Deza and M. Laurent, Applications of cut polyhedra, J. Comp. Appl. Math. (to appear). 11] D. Z. Djokovic, Distance{preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973), 263{267. 12] A.W.M. Dress and R. Scharlau, Gated sets in metric spaces, Aequationes Math. 34 (1987), 112{120 13] S. V. Shpectorov, On scale embeddings of graphs into hypercubes, Europ. J. Combin. 14 (1993), 117{130. 14] M.L.J. van de Vel, Theory of Convex Structures. North{Holland, Amsterdam, 1993.

15

更多相关文档:

avant-hier/ *avant-propos* / avant-premièr

12 Page 3 EN 459-3:2001+AC:2002 *Avant-propos* La présente Norme européenne a été élaborée par le Comité Technique CEN/TC 51 ?Ciments et chaux...

CLE International 1997-ISBN : 209033858-X *AVANT-PROPOS* ? Simple, claire et pratique, cette grammaire s’adresse à des étudiants en début d’...

41 INTRANORMES pour : ALSTOM TRANSPORT Page 3 EN 10088-1:2005 *Avant-propos* Le présent document (EN 10088-1:2005) a été élaboré par le Comité ...

S DE PROTECTION PROCUR?S PAR LES ENVELOPPES (Code IP) --`,,``,``,,`,,,`,,,``,``,`-`-`,,`,,`,`,,`--- *AVANT-PROPOS* 1) La CEI ...

-- Guo Ge Tech 新概念法语 第一讲 *Avant-propos* le

Qwilna新概念法语辅导 - 秋风清,秋月明,落叶聚还散,寒鸦栖复惊。 新概念法语 第一讲 *Avant-propos* le noveau concept fran?ais est une m...

Réf. n° EN 485-4:1993 F Page 2 EN 485-4:1993 Sommaire Page *Avant-propos* 3 4 4 4 4 5 5 5 5 5 5 1 2 3 3.1 3.2 3.3 4 4.1 4.2 ...

-*PROPOS* En tant que norme expérimentale, ce document applicable est soumis à observations pour une durée de 3 mois. Sans observation re?ue *avant* le ...

THOMSON SNECMA SOURIAU ET CIE THUILLIER MINEL LAWSON MARDON BOXAL SA FMM CIMT BAR LAFORGE PECHINEY RHENALU *Avant-propos* national Références aux normes ...

IEC. NOT FOR COMMERCIAL USE OR REPRODUCTION 2 *AVANT-PROPOS* CISPR 16-2-1 Amend. 1 ? CEI:2005 Cet amendement a été établi par le sous-...

INSTITUT DE SOUDURE FRAMATOME SA SPCA SA EDF PRODUCTION TRANSPORT CTE NORDTEST 3 NF EN 571-1:1997 *Avant-propos* national Références aux normes fran...

1998-07 3 NF F 19-483 Sommaire Page *Avant-propos* ... 4 1 2 3 4 5 5....

DGA/DCN COFREND EDF SQR INSTITUT DE SOUDURE EDF DTG FRAMATOME SA SOC MECANIQUE CREUSOT LOIRE AGFA GEVAERT *Avant-propos* national Références aux normes ...

4 4 5 6 7 7 7 7 7 7 8 Saga intranet pour : BUREAU VERITAS Page 3 EN 583-3:1997 *Avant-propos* La présente norme européenne a été élaborée...

RENAULT 2004 Page 2/6 RENAULT D14 1055 / - - D *AVANT-PROPOS* Ce document est équivalent aux documents des Groupes PSA PEUGEOT CITROEN et RENAULT V....

1 ? CEI:2005 *AVANT-PROPOS* Le présent ame

s *Avant-propos* Sommaire Propriétés du PC

生产设备的AMDEC方法 - CNOMO 生产设备的 AMDEC 方法 前言(*AVANT-PROPOS*) 前言 生产设备标准化委员会 E41.50.530.N 1994.06 页码:1/9...

更多相关标签:

文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com