# 臺灣博碩士論文加值系統

(44.211.31.134) 您好！臺灣時間：2024/07/22 19:20

:::

### 詳目顯示

:

• 被引用: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 ...................................................12 Notations and terminology ......................................43 Characterizations of n under disjoint union ....................54 Decomposing m-maximal graphs with separating cliques ..........105 μ 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
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 複投影空間的辛幾何 2 生滅鏈的相變現象 3 戊類圖型的組合演算 4 某些奇異李超代數的圖表 5 簡單有向圖的布勞帝-賀夫曼推測 6 拋物型方程柯西問題解的爆破行為 7 二分圖的譜半徑 8 圓石分配圖的研究 9 OnArithmeticofCurvesoverFunctionFields 10 複單李代數上的有限維對角的自同構 11 漆圖的組合問題 12 圖的點邊度和邊點度 13 有向圖譜半徑之簡易比較方法 14 使用 CUDA 函數庫實現 BiCGstab 與 BiCGstab(L)方法 的 GPU 平行化 15 利用一維度模擬二階與四階生物 離子通道模型的電位與濃度

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室