English  |  正體中文  |  简体中文  |  Items with full text/Total items : 65317/65317 (100%)
Visitors : 21375274      Online Users : 214
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    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 [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.
    Relation: 財團法人國家實驗研究院科技政策研究與資訊中心
    Appears in Collections:[數學系] 研究計畫

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML166View/Open


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明