C6的排斥下整和數(shù).doc

的排斥下整和數(shù)高秀蓮（德州學院數(shù)學系, 山東德州, ,253023）摘 要：下整和標號與排斥下整和標號是圖的新的壓縮表示一個圖 G 稱為下整和圖,若它同構(gòu)于某個 S Q+的下整和圖.本文證明了的排斥下整和數(shù)是2.關(guān)鍵詞：；下整和數(shù)；下整和標號；下整和圖中圖分類號：O157.5文中所用圖論基本術(shù)語與符號遵循文獻1.1990年Harary2提出和圖的概念；1994年Harary3提出整和圖的概念.令N(Z)表示正整數(shù)(整數(shù))集，N(Z)的非空有限子集S的和(整和)圖G+(S)是圖其中 (S,E)，其中uvE當且僅當u+vS .一個圖G稱為和(整和)圖,若它同構(gòu)于某個SN(Z)的和(整和)圖.即S給出了G的一個和(整和)標號,并且將頂點與其標號不加區(qū)分.G的和數(shù)(整和數(shù)) （）是使得GnK1是和圖(整和圖)的非負整數(shù)n的最小值.2003年Miller4等人提出了排斥圖的概念.圖GnK1 的(整)和標號S稱為排斥的(exclusive)，若對每條邊E(G),u+v S V(G).如果GnK1的任意邊的兩端點（標號）之和都是孤立點，則G稱為排斥圖；圖G的排斥（整）和數(shù)（）是使得 GnK1 有排斥(整)和標號的非負整數(shù)n的最小值.顯然對任意的圖G有； .從實用的觀點來看,各種和圖標號都可用作圖的壓縮表示，即表示圖的數(shù)據(jù)結(jié)構(gòu).當利用輸入圖的壓縮表示來工作時,數(shù)據(jù)壓縮不僅可以節(jié)省內(nèi)存,還可以加快某些圖算法的運算速度.近年來和圖理論發(fā)展很快，可參見文獻5 6 7. 2004年李敏8提出下整和圖的概念. 用表示不超過實數(shù)的最大整數(shù)(稱為的下整數(shù)), Q+ 表示正有理數(shù)集. Q+ 的非空有限子集S的下整和圖 G+ (S) 是圖 (S,E) ,其中 uv E 當且僅當 S .一個圖 G 稱為下整和圖,若它同構(gòu)于某個 S Q+的下整和圖.我們說 S 給出 G 的一個下整和標號,并且頂點與標號不加區(qū)分.下整和數(shù) (G) 是使得GnK1 是下整和圖的非負整數(shù) n 的最小值. 下整和標號是圖的新的壓縮表示 .引理8 下整和圖G若包含作為其導出子圖，則工作點數(shù)大于1.定理的排斥下整和數(shù)是2即證明一方面由引理知.另一方面設A=,B， ,V(C6)=AB，C=,E()=,，S=V()C=ABC給出2K1的一組標號, （其中為充分大的正整數(shù)）下面驗證所給標號為2K1的一個排斥下整和標號1）顯然S中元素互異2）驗證任意邊和的下整數(shù)屬于S： 3）驗證任意不相鄰頂點標號之和下整數(shù)不屬于S：顯然因此，只需驗證任意不相鄰頂點標號之和下整數(shù)不等于,即可(1) AB中的元素：（2）AB中的元素與C中的元素之間： 顯然與AB間無邊相連; （3）顯然C間無邊相連.綜上所述此標號確為2K1的一個排斥下整和標號即.有以上兩個方面可知參考文獻 1J.A.Bondy , U.S.R.Murty. Graph Theory with ApplicationsM. New York ,Macmillan London and Elsevier,1976. 2F. Harary.Sum graphs and difference graphsJ.Congr. Numer, 1990, 72 :101108. 3F. Harary.Sum graphs over all the integersJ.Discrete Math., 1994, 124 :99105.4M. Miller, J. Ryan, et al. Exclusive sum graph labelingJ. Discrete Math.,preprint, 2003.5王海棠.和圖論與分數(shù)圖論的若干結(jié)果D.濟南:山東師范大學,2005.6Z. Chen.Integral sum graphs from identificationJ.Discrete Math, 1998 ,181: 7790.7 王海英.幾類圖的(整,模)和數(shù)D.濟南:山東師范大學, 2004.8 李敏.下整和圖與排斥下整和圖D.濟南:山東師范大學, 2006.The exclusive lower integral sum number of graph Xiulian GAO(Department of Mathematics， Dezhou University ,Dezhou Shandong 253023 ,China)Abstract: Lower integral sum labeling and exclusive lower integral sum labeling are another ways used as compressed representation of a graphA graph G is said to be an lower integral sum graph if it is isomorphic to the lower integral sum graph of some S Q+. This paper has proved The exclusive lower integral sum number of graph is 2.K