簡易檢索 / 詳目顯示
| 研究生： |
賴昱儒 |
|---|---|
| 論文名稱： |
最大，二分，外平面圖之容忍表示法 The Tolerance Representations of Maximal Bipartite Outerplanar Graphs |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2010 |
| 畢業學年度： | 98 |
| 語文別： | 英文 |
| 論文頁數： | 35 |
| 中文關鍵詞： | 最大外平面圖 、二分圖 、容忍表示法 |
| 外文關鍵詞： | Tolerance Graphs, Maximal Outerplanar Graphs, Bipartite |
| 相關次數： | 點閱：133 下載：22 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在這篇論文中，我們針對2-連通的最大外平面圖而且是二分圖的圖形，討論
其容忍表示法，並找到它的所有禁止子圖H1、H2、H3、H4。
In this thesis, we prove a 2-connected graph G which is maximal outerplanar and bipartite is a tolerance graph if and only if there is no induced subgraphs H1; H2; H3 and H4 of G.
Abstract ii
中文摘要iii
1 Introduction 1
1.1 History of Tolerance Graphs 1
1.2 The Structure of Tolerance Graphs 3
2 Tolerance Graphs 4
2.1 Definition and Theorem of Tolerance Graph 4
2.2 Bounded Tolerance Representations for Trees
and Bipartite Graphs 6
2.3 A Tolerance Representation of C4 7
2.4 A Tolerance Representation of Concatenation
of Two 4-cycles 10
2.5 A Tolerance Representation of Concatenation
of Three 4-cycles 12
3 Some Results on Maximal Outerplanar Graphs 20
3.1 A 2-connected Graph Which Is Maximal
Outerplanar Graph and Bipartite Is Not
Necessarily a Tolerance Graph 20
4 Open Problems and Further Directions of Studies 30
References 31
[1] M. Golumbic and C. Monma, A generalization of interval graphs with tolerances, Congressus Numerantium, 35 (1982), pp. 321-331.
[2] M. Golumbic, D. Rotem, and J. Urrutia, Comparability graphs and intersection graphs, Discrete Math., 43 (1983), pp. 37-46.
[3] M. Golumbic and A. Trenk, Tolerance graphs, Cambridge Univ Pr, 2004.
[4] R. Hayward and R. Shamir, A note on tolerance graph recognition, Discrete Applied Mathematics, 143 (2004), pp. 307-311.
