兩種特殊圖類直徑的上界

莊 蔚

(廈門理工學(xué)院應(yīng)用數(shù)學(xué)學(xué)院,福建廈門361024)

兩種特殊圖類直徑的上界

莊 蔚

(廈門理工學(xué)院應(yīng)用數(shù)學(xué)學(xué)院,福建廈門361024)

對(duì)邊控制臨界圖與邊控制極小圖這兩種特殊圖類的直徑進(jìn)行了研究.給出了連通的k－EDC（k≥3）圖的直徑的一個(gè)上界，并給出了4－EDC圖的直徑的一個(gè)更好的上界及3－EDC圖的直徑的可達(dá)上界.同時(shí)，利用控制點(diǎn)臨界圖的已有的結(jié)果以及一個(gè)圖的直徑與其線圖的直徑間的關(guān)系，直接給出了連通的k－EDM圖的直徑的一個(gè)上界，進(jìn)而給出了3－EDM圖和4－EDM圖的直徑的可達(dá)上界.

邊控制臨界圖；邊控制極小圖；直徑

1 主要結(jié)論

根據(jù)邊控制臨界圖與邊控制極小圖的定義,容易得到下列結(jié)論：

命題1 假設(shè)G為邊控制臨界圖,uv∈E(G－),S為G＋uv的最小邊控制集,則有

1)uv∈S；

3)u,v兩點(diǎn)在G中的關(guān)聯(lián)邊都不在S中；

4)G中沒有孤立點(diǎn).

命題2假設(shè)G是邊控制極小圖,uv∈E(G),S是G－uv的最小邊控制集,則

1)u,v兩點(diǎn)的關(guān)聯(lián)邊都不在S中；

4)G中沒有割點(diǎn).

定理1如果G是一個(gè)連通的3－EDC圖,那么diam(G)≤2.

由于完全二部圖K3,3是一個(gè)3－EDC圖,因此定理1給出的是一個(gè)上確界.下面將給出k－EDC圖(k≥4)直徑的一個(gè)上界：

定理2如果G是一個(gè)連通的k－EDC圖,k≥4,那么diam(G)≤3k－6.

顯然,定理2給出的上界并不是緊的,因此對(duì)于4－EDC圖的直徑,將給出一個(gè)改進(jìn)的上界：

定理3如果G是一個(gè)連通的4－EDC圖,那么diam(G)≤5.

在討論邊控制極小圖的直徑之前先引入幾個(gè)概念.令G＝(V,E)是一個(gè)簡單圖,S?V(G),如果對(duì)于任何一點(diǎn)v∈V(G)＼S,在S中都有鄰點(diǎn),則稱S為圖G的一個(gè)控制集.在G的所有控制集中,點(diǎn)數(shù)最少的控制集稱為最小控制集.最小控制集包含的點(diǎn)的數(shù)目稱為G的控制數(shù)γ(G).若對(duì)于任意的點(diǎn)v∈V(G),都有γ(G－v)＜γ(G),則稱G是點(diǎn)控制臨界圖.

引理1［5］如果G是控制數(shù)為k的點(diǎn)控制臨界圖 (k≥2),則diam(G)≤2k－2.

注意到,一個(gè)連通的k－EDM圖的線圖就是一個(gè)控制數(shù)為k的點(diǎn)控制臨界圖.因此從上面2個(gè)引理可以直接得到下面的結(jié)論.

定理4如果G是一個(gè)連通的k－EDM圖,k≥2,那么diam(G)≤2k－1.

顯然,定理4給出的上界并不是緊的,因此對(duì)于3－EDM和4－EDM圖的直徑,將分別給出2個(gè)改進(jìn)的上界.

定理5如果G是一個(gè)連通的3－EDM圖,那么diam(G)≤3.

定理6如果G是一個(gè)連通的4－EDM圖,那么diam(G)≤5.

由于圈C7,C10分別是3－EDM圖和4－EDM圖,且直徑分別為3和5,因此定理5和定理6給出的上界都是緊的.在下文中,由于定理1和定理3證明方法極為類似,且定理1證明過程與定理3相比更為簡單,因此將只給出定理3的證明.同樣的,由于定理5和定理6證明方法極為類似,且定理5證明過程與定理6相比更為簡單,因此將只給出定理6的證明.

2 幾個(gè)定理的證明

定理2的證明：用反證法,假設(shè)存在一個(gè)k－EDC圖G′使得diam(G′)＝t≥3k－5.必然存在a, b∈V(G′)使得的d(a,b)＝t,t≥7.令P＝ax1x2…xt－2xt－1b是a,b間的一條最短路.注意到x2xt－2?E(G′),令S是G′＋x2xt－2的最小邊控制集.在E(P)中,｛x1x2,x2x3,…,xt－3xt－2,xt－2xt－1｝被x2xt－2控制,又因?yàn)镻是a,b間的最短路,ax1和xt－1b分別由S＼｛x2xt－2｝中的兩條邊控制.如果γ′(G′)＝4,那么P中其余的邊不可能被S中的邊控制,否則a,b間將出現(xiàn)更短的路.如果γ′(G′)≥5,S中其余的k－4條邊將控制P中其余的t－6條邊.由于S＼｛x2xt－2｝中的每條邊所能控制的P中的邊的數(shù)目不多于3條,于是有t－6≤3(k－4),即t≤3k－6,與之前的假設(shè)矛盾.因此結(jié)論成立.

情形1G［V5∪V6］是完全圖.

情形2G［V5∪V6］不是完全圖.

因此結(jié)論成立.

情形1t＝7.

在G－x3x4中,令S＝｛e1,e2,e3｝是G－x3x4的一個(gè)最小邊控制集.由于x3,x4的關(guān)聯(lián)邊都不在S中,x2x3必然被x2的某條關(guān)聯(lián)邊控制,不妨設(shè)為e1.顯然,au與ax1至少有一條邊不能被e1控制,不妨設(shè)為au.假設(shè)au被e2控制,則e3可以控制｛x4x5,x5x6,x6b,bv｝中的所有邊,那么可以得到連接a, b兩點(diǎn)的長度小于7的路,矛盾.

情形2t＝6.

因?yàn)閤1不是割點(diǎn),必存在u1u2∈E(G),其中u1∈V1＼｛x1｝,u2∈V2.假設(shè)存在一條邊s1s2∈E(G),其中s1∈V3＼｛x3｝,s2∈V4＼｛x4｝,考慮G－x1u1(如果x1u1?E(G),可以考慮G－x2x3,證明過程類似),令S1＝｛e1,e2,e3｝是G－x1u1的最小邊控制集.顯然,x1,u1的關(guān)聯(lián)邊都不在S1中.由于s1s2,vb不可能被S1中的同一條邊控制,因此假設(shè)s1s2,vb分別被e1,e2控制.注意到e3不能控制｛ax1,au1,x1x2,u1u2｝中的所有邊,e1控制x1x2或u1u2.由于e3控制au1和ax1,e2控制｛x3x4,x4x5, x5b,vb｝中的所有邊,于是有e2＝x4b,矛盾.因此在G中不存在一條邊s1s2使得s1∈V3＼｛x3｝,s2∈V4＼｛x4｝.由于x3不是割點(diǎn),在V3＼｛x3｝中存在點(diǎn)s1′使得s1′在V4中有鄰點(diǎn),進(jìn)一步的,這個(gè)鄰點(diǎn)只能是x4.同理,在V4＼｛x4｝中存在點(diǎn)s2′與x3相連.通過類似于前面的推導(dǎo),同樣可以得到矛盾.

因此diam(G)≤5.結(jié)論成立.

［1］MITCHELL S，HEDETNIEMI S T.Edge domination in trees［J］.Congr Numer，1977，19：489-509.

［2］DUTTON R，KLOSTERMEYER W F.Edge dominating sets and vertex covers［J］.Discuss Math Grpah Theory，2013，33：437-456.

［3］ESCOFFIER B，MONNOT J，PASCHOS V T.New results on polynomial inapproximability and fixed parameter approximability of edge dominating set［J］.Theor Comput Syst，2015，56：330-346.

［4］XIAO M，NAGARNOCHI H.A refined exact algorithm for edge dominating set［J］.Theor Comput Sci，2014，560：207-216.

［5］FULMAN J，HANSON D，MACGILLIVRAY G.Vertex domination-critical graphs［J］.Networks，1995，25：41-43.

［6］KNOR M，NIEPEL L，SOLTES L.Centers in line graphs［J］.Math Slovaca，1993，43：11-20.

Upper Bounds of the Diameters of Two Classes of Graphs

ZHUANG Wei
（School of Applied Mathematics，Xiamen University of Technology，Xiamen 361024，China）

In this paper，we study the problem about the diameter of edge domination critical graph and edge domination minimal graph.For k≥3，we obtain an upper bound of the diameter of connected k－EDC graph.Furthermore，we obtain a better upper bound of the diameter of 4－EDC graph and a sharp upper bound of the diameter of 3－EDC graph.Meanwhile，we use some results of domination vertex critical graph and the relationship between the diameter of a graph G and the diameter of the line graph L（G）of G to obtain an upper bound of the diameter of a connected k－EDM graph.Furthermore，we obtain the sharp upper bounds of the diameters of 3－EDM graph and 4－EDC graph.

edge domination critical graph；edge domination minimal graph；diameter

O157

A

1673－4432（2015）05－0080－04

（責(zé)任編輯 李 寧）

2015－06－26

2015－10－10

國家自然科學(xué)基金項(xiàng)目 (11301440)；福建省自然科學(xué)基金項(xiàng)目 (2015J05017)；廈門理工學(xué)院高層次人才項(xiàng)目 (YKJ12026R)

莊蔚(1983－),男,講師,博士,研究方向?yàn)榻M合圖論.E-mail：2012111002＠xmut.edu.cn