Báo cáo toán học: A Formula About Tree

d (q) là mức độ của các đỉnh q, và l (v, q) là khoảng cách giữa v và q trong G. Kết quả này cho phép chúng tôi lấy được một công thức concering khoảng cách trung bình cho một số cây đặc biệt.
Nội dung trích xuất từ tài liệu:
Báo cáo toán học: "A Formula About Tree" 9LHWQDP -RXUQDOVietnam Journal of Mathematics 33:3 (2005) 343–348 RI 0$7+(0$7,&6 ‹ 9$67 A Formula About Tree Ahmed Ayache1 , Walied H. Sharif2 , and Vu Dinh Hoa3 1 University of Bahraib, Faculty of Science, Department of Mathematics, P. O. Box 32038, Isa Town, Kingdom of Bahrain 2 Department of Mathematics, College of Science, Qatar University, Doha, P. O. Box 2713, Qatar 3 Hanoi University of Education, Faculty of Information Technology, 136 Xuan Thuy street, Hanoi, Vietnam Received September 23, 2004 Revised April 12, 2005Abstract. Let G be a tree. It is proved that for any vertex v of G |V | + [d(q ) − 2]l(v, q ) = 1 q ∈Vin which d(q ) is the degree of the vertex q , and l (v, q ) is the distance between v andq in G. This result enable us to derive a formula concering the average distance forsome particular trees.1. IntroductionWe begin by recalling some definitions and notations. A tree G is a connectedgraph that contains no simple cycles [1]. The degree of a vertex v of G, denotedby d(v ), is the number of edges incident with v . The distance between twovertices v anh q , denoted l(v, q ), is the number of edges from v to q on theunique (v, q )-path in the tree G. The transmission of a vertex v of G, is the value σ (v ) = u∈V l(v, u). Thetransmission of G is the value σ (G) = v∈V σ (v ) [3]. The Wiener index of a connected graph G, denoted by W (G), is defined byW (G) = u,v∈V l(v, u), in which the summation is taken over all unorderedpairs {u, v } of distinct vertices of G. It is evident that W (G) = 1 σ (G). Finally, 2344 Ahmed Ayache, Walied H. Sharif, and Vu Dinh Hoathe average distance of G, denoted by μ(G) = W (G)/ p , where p is order of G 2[2]. The purpose of this paper is to establish the following formula |V | + [d(q ) − 2]l(v, q ) = 1 q ∈Vfor any v ∈ V . Consequently, this enables us to evaluate the average distance ofsome particular trees.2. The FormulaTheorem 2.1. Let G be a tree with finite vertex set V . For every vertex v ofG, we have |V | + (d(q ) − 2).l(v, q ) = 1. q ∈VProof. We use induction on D(v ) = maxq∈V l(v, q ). If D(v ) = 1 then G is a starand we have |V | + (d(q ) − 2)l(v, q ) = |V | + (1 − 2)l(v, q ) = 1. q ∈V q ∈VNow suppose that |V | + q∈V (d(q ) − 2)l(v, q ) = 1 for all trees G and for vertexv ∈ V (G) such that D(v ) = k ≥ 1. We consider a tree G with a vertex v ∈ V (G)such that D(v ) = k + 1. Let X be the set of the vertices q with l(v, q ) = k + 1and Y be the set of neighbors of X . It is easy to see that l(v, q ) = k for q ∈ Yand that q∈Y dx = |X |, where dx (q ) is the number of the neighbors of q in X .For the tree G = G − X we have by induction hypothesis 1 = |V − X | + (dG (q ) − 2)l(q, v ) q ∈ V −X = |V | − |X | + (dG (q ) − 2)l(q, v ) + (dG (q ) − 2)l(q, v ) q ∈ V −X −Y q ∈Y = |V |+ dX (q )l(q, v )–|X | (dG (q )–2)l(q, v )+ (dG (q )–2)l(q, v )– q ∈ V −X −Y q ∈Y q ∈Y = |V | + (dG (q ) − 2)l(q, v ) − |X |l(q, v ) − |X | q ∈ V −X = |V | + (dG (q ) − 2)l(q, v ), q ∈Vsince dG (q ) = 1 for all q ∈ X . Thus, Theorem 2.1 holds for any finite tree G.3. The Average DistanceThe previous formula may be used to find the average distance in some specialtrees. Let us start by some preliminary results.A Formula About Tree 345Proposition 3.1. If G is a tree with order p > 1, then 1 1 ...