學術產出-Theses
Article View/Open
Publication Export
-
題名 線星數極值問題
Extremal Problems for Linear Star Number作者 劉宣谷 貢獻者 張宜武
Chang, Yi-Wu
劉宣谷關鍵詞 星形表示法
線星表示法
毛毛蟲
Star representation
Linear star representation
Caterpillar日期 2001 上傳時間 15-Apr-2016 16:02:46 (UTC+8) 摘要 In this thesis, we study relationships between linear star number and star number and obtain bounds on the linear star number. We obtain an upper bound on linear star number in term of star number：s*(G) ≦ 3s(G). When we forbid certain induced subgraphs, we obtain an upper bound on linear star number. If G is a graph without induced K4－e., we prove that s*(G) ≦ s(G)+1. And, the linear star number of the triangle-free graph is also bounded by s(G)+1. The linear star number and star number are equal when G is a graph with △(G)=3. When G is a graph with △(G)=4, we also obtain s*(G)≦s(G)+1. 參考文獻 BOOK{texbook, author = {Douglas B. West}, year = 1996, title = {Introduction to Graph Theory}, publisher = {PRENTICE HALL} } ARTICLE{Gav, author={F. Gavril}, title={The intersection graphs of subtrees in trees are exactly the chordal graphs}, journal={J. Combinatorics Theory B}, volume={16}, year={1974}, pages={45-56},} ARTICLE{Bun, author={P.A. Buneman}, title={A characterization of rigid circuit graphs}, journal={Discrete Math}, volume={9}, year={1974}, pages={205-212}, } ARTICLE{Wal, author={J.R. Walter}, title={Representations of chordal graphs as subtrees of a tree}, journal={J. Graph Theory}, volume={2}, year={1978}, pages={265-267},} ARTICLE{Wes, author={D.B. West}, title={Parameters in partial orders and graphs:Packing, covering, and representation}, journal={Graphs and Order}, volume={2}, year={1985}, pages={267-350},} PHDTHESIS{Chang, author={Yi-Wu Chang}, title={Graph Representations Using Star, Tree, Intervals And Boxes}, school={M.S., University of Illinois}, year={1994},} 描述 碩士
國立政治大學
應用數學系資料來源 http://thesis.lib.nccu.edu.tw/record/#A2002001137 資料類型 thesis dc.contributor.advisor 張宜武 zh_TW dc.contributor.advisor Chang, Yi-Wu en_US dc.contributor.author (Authors) 劉宣谷 zh_TW dc.creator (作者) 劉宣谷 zh_TW dc.date (日期) 2001 en_US dc.date.accessioned 15-Apr-2016 16:02:46 (UTC+8) - dc.date.available 15-Apr-2016 16:02:46 (UTC+8) - dc.date.issued (上傳時間) 15-Apr-2016 16:02:46 (UTC+8) - dc.identifier (Other Identifiers) A2002001137 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/84946 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description.abstract (摘要) In this thesis, we study relationships between linear star number and star number and obtain bounds on the linear star number. We obtain an upper bound on linear star number in term of star number：s*(G) ≦ 3s(G). When we forbid certain induced subgraphs, we obtain an upper bound on linear star number. If G is a graph without induced K4－e., we prove that s*(G) ≦ s(G)+1. And, the linear star number of the triangle-free graph is also bounded by s(G)+1. The linear star number and star number are equal when G is a graph with △(G)=3. When G is a graph with △(G)=4, we also obtain s*(G)≦s(G)+1. en_US dc.description.tableofcontents 封面頁 證明書 致謝詞 論文摘要 目錄 Chapter1 Introduction Chapter2 A General Upper Bound of Linear star Number Chapter3 Bounds of Linear Star Number in Restricted classes Bibliography zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2002001137 en_US dc.subject (關鍵詞) 星形表示法 zh_TW dc.subject (關鍵詞) 線星表示法 zh_TW dc.subject (關鍵詞) 毛毛蟲 zh_TW dc.subject (關鍵詞) Star representation en_US dc.subject (關鍵詞) Linear star representation en_US dc.subject (關鍵詞) Caterpillar en_US dc.title (題名) 線星數極值問題 zh_TW dc.title (題名) Extremal Problems for Linear Star Number en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) BOOK{texbook, author = {Douglas B. West}, year = 1996, title = {Introduction to Graph Theory}, publisher = {PRENTICE HALL} } ARTICLE{Gav, author={F. Gavril}, title={The intersection graphs of subtrees in trees are exactly the chordal graphs}, journal={J. Combinatorics Theory B}, volume={16}, year={1974}, pages={45-56},} ARTICLE{Bun, author={P.A. Buneman}, title={A characterization of rigid circuit graphs}, journal={Discrete Math}, volume={9}, year={1974}, pages={205-212}, } ARTICLE{Wal, author={J.R. Walter}, title={Representations of chordal graphs as subtrees of a tree}, journal={J. Graph Theory}, volume={2}, year={1978}, pages={265-267},} ARTICLE{Wes, author={D.B. West}, title={Parameters in partial orders and graphs:Packing, covering, and representation}, journal={Graphs and Order}, volume={2}, year={1985}, pages={267-350},} PHDTHESIS{Chang, author={Yi-Wu Chang}, title={Graph Representations Using Star, Tree, Intervals And Boxes}, school={M.S., University of Illinois}, year={1994},} zh_TW
