簡易檢索 / 詳目顯示
| 研究生： |
郭瓊雲 |
|---|---|
| 論文名稱： |
最大外平面圖的有界容忍表示法 Bounded Tolerance Representation for Maximal Outerplanar Graphs |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2008 |
| 畢業學年度： | 96 |
| 語文別： | 中文 |
| 論文頁數： | 27 |
| 中文關鍵詞： | 最大外平面圖 、有界容忍表示法 、區間圖 |
| 外文關鍵詞： | Tolerance graphs, Maximal outerplanar graphs, Interval graphs |
| 相關次數： | 點閱：214 下載：19 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本文針對2-連通的最大外平面圖，討論其有界容忍表示法，且找到禁止子圖S3。我們更進一步證明：如果一個2-連通的最大外平面圖恰有兩個點的度為2時，則此圖為區間圖。
We prove that a 2-connected maximal outerplanar graph G is a bounded tolerance graph if and only if there is no induced subgraph S3 of G and G has no
induced subgraph S3 if and only if G is an interval graph.
Contents
Abstract i
中文摘要 ii
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 theorems of tolerance graphs............4
2.2 Bounded tolerance representations for trees and bipartite graphs ..........................................8
3 Some results on maximal outerplanar graphs 10
3.1 A 2-connected maximal outerplanar graph is not necessarily a tolerance graph.............................10
3.2 Bounded tolerance representations for 2-connected maximal outerplanar graphs................................15
4 Open problems and further directions of study 22
References 23
[1] K. Bogart, P. Fishburn, G. Isaak, and L. Langley, 1995. Proper and unit tolerance
graphs. Discrete Applied Math., 60 37-51.
[2] S. Felsner, 1998. Tolerance graphs and orders. J. Graph Theory, 28 129{140.
[3] S. Fisher, R. MÄuller, and L. Wernisch, 1997. Trapezoid graphs and generaliza-
tions, geometry and algorithms. Discrete Applied Math., 74 13-32.
[4] M. C. Golumbic, 1980. Algorithmic Graph Theory and Perfect graphs. Academic
Press.
[5] M. C. Golumbic and C. L. Monma, 1982. A generalization of interval graphs
with tolerances. Congress. Numer., 15 321-331.
[6] M. C. Golumbic, C. L. Monma, and W. T. Trotter, 1984. Tolerance graphs.
Discrete Applied Math., 9 157-170.
[7] M. C. Golumbic and A. N. Trenk, 2004. Tolerance graphs, Cambridge University
Press. Cambridge.
[8] M. C. Golumbic, D. Rotem, and J. Urrutia, 1983. Comparability graphs and
intersection graphs. Discrete Math., 43 37-46.
[9] R. B. Hayward and R. Shamir, 2002. A note on tolerance graph recognition.
Discrete Applied Math.
[10] M. S. Jacobsen, F. R. McMorris and E. R. Scheinerman, General results on
tolerance intersection graphs. J. Graph Theory, 15 573-578.
[11] L. Langley, 1993. Interval tolerance orders and dimension. Ph. D. thesis, Dart-
mouth College.