The 27th Workshop on Combinatorial Mathematics and Computation Theory Displacements of Weighted Graphs ∗ Chiang Lin Department of Mathematics National Central University, Chung-Li, Taiwan, R.O.C. [email protected] Jen-Ling Shang Department of Banking and Finance Kainan University, Tao-Yuan, Taiwan, R.O.C. [email protected] Abstract x in G, the status sG (x) of x is defined by X dG (x, y). sG (x) = In this paper we investigate the relationship between the status and the displacement of a connected weighted graph. We also obtain a product result for the displacements. y∈V (G) The status s(G) of the graph G is defined by s(G) = min sG (x). x∈V (G) 1 The median of G is the set of vertices in G with status equal to s(G) (i.e, the set of vertices with minimum status). For the results about statuses one may refer to [1]. The following characterization of the median of a tree follows from the results of A. Kang and D. Ault [2], and was mentioned by O. Kariv and S.L. Hakimi in [4] for trees with weights on the vertices and edges. Introduction All the graphs considered in this paper are finite and simple. We introduce two parameters of graphs: displacement and status. We first give the definition of the displacement of a graph. Let G be a connected graph and let φ be a permutation of V (G) (i.e., φ is a bijection from V (G) to V (G)). The displacement DG (φ) of φ is defined by X DG (φ) = dG (x, φ(x)). Proposition 1.1 [3] Let T be a tree and v be a vertex in T . Then v is in the median of T if and only if |V (T 0 )| ≤ 21 |V (T )| for every component T 0 of T − v. 2 x∈V (G) The displacement D(G) of G is defined by In the following the notions of displacement and status are extended to the graphs with weights on the edges. If G is a graph and there exists a weight function w : E(G) → R+ , then (G, w) is called a weighted graph. Let (G, w) be a connected weighted graph. For a path P in (G, w) the weight wG (P ) of P is defined by X wG (P ) = w(e). D(G) = max DG (φ), where the maximum is taken over all permutations φ of V (G). E.T.H. Wang proposed a problem [5] which is equivalent to determining the displacements of all permutations of the path Pn (a path on n vertices). He and other solvers obtained that all the possible 2 values are 0, 2, 4, · · · , b n2 c. Next we give the definition of the status of a graph. Let G be a connected graph. For a vertex e∈E(P ) For two vertices x, y in (G, w), the weight distance dG,w (x, y) between x and y is defined by ∗ This research was supported by NSC of R.O.C. under grant NSC 98-2115-M-008-004 dG,w (x, y) = min wG (P ), 96 The 27th Workshop on Combinatorial Mathematics and Computation Theory where the minimum is taken over all paths P which join x and y. Note that if w(e) = 1 for every edge e in (G, w), then the weight distance is the distance in usual sense, i.e. dG,w (x, y) = dG (x, y). It is easy to see that for a connected weighted graph (G, w), we have dG,w (x, z) + dG,w (z, y) ≥ dG,w (x, y) where x, y, z ∈ V (G), and if v is a cut vertex of G and x, y are vertices in different components of G − v, then dG,w (x, v) + dG,w (v, y) = dG,w (x, y). Let (G, w) be a connected weighted graph and let φ be a permutation of V (G). The displacement DG,w (φ) of φ is defined by X DG,w (φ) = dG,w (x, φ(x)). X + (dG,w (y, x) − dG,w (y, v)) y∈V (G)−V (G0 ) ≥ X −dG,w (x, v) + y∈V (G0 ) X dG,w (v, x) y∈V (G)−V (G0 ) = (|V (G)| − 2|V (G0 )|) dG,w (v, x) ≥ 0. Thus sG,w (x) ≥ sG,w (v) for all vertices x 6= v. Hence v is in the median of (G, w). 2 In this paper, we investigate the relationship between the status and the displacement of a connected weighted graph and also the displacement about the product of two weighted graphs. x∈V (G) The displacement D(G, w) of (G, w) is defined by 2 D(G, w) = max DG,w (φ), where the maximum is taken over all permutations φ of V (G). For a vertex x in a connected weighted graph (G, w), the status sG,w (x) of x is X sG,w (x) = dG,w (y, x) . Relationship between Displacement and Status In this section, we investigate the relationship between the displacement and the status of a connected weighted graph. The displacement of a graph being the maximum of the displacements of all permutations of the vertices in the graph and the status being the minimum of the statuses of all vertices, the following is an min-max inequality for these two variants. y∈V (G) The status s(G, w) of the graph (G, w) is s(G, w) = minx∈V (G) sG,w (x). Theorem 2.1 Suppose that (G, w) is a connected weighted graph. Then The median of (G, w) is the set of vertices in (G, w) with status equal to s(G, w). If w(e) = 1 for every edge e in (G, w), then sG,w (x) = sG (x) for all x ∈ V (G), s(G, w) = s(G), and the median of (G, w) is the same as the median of G. D(G, w) ≤ 2s(G, w). Proof. Let φ be an arbitrary permutation of V (G), and y be an arbitrary vertex of G. Then X DG,w (φ) = dG,w (x, φ(x)) Theorem 1.2 Suppose that (G, w) is a connected weighted graph which has a cut vertex v such that |V (G0 )| ≤ 21 |V (G)| for every component G0 of G − v. Then v is in the median of (G, w). x∈V (G) ≤ X (dG,w (x, y) + dG,w (φ(x), y)) x∈V (G) Proof. Suppose that x is an arbitrary vertex of G other than v, and x ∈ V (G0 ) for some component G0 of G − v. Then = = X X = y∈V (G) 2sG,w (y). Since φ is an arbitrary permutation, and y is an arbitrary vertex, we have (dG,w (y, x) − dG,w (y, v)) X dG,w (φ(x), y) x∈V (G) y∈V (G) = dG,w (x, y) + x∈V (G) sG,w (x) − sG,w (v) X X = dG,w (y, x) − dG,w (y, v) y∈V (G) X max DG,w (φ) ≤ min 2sG,w (y). (dG,w (y, x) − dG,w (y, v)) Thus D(G, w) ≤ 2s(G, w). y∈V (G0 ) 97 2 The 27th Workshop on Combinatorial Mathematics and Computation Theory Let (G, w) be a weighted graph. A permutation π of V (G) is optimal for the displacement of (G, w) if DG,w (π) = D(G, w). In Theorem 2.3 the minmax inequality about displacement and status will be shown to be an equality for some class of connected graphs, and the optimal permutations for the displacement are also characterized for these graphs. Let us begin with the following observation. dG,w (x, v) + dG,w (v, π(x)). Hence X DG,w (π) = dG,w (x, π(x)) x∈V (G) = 2 X dG,w (x, v) x∈V (G) = 2sG,w (v) ≥ 2s(G, w). On the other hand, by Theorem 2.1, 2s(G, w) ≥ D(G, w) ≥ DG,w (π). Proof. Let X = {x1 , x2 , · · · , x|X| } such that Xm (dG,w (x, v) + dG,w (π(x), v)) x∈V (G) Lemma 2.2 Let X1 , X2 , · · · , Xm be disjoint nonempty subsets of a set X. If |Xi | ≤ 12 |X| for i = 1, 2, · · · , m. Then there exists a permutation φ of X such that φ(Xi ) ∩ Xi = ∅ for i = 1, 2, · · · , m. X1 X2 X = Thus DG,w (π) = D(G, w) = 2s(G, w). Hence we have proved (1) and the sufficiency of (2). Now we prove the necessity of (2). Suppose, on the contrary, there exists a vertex z with dG,w (z, π(z)) < dG,w (z, v) + dG,w (v, π(z)). Then X DG,w (π) = dG,w (x, π(x)) = {x1 , x2 , · · · , x|X1 | }, = {x|X1 |+1 , x|X1 |+2 , · · · , x|X1 |+|X2 | }, .. . = {x|X1 |+|X2 |+···+|Xm−1 |+1 , x|X1 |+|X2 |+···+|Xm−1 |+2 , · · · , x|X1 |+|X2 |+···+|Xm | }. x∈V (G) < X (dG,w (x, v) + dG,w (π(x), v)) x∈V (G) Let A be an integer such that |Xi | ≤ A ≤ 12 |X| for i = 1, 2, · · · , m. Define φ : X → X by π(xi ) = xi+A (the subscripts being taken modulo |X|) for i = 1, 2, · · · , |X|. It is easy to see that φ satisfies the required property. 2 = = 2sG,w (v) 2s(G, w). The last equality follows from Theorem 1.2. By (1) of this theorem, we have DG,w (π) < D(G, w), a contradiction. This complete the proof. 2 Theorem 2.3 Suppose that (G, w) is a connected weighted graph which has a cut vertex v such that |V (G0 )| ≤ 12 |V (G)| for every component G0 of G − v. Then we have (1) D(G, w) = 2s(G, w), (2) a permutation π of V (G) is optimal for the displacement of (G, w) if and only if dG,w (x, π(x)) = dG,w (x, v) + dG,w (v, π(x)) whenever the vertices x and π(x) are in the same component of G − v. Corollary 2.4 If (T, w) is a weighted tree, then (1) D(T, w) = 2s(T, w), (2) a permutation π of V (T ) is optimal for the displacement of (T, w) if and only if π(V (T 0 )) ∩ V (T 0 ) = ∅ for every component T 0 of T − v where v is in the median of T . Proof. This follows from Proposition 1.1, Lemma 2.2 and Theorem 2.3. 2 An easy consequence follows from Corollary 2.4 (1). Proof. We first show (1) and the sufficiency of (2). Since |V (G0 )| ≤ 12 |V (G)| for every component G0 of G − v, by Lemma 2.2 there exists a permutation φ of V (G) such that φ(V (G0 ))∩V (G0 ) = ∅ for every component G0 of G−v. Let π be any permutation of V (G) with this property dG,w (x, π(x)) = dG,w (x, v) + dG,w (v, π(x)) whenever the vertices x and π(x) are in the same component of G − v. (The permutation φ satisfies this property trivially.) Then for every x ∈ V (G), dG,w (x, π(x)) = Corollary 2.5 If (T, w) is a tree with integral weights (i.e., w(e) is an integer for each e ∈ E(T )), then D(T, w) is an even integer. 2 Corollary 2.5 can also follow from the following result. Theorem 2.6 Let (T, w) be a weighted tree with integral weights. Suppose that π is a permutation of V (T ). Then DT,w (π) is an even integer. 98 The 27th Workshop on Combinatorial Mathematics and Computation Theory Proof. For y, z ∈ V (T ), we use [y, z] to denote the set of edges in the path which joins y and z. We have X DT,w (π) = dT,w (x, π(x)) x∈V (T ) = X X w(e) = X w(e) e∈E(T ) x:e∈[x,π(x)] = X a12 a22 .. . ··· ··· .. . a1i a2i .. . ··· ··· .. . a1n a2n .. . am1 am2 ··· ami ··· amn such that each element of X appears n times in A. Then for each i (i = 1, 2, · · · , m), there exists a permutation ai1 ai2 · · · ain of ai1 ai2 · · · ain such that for each j (j = 1, 2, · · · , n), a1j , a2j , · · · , am j are distinct elements (i.e., {a1j , a2j , · · · , am j } = {x1 , x2 , · · · , xm }). x∈V (T ) e∈[x,π(x)] X a11 a21 .. . w(e)|{x : e ∈ [x, π(x)]}|. e∈E(T ) Proof. First we choose a11 , a21 , · · · , am 1 as follows: For i = 1, 2, · · · , m, let Bi = {aij : 1 ≤ j ≤ n}. Let 1 ≤ i1 < i2 < · · · < ik ≤ m. Since each element in X appears n times in A, it appears at most n times in the cells of i1 -th, i2 -th, · · ·, ik -th rows of A. The i1 -th, i2 -th, · · ·, ik -th rows has kn cells. Thus |Bi1 ∪ Bi2 ∪ · · · ∪ Bik | ≥ k. By Hall’s Theorem, there exist Let e be an arbitrary edge in T , we show that |{x : e ∈ [x, π(x)]}| is an even integer. Let B1 and B2 be the components of T − e. Then {x : e ∈ [x, π(x)]} = S {x : x ∈ V (B1 ), π(x) ∈ V (B2 )} {x : x ∈ V (B2 ), π(x) ∈ V (B1 )}. Since |{x : x ∈ V (B1 ), π(x) ∈ V (B2 )}| = |{x : x ∈ V (B2 ), π(x) ∈ V (B1 )}|, we have that |{x : e ∈ [x, π(x)]}| is even. Thus DT,w (π) is even. 2 a1j1 ∈ B1 , a2j2 ∈ B2 , · · · , amjm ∈ Bm such that a1j1 , a2j2 , · · · , amjm are distinct. Let 3 a11 = a1j1 , a21 = a2j2 , · · · , am 1 = amjm . Product Result for Displacement Next we choose a12 , a22 , · · · , am 2 as follows : For i = 1, 2, · · · , m, let Bi 0 = {aij : 1 ≤ j ≤ n, j 6= ji }. For 1 ≤ i1 < i2 < · · · < ik ≤ m, by the same arguments as above, we have |Bi01 ∪ Bi02 ∪ · · · ∪ Bi0k | ≥ k. Again, by Hall’s Theorem, there exist Let G and H be graphs. The Cartesian product graph G × H of G and H is the graph with vertex set V (G × H) = V (G) × V (H) and edge set E(G × H) = {((x, y), (x0 , y 0 )) : x = x0 ∈ V (G), yy 0 = (y, y 0 ) ∈ E(H) or xx0 = (x, x0 ) ∈ E(G), y = y 0 ∈ V (H)}. Let (G, w) and (H, u) be weighted graphs. Then the Cartesian product graph of (G, w) and (H, u) is the weighted graph (G × H, w × u) where the weight function w × u is defined as follows: if ((x, y), (x0 , y 0 )) ∈ E(G × H) then w × u((x, y), (x0 , y 0 )) = 0 u(yy ) if w(xx0 ) if 0 0 ∈ B a1j10 ∈ B10 , a2j20 ∈ B20 , · · · , amjm m 0 such that a1j10 , a2j20 , · · · , amjm are distinct. Let 0 . a12 = a1j10 , a22 = a2j20 , · · · , am 2 = amjm Repeating the above procedure, we eventually have aij 1 ≤ i ≤ m, 1 ≤ j ≤ n such that a1j , a2j , · · · , am j are distinct for every j (j = 1, 2, · · · , n). We can also see that ai1 ai2 · · · ain is a permutation of ai1 ai2 · · · ain for each i(i = 1, 2, · · · , m). 2 0 x=x, y = y0 . It is easy to see that if (x, y) and (x0 , y 0 ) are vertices in (G × H, w × u), then dG×H,w×u ((x, y), (x0 , y 0 )) = dG,w (x, x0 ) + dH,u (y, y 0 ). Now we will establish a product result about displacements of weighted graphs. We begin with a lemma. Now we prove the product result for displacements. Theorem 3.2 Suppose that (G, w), (H, u) are connected weighted graphs, and the orders of G and H are m and n respectively. Then Lemma 3.1 Let X be the set {x1 , x2 , · · · , xm }, and A be an m by n matrix D(G × H, w × u) = nD(G, w) + mD(H, u). 99 The 27th Workshop on Combinatorial Mathematics and Computation Theory Proof. First we prove that D(G × H, w × u) ≥ nD(G, w) + mD(H, u). Let π1 be a permutation of V (G) such that DG,w (π1 ) = D(G, w). Let π2 be a permutation of V (H) such that DH,u (π2 ) = D(H, u). Define π : V (G × H) → V (G × H) by π(x, y) = (π1 (x), π2 (y)). Then Here we show that D1 ≤ n D(G, w). Let V (G) = {x1 , x2 , · · · , xm }, V (H) = {y1 , y2 , · · · , yn }. Since π is a permutation of V (G × H), we have {π(xi , yj ) : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = {(xi , yj ) : 1 ≤ i ≤ m, 1 ≤ j ≤ n}. Thus each xi (1 ≤ i ≤ m) appears n times in the array (p1 (π(xi , yj )))1≤i≤m,1≤j≤n . (x,y)∈V (G×H) X dG×H,w×u ((x, y), (π1 (x), π2 (y))) (x,y)∈V (G×H) X = (dG,w (x, π1 (x)) + dH,u (y, π2 (y))) (x,y)∈V (G×H) X = dG,w (x, π1 (x)) Let aij = p1 (π(xi , yj )), 1 ≤ i ≤ m, 1 ≤ j ≤ n. By Lemma 3.1, for each i (i = 1, 2, · · · , m), there exists a permutation ai1 ai2 · · · ain of ai1 ai2 · · · ain such that for each j (j = 1, 2, · · · , n), {a1j , a2j , · · · am j } = {x1 , x2 , · · · xm }. Thus X X D1 = dG,w (xi , p1 (π(xi , yj ))) 1≤i≤m 1≤j≤n (x,y)∈V (G×H) X + dH,u (y, p2 (π(x, y))). (x,y)∈V (G×H) DG×H,w×u (π) X = dG×H,w×u ((x, y), π(x, y)) = X D2 = = dH,u (y, π2 (y)) X X dG,w (xi , aij ) 1≤i≤m 1≤j≤n (x,y)∈V (G×H) = = nDG,w (π1 ) + mDH,u (π2 ) = nD(G, w) + mD(H, u). X X dG,w (xi , aij ) 1≤i≤m 1≤j≤n = Since D(G × H, w × u) ≥ DG×H,w×u (π), we have D(G × H, w × u) ≥ n D(G, w) + m D(H, u). Next we prove the reverse inequality D(G × H, w × u) ≤ n D(G, w) + m D(H, u). Let π be an arbitrary permutation of V (G × H). We will show that DG×H,w×u (π) ≤ n D(G, w) + m D(H, u). Let p1 be the function from V (G × H) to V (G) such that p1 (x, y) = x for (x, y) ∈ V (G × H), and p2 be the function from V (G × H) to V (H) such that p2 (x, y) = y for (x, y) ∈ V (G × H). Note X X dG,w (xi , aij ) 1≤j≤n 1≤i≤m ≤ X D(G, w) 1≤j≤n = n D(G, w). Similarly, we can show that D2 ≤ m D(H, u). Thus DG×H,w×u (π) dG×H,w×u ((x, y), π(x, y)) = dG×H,w×u ((x, y), (p1 (π(x, y)), p2 (π(x, y)))) = dG,w (x, p1 (π(x, y))) + dH,u (y, p2 (π(x, y))). = D1 + D2 ≤ n D(G, w) + m D(H, u). Since π is an arbitrary permutation of V (G × H), we obtain D(G × H, w × u) ≤ n D(G, w) + m D(H, u). This completes the proof. 2 Thus DG×H,w×u (π) X = dG×H,w×u ((x, y), π(x, y)) References [1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Publishing company (1990). (x,y)∈V (G×H) X = dG,w (x, p1 (π(x, y))) [2] A. Kang and D. Ault, Some properties of a centroid of a free tree, Inform. Process. Lett. 4, No. 1 (1975) 18-20. (x,y)∈V (G×H) + X dH,u (y, p2 (π(x, y))). (x,y)∈V (G×H) [3] C. Lin, Y.-J. Zhang and J.-L. Shang, Statuses of Graphs, Proceedings of the 26th Workshop on Combinatorial Mathematics and Computation Theory (2009) 282-287. Let D1 = X dG,w (x, p1 (π(x, y))), (x,y)∈V (G×H) 100 The 27th Workshop on Combinatorial Mathematics and Computation Theory [4] O. Kariv and S.L. Hakimi, An algorithmic approach to network location problems. II: The p-medians, Siam J. Appl. Math. 37 (1979) 539560. [5] E.T.H. Wang, The symmetric group as a metric space, E2424, Amer. Math. Monthly (1974) 668-670. 101

© Copyright 2018