簡易檢索 / 詳目顯示
| 研究生： |
呂吉祥 |
|---|---|
| 論文名稱： |
圖的全星數 The total star number of graphs |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 1997 |
| 畢業學年度： | 85 |
| 語文別： | 英文 |
| 論文頁數： | 24 |
| 外文關鍵詞： | Multiple-star representation, Total star number |
| 相關次數： | 點閱：148 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
A multiple-star representation of a simple graph G assigns each vertex a union of stars in a host tree, such that vertices are adjacent if and only if their assigned sets intersect. The total star number S(G) is the minimum of the total number of stars used in any such representation of G. We obtain the maximum value of S(G) for m-edge connected graphs: m + 1, n-vertex graphs: [n<sup>2</sup> + 1)/ 4], and n-vertex outer-planar graphs: [3n /2-l]
0 INTRODUCTION-----1
1 S(G) OF SOME EXAMPLES-----5
1.1 Some graphs with S(G) = n-----5
1.2 Some graphs with S(G) > n-----7
2 EXTREMAL PROBLEMS FOR TOTAL STAR NUMBER-----12
2.1 Graphs with m edges-----12
2.2 Graphs on n vertices-----14
3 OUTER-PLANAR GRAPHS ON n VERTICES-----18
Appendix A Comparison table-----23
REFERENCE-----24
(限達賢圖書館四樓資訊教室A單機使用)