| 摘要: | 研究期間：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 [6] 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 [5] 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 [5]. 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 [7] which is equivalent to determining the variance spectrum of Pn. He and other solvers [7] 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. |
