 English  |  正體中文  |  简体中文  |  Items with full text/Total items : 69561/69561 (100%) Visitors : 23099281      Online Users : 839
 Scope All of NCUIR 理學院    數學系       --研究計畫 Tips: please add "double quotation mark" for query phrases to get precise resultsplease goto advance search for comprehansive author search Adv. Search
 Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer NCU Institutional Repository > 理學院 > 數學系 > 研究計畫 >  Item 987654321/63170

 Please use this identifier to cite or link to this item: `http://ir.lib.ncu.edu.tw/handle/987654321/63170`

 Title: 圖的距離和與變量之研究;The Study of Statuses and Variances in Graphs Authors: 林強;商珍綾 Contributors: 國立中央大學數學系 Keywords: 數學 Date: 2012-12-01 Issue Date: 2014-03-17 14:20:46 (UTC+8) Publisher: 行政院國家科學委員會 Abstract: 研究期間：10108~10207;The purpose of this project is to investigate the following topics: (1) Status unique graphs. (2) Minimum statuses, maximum variances and variance spectrums of graphs. FIRST YEAR PROPOSAL. Status unique graphs. Let G be a connected graph. The status of a vertex x in G, is denoted and defined by The status sequence of a graph is the list of the statuses of all vertices arranged in nondecreasing order. Non-isomorphic graphs may have the same status sequence. Slater  provides infinite pairs of non-isomorphic trees with the same status sequence. Example of non-isomorphic nontree graphs with the same status sequence can be found in [1,3]. Motivated by these facts, we consider the problem: "Which graph is uniquely determined by its status sequence?" Let us give the following definition. Let F be a family of some connected graphs and G be a graph in F. We say that G is a status unique graph in F (or simply G is status unique in F ) if G is uniquely determined in F by its status sequence (i.e, whenever H is a graph in F and H, G have the same status sequence, we have H isomorphic to G). For example any path is status unique in the family of all connected graphs since a path of order n is the only connected graph of order n which contains a vertex with status A spider is a tree which contains exactly one vertex with degree at least three. In  we prove that every spider is status unique in the family of all trees. A connected graph is status injective [1,2,4] if the statuses of its vertices are all different. Our goal is to deal with the following conjectures which are proposed in . Conjecture 1. Any status injective tree is status unique in all connected graphs. Conjecture 2. A tree and a nontree graph can not have the same status sequence. References. 1. F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley Publishing company (1990) 181-185. 2. F. Buckley, F. Harary, Unsolved problems on distance in graphs, Elctron. Notes Discrete Math. 11 (2002) 89-97. 3. R.C. Entringer, D.E. Jackson, D.A. Snyder, Distance in graphs, Czech. Math. J. 26 (101) (1976) 283-296. 4. L. Pachter, Constructing status injective graphs, Discrete Applied Math. 80 (1997) 107-113. 5. J-L Shang , C. Lin, 2011, Spiders are status unique in all trees, Discrete Math. 311 (2011), 785-791 6. P.J. Slater, Counterexamples to Randic conjecture on distance degree sequences for trees, J. Graph Theory 6 (1982) 89-92. SECOND YEAR PROPOSAL Minimum statuses, maximum variances and variance spectrums of graphs. Let G be a connected graph. Recall that the status of a vertex x in G, is denoted and defined by s (^) = X d (x, y ). y e V ( G ) The minimum status of G is denoted and defined by ms(G)= min{ s(x)| xe V(G)}. Let G be a connected graph. For a permutation n of V(G) (i.e., nis a bijection from V(G) to V(G)), the variance of n is denoted and defined by The maximum variance of G is denoted and defined by Mv(G) = max{v(n) |n is a permutation of V(G)}. The variance spectrum of G is denoted and defined by v-Spec (G)= {v(n) In is a permutation of V(G)}. Let Pn denote a path on n vertices. E.T.H. Wang proposed a problem in Mathematical Monthly  which is equivalent to determining the variance spectrum of Pn. He and other solvers  obtained that v-Spec(Pn)= {0,2,4........ For a connected graph G,it is easy to prove that Mv(G) ^ 2ms(G). We list the following problems for our study. 1. Prove or disprove: For any connected graph G, ms(G) ^ Mv(G). 2. Determine the variance spectrum of some specific graphs. 3. We can define status spectrum the way we define variance spectrum. We try to determine the status spectrum of some specific family of graphs. Reference. 7. E.T.H. Wang, The symmetric group as a metric space, E2424, Amer. Math. Monthly 81 (1974) 668-670. Relation: 財團法人國家實驗研究院科技政策研究與資訊中心 Appears in Collections: [數學系] 研究計畫

Files in This Item:

File Description SizeFormat
index.html0KbHTML191View/Open