跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2025/02/10 10:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:康朝翔
研究生(外文):Chaur-Shang Kang
論文名稱:圖形的測地線數
論文名稱(外文):Geodetic Numbers of Graphs
指導教授:張鎮華張鎮華引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:17
中文關鍵詞:測地線數
外文關鍵詞:Geodetic Numbers
相關次數:
  • 被引用被引用:0
  • 點閱點閱:138
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本文所討論的圖形均為簡單圖,即頂點個數為有限、邊的兩端點不一樣、邊沒有方向、以及兩個頂點之間最多只有一條邊。
對圖形G裡的任意兩個頂點u和v,集合I(u, v)為包含了u和v,以及所有位於長度為d(u, v)、端點為u和v的路徑上面的所有頂點的集合。如果S是一個頂點的子集合,則I(S)表示所有任意在S裡的兩個點u和v所構成的I(u, v)的聯集。如果I(S)剛好就是所有的頂點的話,我們就稱S為測地線集。而測地線數,g(G),就是最小的測地線集的大小。
在第一節我們介紹一些本論文所用及的定義。
第二節我們將討論圖形迪氏積的測地線數,主要的結果是對任意兩個圖形都有
g(G)≦ g(G□H),且在一些特殊的條件下等號會成立。
第三節則討論到補可簡化圖的測地線數的上界。並且我們定義了2-N-支配,一個2-N-支配集D的定義是任意一個不在集合D裡的頂點v,必有兩個不相鄰的鄰居在集合D裡面,而2-N-支配數則是最小的2-N-支配集的大小。並討論一些測地線數和2-N-支配數的等價關係。
第四節討論到樹形補可簡化圖的測地線數的上界,還設計了一個演算法來求在一個樹形圖上的2-N-支配數。
All graphs in this thesis are simple, i.e., finite, undirected, loopless and without multiple edges.
For any two vertices u and v of a graph G, a u-v geodesic is a path of length d(u, v). The set I(u, v) consists of all vertices lying on some u-v geodesic of G.. If S is a subset of V(G), then I(S) is the union of all sets I(u, v) for u and v in S. The geodetic number g(G) is the minimum cardinality among the subset S of V(G) with I(S)=V(G).
In section 1, we introduce some definitions, which is used in this thesis.
In section 2, we discuss geodetic numbers on Cartesian products of graphs. The main result is g(G) ≦ g(G□H) for any two graphs G and H. And g(G)=g(G□H) for some H with some special condition.
In section 3, we discuss an upper bound of geodetic numbers of cographs. A 2-N-dominating set of a graph G is a vertex subset D such that every vertex not in D is adjacent to two distinct non-adjacent vertices in D. Denote by g2(G) the minimum cardinality of a 2-N-dominating set in G. And we discuss the relation between geodetic numbers and 2-N-domination numbers.
In section 4, we define tree-cographs and term f-domination. And we design an algorithm to find the 2-N-domination number of a tree-cograph.
中文摘要……………………………………………………………i
英文摘要……………………………………………………………ii
目錄…………………………………………………………………iii
Section 1:Introduction………………………………………1
Section 2:Geodetic numbers of G□H………………………3
Section 3:Geodetic numbers of cographs…………………6
Section 4:Geodetic numbers of tree-cographs…………10
References………………………………………………………14
[1] M. Atici, Graph operations and geodetic numbers. Proceedings of the Thirtieth
Southeastern International Conference on Combinatorics, Graph Theory, and
Computing (Boca Raton, FL, 1999) 141 (1999), 95{110.
[2] M. Atici, On the edge geodetic number of a graph, Int. J. Comput. Math. 80
(2003), no. 7, 853{861.
[3] G. B. Chae, E. M. Palmer and W. C. Siu, Geodetic number of random graphs
of diameter 2, Australas. J. Combin. 26 (2002), 11{20.
[4] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph,
Networks 39 (2002), 1{6.
[5] G. Chartrand, E. M. Palmer and P. Zhang, The geodetic number of a graph:
a survey, Proceedings of the Thirty-third Southeastern International Conference
on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002) 156
(2002), 37{58.
[6] G. Chartrand and P. Zhang, The forcing geodetic number of a graph, Discuss.
Math. Graph Theory 19 (1999), no. 1, 45{58.
[7] G. Chartrand and P. Zhang, The geodetic number of an oriented graph, European
J. Combin 21 (2000), no. 2, 181{189.
[8] A. L. Douthat and M. C. Kong, Computing the geodetic number of bipartite
graphs, Proceedings of the Twenty-sixth Southeastern International Conference
16
on Combinatorics Graph Theory and Computing (Boca Raton, FL, 1995) 107
(1995), 113{119.
[9] F. Harary, E. Loukakis and C. Tsouros The geodetic number of a graph, Graph-
theoretic Models in Computer Science, II (Las Cruces, NM, 1988{1990), Math.
Comput. Modelling 17 (1993), no. 11, 89{95.
[10] P. Zhang, The upper forcing geodetic number of a graph, Ars Combin 62 (2002),
3{15
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文