樹形圖具有對稱相似性

Abstract

論文提要:\r\n圖論上，談到兩點相似(similar)，是這樣定義的:若a，b是圖G上的兩點，且存在一箇定義於V (G)的某排列ϕ，滿足:(1)ϕ∈Aut (0) 及(2) ϕ(a) =b. 則稱G 之a. b兩點相似。由定義吾人固然知必有一ϕ∈Aut(O). 滿足ϕ(a) =b. 如果G之a. b兩點相似的話。然而，有人不禁會問:若G上任二點a. b相似，則是否存在一ϕ∈Aut (G) .同時滿足ϕ (a)=b 且ϕ (b) =a 呢7?(本文稱G為對稱相似(symmetrically similar). 若答案為真時。)\r\n作者在研究GRAPH RECONSTRUCTION CONJECTURE時，亦產生相同的疑問。本文乃作者試就此一問題，將樹型圖(Tree)加以研究，發現：凡是具有有限點的樹形圖(finite tree) 皆具備此特性。\r\n首先，吾人知: 任意樹形圖乃一不具環路的聯結圖( acyclic cconnected graph ).且任二不同點，a. b僅可決定出唯一的(a-b)路逕(path)。\r\n本文先針對此路徑觀察出二項特性(1)當(a-b)為偶路徑，c為其中點，且ϕ (a) = b.ϕ∈Aut (G) 時，ϕ作用在c之後不變。(2)當(a-b)為奇路徑，y. z為其二中點，且ϕ (a) = b，ϕ∈Aut(G)時，ϕ作用在y. z 之後對調(即ϕ (y)=z 且φ(z)=y) 。其證明包含在定理2. 1. 7 及定理2. 1. 10 立中。\r\n其次，以定理2. 1. 7 及定理2. 1. 10 為基礎，本文將證明出確實存在一ϕ∈Aut (G) .同時滿足ϕ (a) = b 且ϕ (b) = a. 此處G為一樹形圖。\r\n由於找不到反例，本文將給一箇Conjecture 作為總結，即任一有限simple圖皆具對稱相似性。

[Introduction]\r\n [Introduction]\r\nIt`s well known in graph theory that if u and v are two vertices of a graph G and for some automophism ϕ of G. ϕ (u)=v then u and v are said to be similar. A graph G is said to be vertex-symmetric (edge-symmetric) if every pair of its vertices (edges) are similar.(see [5]. pp. 171-175)\r\nSeveral properties concerning these similarities have been dealt with in some papers. For example,\r\n(1) If u and v are similar, then G-u≅G-v. (see [6])\r\n(2) Not every regular edge-symmetric graph is vertex-symmetric. (see [4])\r\nEspecially, (1) is frequently occurred in the articles about the famous problem--graph reconstruction conjecture. e.g. [2]. [7] and [8]. And probably, the research of these similarities of graphs is a key to solve this reconstruction conjecture.\r\nIn this paper, we will investigate a special kind of similarity of trees. That is, we`ll assert that if u and v are two similar vertices of a finite tree T. then there is an automorphism ¢ of T satisfying: ¢(u) = v and ¢(v) = u. ( In such case. we say that T is symmetrically similar (Definition 2.1.2) or T preserves symmetric similarity . )\r\nIn Part I. we only give the fundamental definitions and concepts about graph theory as the preliminaries for our main subject. And in general, we follow the terminology and notations of [1]. [3] and [5].\r\nIn Part II, we`ll present some lemmas. e.g. Lemma 2.1.4. Lemma 2.1.5. Lemma 2.1.6. Lemma 2.1.8. Lemma 2.1.9 and Lemma 2.2.1 and we will prove:\r\nTheorem 2.1.7 Let T be a tree. aT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d<0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1),, i=0, 1,…, d.\r\nTheorem 2.1.10 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d>0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1), i=0, 1,…, d.\r\nTheorem 2.2.2 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad=b is an even path of T where d>1, then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a and (2) ψ(x)=x, ∀x∈{w∈V(T)│Tc<w>≠Tc<a>}, Tc<w>≠Tc<b>.\r\nTheorem 2.2.3 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_ad, X_(ad+1)=b be an odd path of T where d>0. then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a\r\nSince the length of any (a-b) path of the tree T is either even or odd, imploying Theorem 2.2.2-(1) 2.2.3. we immediately have:\r\nTheorem 2.2.4 Every Tree is symmetrically similar\r\nAt last, we give a conjecture as a conclusion for this paper, i.e. Conjecture: Every simple graph is symmetrically similar.