分裂圖O_{m}vee K_{2}的IC-著色

On the IC-Colorings of Split Graphs O_{m}vee K_{2}

陳建彰(Chen-Chien Chang)

指導教授 ： 史青林

中原大學/理學院/應用數學系/碩士(2008年)

https://doi.org/10.6840/CYCU.2008.00053

摘要

令G是一個圖, , f為將圖G的每一個頂點對應到正整數集合的函數我們定義, f(H)=sum_{vin V(H)}f(v), 其中H為G的任何子圖_{。}如果對於任一個正整數, kin{1,2,cdots,f(G)},存在一個連通子圖, H,使得, f(H)=k, 則我們稱函數f為圖G的IC-著色_{。}圖G的IC-指數, 記為 M(G), 且定義, M(G)=max,{f(G),mid, f 是G的IC-著色}_{。}

令G和H是兩個互斥圖, 我們定義G和H的連結圖, 記為Gvee H，是有點集合V=V(G)cup V(H)和邊集合E=E(G)cup E(H)cup{(u,v):|: uin V(G),: vin V(H)}的圖_{。} 令O_{m}是有, m,個點但沒有邊的圖, 則我們稱O_{m}vee K_{n}為分裂圖_{。}翁韻淳left[12
ight]證明出當 mgeq2 且 ngeq3 時, M(O_{m}vee K_{n})=2^{m+n}-2^{m}+1, 只剩下n=2的情況未解決_{。}

在這篇論文中, 我們證明對所有的整數 mgeq2,M(O_{m}vee K_{2})=2^{m+2}-2^{m}+1_{。}這個結果完成找每一個分裂圖的指標的問題_{。}

關鍵字

IC-指標 ； 分裂圖 ； IC-著色

並列摘要

Let G be a graph, and let f be a function mapping V(G) into the set of positive integers. We define f(H)=sum_{vin V(H)}f(v) for any subgraph H of G. The function f is called an IC-coloring of G if for any integer kin{1,2,cdots,f(G)} there is a connected subgraph H of G such that f(H)=k. The IC-index of G, denoted by M(G), is defined to be M(G)=max,{f(G),mid, f, is, an, IC-coloring, of, G,}.

Let G and H be two disjoint graphs. The join of G and H , denoted by Gvee H, is the graph with the vertex set V=V(G)cup V(H) and the edge set. E=E(G)cup E(H)cup{(u,v):|: uin V(G),: vin V(H)}. Let O_{m} be a graph with m vertices and no edges. Then we say the graph O_{m}vee K_{n} to be a split graph.Weng left[12
ight] show that M(O_{m}vee K_{n})=2^{m+n}-2^{m}+1 for O_{m}vee K_{n}, mgeq2 and ngeq3. Only the case n=2 is unsolved.

In this thesis, we show that M(O_{m}vee K_{2})=2^{m+2}-2^{m}+1 for each integer mgeq2_{。} This completes to find the IC-index for each split graph.

並列關鍵字

split graph ； IC-index ； IC-coloring

參考文獻

[1] R. Alter and J. A. Barnett, A postage stamp problem, Amer. Math. monthly

[3] G. Chartrand, Introduction to graph theory, McGraw-Hill Higher Education, c2005

[6] R. Guy, The postage Stamp Problem, Unsolved Problems in Number Theory, second

Tech. Rep. 95-29 (1995), 1–9.

[8] E. Salehi, Sin-Min Lee and M. Khatirinejad, IC-Colorings and IC-Indices of graphs,