有關線圖兩個性質的討論

孫林，蔡華，楊紅梅

(1.山東大學 數學學院，山東 濟南 250000；2.昌吉學院 數學系，新疆 昌吉 831100)

有關線圖兩個性質的討論

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

(1.山東大學 數學學院，山東 濟南 250000；2.昌吉學院 數學系，新疆 昌吉 831100)

通過介紹線圖的內部結構，對線圖的連通性以及線圖是否為自補圖的問題進行了詳細的討論，并得出一些結果.

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

1 引言

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

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

定理1.1[4]設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]設G是無向圖，λL≥2λG-2

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

2 線圖的內部結構及相關定理

線圖的特有結構基本是通過線圖的禁用子圖來體現，在文獻[2]中線圖的禁用子圖已經給出，但是關于其證明，很少有相關文獻研究，現就其中一種重要禁用子圖K1,3給出簡潔的證明方法.

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

證明：反證法，假設某線圖L(G)含4階導出子圖K1,3，則K1,3應是由G的4條邊導出子圖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.

設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

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

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

由以上的定理，可以得到以下兩個關于線圖的結論：

結論一：在文獻[5]中，給出了關于判定某圖是否為線圖的一個必要條件：

但是此結論反之則不成立.

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

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

3 主要結論

3.1 線圖的連通性

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

圖1 原圖的連通性質和其線圖的連通性質的關系

命題3.1.1 設G=(V,E)是無孤立點的無向圖，若λG≥3,則λL=2λG-1當且僅當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.

假設λ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 設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′]中的邊構成一條(x,u)鏈，因此，G中有一條(x,y)路.由x,y∈V(G[E′])的任意性知，G[E′]也是強連通的.

3.2 線圖的自補圖的性質

線圖的同構性質也可以在某些特殊情況下從原圖中得到.如果T1,T2是兩棵樹，且L(T1)?L(T2)，那么T1?T2，但是對于任何圖G不一定成立.例如，K3是K3和K1,3的線圖，但K3與K1,3不同構.同時還有自補圖的概念，即Gc是圖G的補圖，若G?Gc，則稱圖G是自補圖.以下討論關于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關聯的k條邊ee,e2,…,ek，設ee,e2,…,ek的不同于x的另一個端點為y1,y2,…,yk.

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

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

由K3,3的性質知，L(K3,3)是9個頂點的4-正則圖，且L(K3,3)中的頂點由K3,3中其對應的邊的兩個頂點來表示，即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)與其補圖的鄰接關系，所以L(K3,3)是自補的.

根據線圖和原圖的關系，當以L(G)為自補圖時，可以根據這一特性，得出原圖相應的性質，由此，以下討論L(G)為自補圖的必要條件.

所以

即

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

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

[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].北京:機械工業出版社,2004:273- 282.

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

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

[5]徐俊明.組合網絡理論[M].北京：科學出版社,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-)，女，陜西漢中人，山東大學數學學院在讀博士研究生，昌吉學院數學系講師，主要從事圖論及其應用的研究.

閆昕]