關(guān)于樹與完全圖的笛卡爾乘積圖的連通測地數(shù)

殷巧娟

(浙江師范大學數(shù)理與信息工程學院,浙江金華 321004)

關(guān)于樹與完全圖的笛卡爾乘積圖的連通測地數(shù)

殷巧娟

(浙江師范大學數(shù)理與信息工程學院,浙江金華 321004)

給出了兩個非平凡圖,確定了樹與完全圖的笛卡爾乘積圖的連通測地數(shù).測地數(shù)與連通測地數(shù)是圖的兩個重要參數(shù).樹與完全圖的笛卡爾乘積圖的測地數(shù)已被確定.

笛卡爾乘積;測地集;測地數(shù);連通測地集;連通測地數(shù)

0 引言

本文僅考慮有限簡單無向圖.通常用 G=(V,E)表示一個圖G,其中V=V(G)是圖G的頂點集,E=E(G)是圖 G的邊集;用 d(x,y)表示圖中兩點之間的最短路,用ω(G)表示一個圖 G的連通分支數(shù);用N(v)表示頂點v的所有鄰點的集合;對于S?V(G),用G[S]表示G中由頂點集S導出的子圖.

對于連通圖 G中的任意兩點u和v,u-v測地線是指u和v之間的最短路;I(u,v)表示位于 u-v所有測地線上的頂點的集合;對于子集 S?V(G),I(S)表示所有 I(u,v)的并,其中 u,v∈S,即I(S)= ∪u,v∈SI(u,v).

如果I(S)=V(G),則稱S是G的測地集,基數(shù)最小的測地集叫做最小測地集,并把最小測地集的基數(shù)稱為測地數(shù),記為 g(G).如果S是G的測地集,且 G[S]連通,則稱 S是G的連通測地集.基數(shù)最小的連通測地集叫做最小連通測地集,并把最小連通測地集的基數(shù)稱為連通測地數(shù),記為 gc(G).顯然,對于任意的 n階非平凡連通圖G,有2

對于圖的測地數(shù)和連通測地數(shù),目前已有一些研究結(jié)果.Chartrand[1]等證明了:若 G是非平凡連通圖,則 g(G)≤g(G×K2).呂長虹[2]給出了使等式 g(G)=g(G×K2)成立的一個充要條件.葉永升[3-4]等確定了圈與完全圖、樹與完全圖笛卡爾乘積圖的測地數(shù).Bostjan[5]等給出了兩個非平凡連通圖的笛卡爾乘積圖的測地數(shù)的緊的上界和下界,并給出使等式成立的圖類.Santhakumaran[6]等研究了連通測地數(shù),確定了一些圖類的上連通測地數(shù).本文給出了兩個非平凡圖,樹與完全圖笛卡爾乘積圖的連通測地數(shù),即 gc(Tn×Km)=n+m-1.

在給出主要結(jié)果之前,先給出文章中所用的記號及引理.

1 預(yù)備知識

記樹 Tn和完全圖Km的頂點集分別為V(Tn)={v1,v2,…,vn}和V(Km)={u1,u2,…,um}.在 G= Tn×Km中,記頂點集{(vi,uj)|j=1,2,…,m}為Vi,頂點集{(vi,uj)|i=1,2,…,n}為 Uj.顯然,G[Vi]?Km,G[Uj]?Tn.

性質(zhì)1[4]如果 S是圖Tn×Km的測地集,那么 S∩Uj≠?(j=1,2,…,m).

性質(zhì)2[7]設(shè)v1,v2,…,vk是樹Tn的k個葉子結(jié)點,vk+1,vk+2,…,vn是樹Tn的n-k個非葉子結(jié)點.若S是圖Tn×Km的連通測地集,那么 S∩Vi≠?(i=1,2,…,k).

性質(zhì)3 設(shè) v1,v2,…,vk是樹Tn的k個葉子結(jié)點,vk+1,vk+2,…,vn是樹Tn的n-k個非葉子結(jié)點.若S是圖Tn×Km的連通測地集,那么 S∩Vi≠?(i=k+1,k+2,…,n).

證明 因為 S是連通測地集必定是測地集,由性質(zhì)2可知

因為樹中的任意不同兩頂點恰由一條路所連接,對任意 i,i∈{k+1,k+2,…,n},存在

在圖 Tn×Km中任意一條連接(vt,ujt)和(vs,ujs)的路 P,都有

從而Vi是圖Tn×Km的點割集.又因為 S是連通測地集且S∩Vt≠?(t=1,2,…,k),則有

以下是本文的一些主要結(jié)果:

2 主要結(jié)果

定理1 設(shè) G=Tn×Km(n,m ≥2),S?V(G),S∩Vi≠?(i=1,2,…,n)且 S∩Uj≠?(j=1,2,…,m),若 |S|=n+m-2,則 G[S]不連通.

證明 因為 S∩Vi≠?(i=1,2,…,n).設(shè)(vi,uji)∈S∩Vi,(i=1,2,…,n).記 S1={(vi,uji)|i=1,2,…,n},則 S1? S且|S1|= n.

下證 G[S1]不連通.

若 G[S1]連通,則j1=j2= …=jn.不妨設(shè)j1=j2= …=jn=1,則|S∩U1|=n.因為S∩Uj≠?(j=1,2,…,m),所以|S ∩Uj|≥1(j=2,…,m).顯然,對任意 i≠j,Ui∩Uj= ?.故|S|≥n+(m-1),與假設(shè)|S|=n+m-2矛盾,所以 G[S1]不連通,設(shè)ω(G[S1])=k,則2≤k≤n.設(shè)|{j1,j2,…,jn}|= t,則2 ≤t≤k.

不妨設(shè){j1,j2,…,,jn}={1,2,…,t},即 S1? U1∪U2∪…Ut且對任意t

令 S3=S{S1∪S2},則|S3|=(n+m-2)-n-(m-t)=t-2≥0.

若 S3= ?,ω(G[S])=ω(G[S1∪S2])=k≥t≥2,即 G[S]不連通.

若 S3≠?,對(vp,uq)∈S3,由笛卡爾乘積的定義,N(vp,uq)?Vp∪Uq.所以ω(G[S])≥t-|S3|=t-(t-2)=2,即 G[S]不連通.

綜上所述,引理得證.

定理2 設(shè) Tn是一棵n階樹,Km是m階非平凡完全圖,令 G=Tn×Km,則 gc(G)=n+m-1.

證明 設(shè) S={(v1,u1),(v2,u1),…,(vn,u1),(vn,u2),(vn,u3),…,(vn,um)}.顯然,G[S]連通,且|S|=n+m-1.下證 S是G=Tn×Km的測地集.

設(shè)(vi,uj)∈V(G)且(vi,uj)?S,(i∈{1,2,…,n},j∈{1,2,…,m}).則存在(vi,u1),(vn,uj)(1≤i≤n,1≤j≤m),使得(vi,uj)在(vi,u1)-(vn,uj)測地線上,其中(vi,u1),(vn,uj)∈S,所以I(S)=V(G),由定義,S是Tn×Km的測地集,又因為 G[S]連通,所以 gc(G)≤n+m-1.

若 S是Tn×Km的一個連通測地集,則由性質(zhì)1,性質(zhì)2,性質(zhì)3及定理1知,gc(G)≥n+m-1.

綜上所述,gc(G)=n+m-1,即有 gc(Tn×Km)=n+m-1.

推論1 設(shè) Pn(n≥2)是一條 n階路,Km是m階非平凡完全圖,令 G=Pn×Km,則 gc(G)=n+m-1.

[1] Chartrand G,Harary F,Zhang P.On the geodetic number of a graph[J].Networks,2002,39:1-6.

[2] 呂長虹.圖和有向圖的測地數(shù)[J].中國科學(A),2007,37(5):579-586.

[3] 葉永升,姚淑華,劉慶敏.關(guān)于圈與完全圖的笛卡兒積的測地數(shù)[J].淮北煤炭師范學院學報,2006,27(3):12-14.

[4] Ye Y S,Lv C H,Liu Q M.The geodetic number of Cartesian products of graph[J].Mathematic Applicata,2007,20(1):158-163.

[5] Bostjan B,Sandi K,Aleksandra T H.On the geodetic number and related metric sets in Cartesian product graphs[J].Discrete Mathematics,2008,308:5555-5561.

[6] Santhakumaran A P,Titus P,John J.The upper connected geodetic number and forcing connected geodetic number of a graph[J].Discrete Applied Mathematics,2009,157:1571-1580.

[7] 葉永升,翟明清,莫艷紅.樹的笛卡爾積的測地數(shù)[J].應(yīng)用數(shù)學學報,2008,31(3):514-519.

The Connected Geodetic Number of Cartesian Products of Tree andComplete Graph

YIN Qiao-juan
(College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua Zhejiang 321004,China)

Geodetic number and connected geodetic number are two important parameters of graphs.The geodetic number of Cartesian products of tree and complete graph has been determined.This paper determines the connected geodetic number of Cartesian products of tree and complete graph.

cartesian product;geodetic set;geodetic number;connected geodetic set;connected geodetic number

O157.5

A

1671-6876(2010)04-0299-03

2010-04-23

殷巧娟(1986-),女,江蘇揚州人,碩士研究生,研究方向為圖論.

[責任編輯:李春紅]