(3.210.184.142) 您好!臺灣時間:2021/05/09 09:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉宣谷
論文名稱:線星數極值問題
論文名稱(外文):Extremal Problems for Linear Star Number
指導教授:張宜武
指導教授(外文):Yi-Wu Chang
學位類別:碩士
校院名稱:國立政治大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:24
中文關鍵詞:星形表示法線星表示法毛毛蟲
外文關鍵詞:star representationlinear star representationcaterpillar
相關次數:
  • 被引用被引用:0
  • 點閱點閱:118
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中,我們藉由討論線星數和星數之間的關係得到線星數的邊界值。我們藉由星數得到線星數的上界為:$s^*(G) \leq 3s(G)$。當我們限制某些induced subgraphs,我們得到線星數的上界。當G沒有induced $K_4-{e}$, 我們得到$s^*(G) \leq s(G)+1$。而且,triangle-free graph 的線星數上界也是 $s(G)+1$。 當圖形G的$\triangle (G)=3$,我們得到星數等於線星數。圖形G的$\triangle (G)=4$,我們也可得到 $s(G)+1$。

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) \leq 3s(G)$. When we forbid certain induced subgraphs, we obtain an upper bound on linear star number. If G is a graph without induced $K_4-{e}$, we prove that $s^*(G) \leq 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 $\triangle (G)=3.$ When G is a graph with $\triangle (G)=4$. , we also obtain $s(G)+1$.

1 Introduction
2 A General Upper Bound of Linear star Number
3 Bounds of Linear Star Number in Restricted classes

@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},
}
% ------------------------------------------------------------------------

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔