孫林，蔡華，楊紅梅

(1.山東大學(xué) 數(shù)學(xué)學(xué)院，山東 濟(jì)南 250000；2.昌吉學(xué)院 數(shù)學(xué)系，新疆 昌吉 831100)

有關(guān)線圖兩個性質(zhì)的討論

孫林1,2，蔡華1,2，楊紅梅2

(1.山東大學(xué) 數(shù)學(xué)學(xué)院，山東 濟(jì)南 250000；2.昌吉學(xué)院 數(shù)學(xué)系，新疆 昌吉 831100)

通過介紹線圖的內(nèi)部結(jié)構(gòu)，對線圖的連通性以及線圖是否為自補圖的問題進(jìn)行了詳細(xì)的討論，并得出一些結(jié)果.

線圖；K1,3；邊連通度；強連通；自補圖①

1 引言

線圖的概念是由Harary 和Normal 于1960年首先提出來的.它是從一個已知圖構(gòu)造另一個圖的重要方法.線圖中的許多圖論性質(zhì)，比如頂點度，連通性，同構(gòu)等都可以很方便地從原始圖導(dǎo)出來.線圖是從圖中與邊有關(guān)的性質(zhì)導(dǎo)出與頂點有關(guān)的性質(zhì)的重要工具.文中主要用到以下基本概念和性質(zhì).

設(shè)G是一個圖,分別用V(G)和E(G)表示圖G的頂點集和邊集，用dG(x)表示頂點x在G中的度數(shù)，N(x)表示頂點x的鄰點集. 設(shè)G=(V,E)是無孤立點的無向圖，G的線圖記為L(G)，L(G)的頂點集為E(G)，L(G)中頂點e1,e2相鄰當(dāng)且僅當(dāng)它們在G中相鄰.如果在G中存在Φ≠B?E(G)，使得G-B中的連通分支數(shù)大于G中的連通分支數(shù)，則稱B為G中的邊割集，λG為G中所有邊割集的最小邊數(shù).設(shè)G=(V,E)是無孤立點的有向圖(可以有環(huán)和平行邊)，G的線圖記為L(G)，L(G)的頂點集為E(G)，L(G)中頂點a,b相鄰當(dāng)且僅當(dāng)在G中a的終點是b的起點.有向圖的線圖通常簡稱為有向線圖.圖G的禁用子圖G′指的是：若圖G存在，則此圖不可能含有子圖G′.文中所涉及到的圖G均為無向簡單圖或有向簡單圖.未說明的記號和術(shù)語參見文獻(xiàn)[1,2，3].

定理1.1[4]設(shè)G是無向圖，L(G)是G的線圖,則

(1)L(G)是簡單圖，有ν(L(G))=ε(G)

(2)e=xy∈E(G),有dL(G)(e)=dG(x)+dG(y)-2，因此δ(L(G))=ξ(G)

定理1.3[6]設(shè)G是無向圖，λL≥2λG-2

記λL為線圖L(G)的邊連通度，δL為線圖L(G)的最小度，即圖G的最小邊度.

2 線圖的內(nèi)部結(jié)構(gòu)及相關(guān)定理

線圖的特有結(jié)構(gòu)基本是通過線圖的禁用子圖來體現(xiàn)，在文獻(xiàn)[2]中線圖的禁用子圖已經(jīng)給出，但是關(guān)于其證明，很少有相關(guān)文獻(xiàn)研究，現(xiàn)就其中一種重要禁用子圖K1,3給出簡潔的證明方法.

定理2.1[2]任何線圖都不含4階導(dǎo)出子圖K1,3.

證明：反證法，假設(shè)某線圖L(G)含4階導(dǎo)出子圖K1,3，則K1,3應(yīng)是由G的4條邊導(dǎo)出子圖H的線圖.由引言的定理1.1(1)(3)分別可得，

ν(K1,3)=4,ε(K1,3)=3,ε(H)=4.

所以

①

由上式知，?x∈V(H),dH(x)≤3，又知H是連通圖，所以?x∈V(H),1≤dH(x)≤3.

設(shè)H中有n1個1度頂點，n2個2度頂點，n3個3度頂點，則ν(H)=n1+n2+n3.

由①式得

n1+4n2+9n3=14

②

由握手定理得

n1+2n2+3n3=8

③

②-③得

n2+3n3=3,0≤ni,i∈{1,2,3}

所以

n2=0,n3=1或n2=3,n3=0

由①式得

n1=5,n2=0,n3=1或n1=2,n2=3,n3=0

由此產(chǎn)生兩個度序列，分別為(1,1,1,1,1,3)或(1,1,2,2,2)，第一個度序列不可圖示化，第二個度序列對應(yīng)唯一一個圖P4，但其線圖不是K1,3.

由此這樣的H不存在，所以任何線圖都不含4階導(dǎo)出子圖K1,3.

由以上的定理，可以得到以下兩個關(guān)于線圖的結(jié)論：

結(jié)論一：在文獻(xiàn)[5]中，給出了關(guān)于判定某圖是否為線圖的一個必要條件：

但是此結(jié)論反之則不成立.

但由定理2.1.1知，K1,3不是P4的線圖.

結(jié)論二：線圖中任何頂點子集的導(dǎo)出子圖是某個圖的線圖，但對于邊導(dǎo)出子圖，此論述不正確.線圖L(G)中可以有邊導(dǎo)出子圖為K1,3，但由定理2.1.1知，此子圖不是任何圖的線圖.

3 主要結(jié)論

3.1 線圖的連通性

連通性是線圖的重要性質(zhì)，我們試圖從原圖當(dāng)中推出其線圖連通方面的結(jié)果.其中，易得λ(G)≥κ(L(G))不成立.由圖1可看出，圖G的最小邊割集不一定是L(G)的最小點割集，如圖1，圖G的一個最小邊割為{e1,e2,e3}，但{e1,e2,e3}不是L(G)的最小點割集.以下命題主要討論原圖的連通性質(zhì)和其線圖的連通性質(zhì)的關(guān)系.

圖1 原圖的連通性質(zhì)和其線圖的連通性質(zhì)的關(guān)系

命題3.1.1 設(shè)G=(V,E)是無孤立點的無向圖，若λG≥3,則λL=2λG-1當(dāng)且僅當(dāng)G中存在兩個相鄰的頂點x和y使得dG(x)=λG且dG(y)=λG+1，且

e=xy∈E(G),ξ(G)=dL(e)=δL.

由定理1.2知，λL=δL，則存在e=xy∈E(G)且ξ(G)=dL(e)=δL，使得

2λG≤dG(x)+dG(y)=ξ(G)+2=δL+2=2λG+1.

另一方面，dG(x)≥λG,dG(y)≥λG

所以

dG(y)=λG,dG(x)=λG+1或dG(y)=λG+1,dG(x)=λG.

? 已知x和y是G中兩個相鄰的頂點，且dG(x)=λG,dG(y)=λG+1，則

λL≤δL=ξ(G)=dG(x)+dG(y)-2=2λG-1

由定理1.3知，λL≥2λG-2，所以λL=2λG-2或λL=2λG-1.

假設(shè)λL=2λG-2，見必要性證明，同理可得λL=δL，所以

λL=δL=2λG-2≤2δG-2≤ξ(G)=δL

所以2δG-2=ξ(G)，這與e=xy∈E(G),ξ(G)=dL(e)=δL=2λG+1矛盾.所以λL=2λG-1.

命題3.1.2 設(shè)G=(V,E)是無孤立點的簡單有向圖，E′?E(G),|E′|≥2,L′是L(G)的子圖使得E′=V(L′)，則如果L′是強連通，則G[E′]也是強連通的.

證明：由L′是強連通有向圖，?x,y∈V(G[E′])，則存在a,b∈E′，使得

a=(x,z),b=(y,u)∈E′.

因為L′是強連通 ，則a,b之間至少存在一條有向路，令W=(a,a1,a2,…,am,b)是L′中一條最短(a,b)路，這條路中的頂點，即G[E′]中的邊構(gòu)成一條(x,u)鏈，因此，G中有一條(x,y)路.由x,y∈V(G[E′])的任意性知，G[E′]也是強連通的.

3.2 線圖的自補圖的性質(zhì)

線圖的同構(gòu)性質(zhì)也可以在某些特殊情況下從原圖中得到.如果T1,T2是兩棵樹，且L(T1)?L(T2)，那么T1?T2，但是對于任何圖G不一定成立.例如，K3是K3和K1,3的線圖，但K3與K1,3不同構(gòu).同時還有自補圖的概念，即Gc是圖G的補圖，若G?Gc，則稱圖G是自補圖.以下討論關(guān)于L(G)為自補圖的一個充分條件.

命題3.2.1L(G)為k-正則圖G(k≥1)的線圖，且n=2k.若在G中有2k個完美匹配，且存在一個頂點x∈V(G)，滿足

則L(G)為自補圖.

證明：因為G中存在一個頂點x∈V(G)，有

則可將G中得邊按如下排列：第一行為與x關(guān)聯(lián)的k條邊ee,e2,…,ek，設(shè)ee,e2,…,ek的不同于x的另一個端點為y1,y2,…,yk.

例L(K3,3)是自補的.

證明：設(shè)K3,3的兩部分頂點集為V,V′，V={1,2,3},V′={1′,2′,3′} .

由K3,3的性質(zhì)知，L(K3,3)是9個頂點的4-正則圖，且L(K3,3)中的頂點由K3,3中其對應(yīng)的邊的兩個頂點來表示，即V(L(K3,3))={11′,12′,13′,21′,22′,23′,31′,32′,33′}.

我們可以建立一雙射φ，

φ(11′)=11′,φ(12′)=22′,φ(13′)=33′

φ(21′)=23′,φ(22′)=31′,φ(23′)=12′

φ(31′)=32′,φ(32′)=13′,φ(33′)=21′

從上述映射可以看出每一行的像集Gi與每一列的像集Hj分別是K3,3的匹配，i,,j∈{1,2,3}. 顯然，此匹配映射φ保持L(K3,3)與其補圖的鄰接關(guān)系，所以L(K3,3)是自補的.

根據(jù)線圖和原圖的關(guān)系，當(dāng)以L(G)為自補圖時，可以根據(jù)這一特性，得出原圖相應(yīng)的性質(zhì)，由此，以下討論L(G)為自補圖的必要條件.

所以

即

(2,1),(5,2),(6,3),(7,6)

通過介紹線圖的內(nèi)部結(jié)構(gòu)，對線圖的連通性以及線圖是否為自補圖的問題進(jìn)行了詳細(xì)的討論，并得出一些結(jié)果.但是，關(guān)于線圖為自補圖的充分必要條件還沒有得出結(jié)果，希望在以后的研究中解決此類問題.

[1] Bondy J A,Murty USR. Graph Theory and Application[M]. NewYork: Academic press,1976：42-45.

[2] Douglas B.Introduction to Graph Theory[M].北京:機械工業(yè)出版社,2004:273- 282.

[3]殷劍宏,吳開亞.圖論及其算法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社,2003:20-21.

[4]Lowell W.Beineke,Robin J.Wilson,Selected Topics in Graph Theory[M].NewYork, Academic press,1978：273-274.

[5]徐俊明.組合網(wǎng)絡(luò)理論[M].北京：科學(xué)出版社,2007:40-41.

[6]Hellwig A, Rautenbach D, Volkmann L. Note on the connectivity of line graphs [J]. Inform Process Lett, 2004, 91(1): 7-10.

SomeTopicsonLineGraphs

SUN Lin1,2,CAI hua1,2,Yang Hong-mei2

(1.College of Mathematics,Shandong University,Jinan 250000,China;2.Department of Maths,Changji 831100,China)

In this paper, firstly, the structures of line graphs are discussed. Secondly, its connectivity and self-complementary property are stated, some results of which are given.

Line graphs; K1,3; edge connectivity; strong connectivity; self-complementary graph

O153.3

A

1004-7077(2013)05-0055-05

2013-09-02

孫林(1981-)，女，陜西漢中人，山東大學(xué)數(shù)學(xué)學(xué)院在讀博士研究生，昌吉學(xué)院數(shù)學(xué)系講師，主要從事圖論及其應(yīng)用的研究.

閆昕]