Return to search

有向圖的視線數 / Bar visibility number of oriented graph

在張宜武教授的博士論文中研究到視線表示法和視線數。我們以類似的方法定義有向圖的表示法和有向圖的視線數。
首先,我們定義有向圖的視線數為b(D) ,D為有方向性的圖,在論文中可得b(D)≦┌1/2max{△﹢(D),△﹣(D)}┐。另一個重要的結論為考慮一個平面有向圖D,對圖形D上所有的點v,離開點v的邊(進入的邊)是緊鄰在一起時,則可得有向圖的視線數在這圖形上是1(即 b(D)=1)。
另外對特殊的圖形也有其不同的視線數,即對有向完全偶圖Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐ ,而對競賽圖Dn ,可得b(Dn)≦┌n/3┐+1。 / In [2], Chang stuidied the bar visibility representations and defined bar visibility number.We defined analogously the bar visibility representation and the bar visibility number of a directed graph D.
First we show that the bar visibility number, denoted by b(D),is at most ┌1/2max{△﹢(D),△﹣(D)}┐ if D is an oriented graph.And we show that b(D)=1 for the oriented planar graphs in which all outgoing (incoming) edges of any vertex v of D appear consecutively around v.For any complete bipartite digraph Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐.For any tournament Dn,b(Dn)≦┌n/3┐+1.

Identiferoai:union.ndltd.org:CHENGCHI/B2002001695
Creators曾煥絢, Tseng, Huan-Hsuan
Publisher國立政治大學
Source SetsNational Chengchi University Libraries
Language英文
Detected LanguageEnglish
Typetext
RightsCopyright © nccu library on behalf of the copyright holders

Page generated in 0.0019 seconds