跳到主要內容

臺灣博碩士論文加值系統

(44.211.31.134) 您好!臺灣時間:2024/07/22 19:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許峻舷
研究生(外文):Hsu, Chun-Hsien
論文名稱:Colin de Verdière圖不變量在一些圖運算下的行為
論文名稱(外文):Behaviors of the Colin de Verdière graph invariant under some graph operations
指導教授:翁志文翁志文引用關係蔡孟傑
指導教授(外文):Weng, Chih-WenChuah, Meng-Kiat
口試委員:張耀祖傅東山
口試委員(外文):Chang, Yao-TsuFu, Tung-Shan
口試日期:2018-07-02
學位類別:碩士
校院名稱:國立清華大學
系所名稱:數學系所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2018
畢業學年度:106
語文別:英文
論文頁數:22
中文關鍵詞:Colin de Verdière圖不變量完全多部圖
外文關鍵詞:Colin de Verdière graph invariantdisjoint uniongraph joinCartesian productclique sumcomplete multipartite graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:154
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
Kotlov、Lovász和Vempala[1]以graph labellings 定義了一個圖不變量ν並以此給出Colin de Verdière 圖不變量μ的另一個等價定義。當G ̸= \overline{K_2}時,這兩個圖不變量滿足等式μ(G)+ν(\overline{G})=|G|-1。這篇論文旨在探討μ和ν在一些為人熟知的圖運算下的行為,如Cartesian products、disjoint unions和graph joins。

首先我們引進“almost one-directional” labelling 來證明對於一系列的圖{G_i}的disjoint union,有不等式max ν(G_i)≤ ν(∪ G_i)≤ max ν(G_i)+1。而且我們提供了一個充分條件使得第一個等式成立。這近乎刻劃 在disjoint unions 下的行為。作為一個簡單的應用,我們能夠計算完全多部圖的μ值。除此之外,這個不等式也提供一些判斷不連通圖是否為ν-minimal graph 的必要條件。這也促使我們去探討,要如何用小的μ-maximal graphs 來生成一個給定的有separating cliques 的μ-maximal graph。藉由van der Holst、Lovász 和Schrijver 三人於[4]中所刻劃的μ在clique sum 下的行為,我們給出一個判斷μ-maximal graphs 的clique sum 是否仍是μ-maximal 的準則。最後我們證明ν在Cartesian products下的成長速率有一個以圖的片數為變數的線性成長的上界,而μ則有一個指數成長的下界。
Kotlov, Lovász and Vempala in [1] offered a reformulation for the Colin de Verdière graph invariant μ by introducing another graph invariant ν defined via graph labellings. These two parameters are related by the equality μ(G)+ν(\overline{G})=|G|-1 for G ̸= \overline{K_2}. In this paper we examine how these two invariants μ and ν vary under some well-known graph operations, such as Cartesian products, disjoint unions and graph joins.

First, we introduce "almost one-directional" labelling to derive that for the disjoint union of graphs {G_i}, max ν(G_i)≤ ν(∪ G_i)≤ max ν(G_i)+1. Also we show a sufficient condition for the first equality to hold. This nearly characterizes the behavior of ν under disjoint unions. As an application, we are able to compute the exact value μ for complete multipartite graphs. The inequality also provides us with some necessary conditions for a disconnected graph being ν-minimal. Therefore, this also motivates us to look into how μ-maximal graphs with separating cliques could be built up by smaller ones via clique sums. Using the characterization of μ under clique sum proved by van der Holst, Lovász and Schrijver in [4], we derive a criterion in judging whether a clique sum of two μ-maximal graphs is μ-maximal. Lastly, we show that the growth rate of ν under Cartesian products has a linear upper bound in the number of graphs while that of μ has a exponential lower bound in the number of graphs.
1 Introduction ...................................................1
2 Notations and terminology ......................................4
3 Characterizations of n under disjoint union ....................5
4 Decomposing m-maximal graphs with separating cliques ..........10
5 μ and ν under Cartesian products ..............................16
[1] A. Kotlov, L. Lovász, S. Vempala. The Colin de Verdière number and sphere representations of a graph. Combinatorica, 17 (1997), 483-512.

[2] F. Barioli, S. Fallat, L. Hogben. A variant on the graph parameters of Colin de Verdière: implications to the minimum rank of graphs. Electronic Journal of Linear Algebra, 13 (2005), 387-404.

[3] F. Goldberg. On the Colin de Verdière numbers of Cartesian graph products. Linear Algebra and its Applications 431 (2009), 2285-2290.

[4] H. van der Holst, L. Lovász, A. Schrijver. On the invariance of Colin de Verdière's graph parameter under clique sums, Linear Algebra Appl. 226 (1995) 509-519.

[5] H. van der Holst, L. Lovász, A. Schrijver. The Colin de Verdière graph parameter. Bolyai Soc Math Stud, 7 (2009).

[6] N. Robertson, P. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2) (2004), 325-357

[7] P. Seymour. Hadwiger's conjecture, in Open Problems in Mathematics (J. Nash Jr. and M. Rassias, eds.). Springer, (2016) 417-437.

[8] R. McCarty. The Extremal Function and Colin de Verdière Graph Parameter. arXiv:1706.07451.

[9] R. Pendavingh. On the relation between two minor-monotone graph parameters. Combinatorica, 18(2) (1998), 281-292.

[10] Y. C. Chen, Y. L. Syu. Connected Dominating Set of Hypercubes and Star Graphs. International Conference on Software and Computer Applications, 2012, 41.

[11] Y. Colin de Verdière. Sur un nouvel invariant des graphes et un critère de pla-nariète. Journal of Combinatorial Theory Series B., 50, (1990), 11-21.
22
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top