关于树与完全图的笛卡尔乘积图的连通测地数

殷巧娟

(浙江师范大学数理与信息工程学院,浙江金华 321004)

关于树与完全图的笛卡尔乘积图的连通测地数

殷巧娟

(浙江师范大学数理与信息工程学院,浙江金华 321004)

给出了两个非平凡图,确定了树与完全图的笛卡尔乘积图的连通测地数.测地数与连通测地数是图的两个重要参数.树与完全图的笛卡尔乘积图的测地数已被确定.

笛卡尔乘积;测地集;测地数;连通测地集;连通测地数

0 引言

本文仅考虑有限简单无向图.通常用 G=(V,E)表示一个图G,其中V=V(G)是图G的顶点集,E=E(G)是图 G的边集;用 d(x,y)表示图中两点之间的最短路,用ω(G)表示一个图 G的连通分支数;用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的测地集,基数最小的测地集叫做最小测地集,并把最小测地集的基数称为测地数,记为 g(G).如果S是G的测地集,且 G[S]连通,则称 S是G的连通测地集.基数最小的连通测地集叫做最小连通测地集,并把最小连通测地集的基数称为连通测地数,记为 gc(G).显然,对于任意的 n阶非平凡连通图G,有2

对于图的测地数和连通测地数,目前已有一些研究结果.Chartrand[1]等证明了:若 G是非平凡连通图,则 g(G)≤g(G×K2).吕长虹[2]给出了使等式 g(G)=g(G×K2)成立的一个充要条件.叶永升[3-4]等确定了圈与完全图、树与完全图笛卡尔乘积图的测地数.Bostjan[5]等给出了两个非平凡连通图的笛卡尔乘积图的测地数的紧的上界和下界,并给出使等式成立的图类.Santhakumaran[6]等研究了连通测地数,确定了一些图类的上连通测地数.本文给出了两个非平凡图,树与完全图笛卡尔乘积图的连通测地数,即 gc(Tn×Km)=n+m-1.

在给出主要结果之前,先给出文章中所用的记号及引理.

1 预备知识

记树 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.

性质1[4]如果 S是图Tn×Km的测地集,那么 S∩Uj≠ö(j=1,2,…,m).

性质2[7]设v1,v2,…,vk是树Tn的k个叶子结点,vk+1,vk+2,…,vn是树Tn的n-k个非叶子结点.若S是图Tn×Km的连通测地集,那么 S∩Vi≠ö(i=1,2,…,k).

性质3 设 v1,v2,…,vk是树Tn的k个叶子结点,vk+1,vk+2,…,vn是树Tn的n-k个非叶子结点.若S是图Tn×Km的连通测地集,那么 S∩Vi≠ö(i=k+1,k+2,…,n).

证明 因为 S是连通测地集必定是测地集,由性质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),则有

以下是本文的一些主要结果:

2 主要结果

定理1 设 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).设(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.不妨设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),与假设|S|=n+m-2矛盾,所以 G[S1]不连通,设ω(G[S1])=k,则2≤k≤n.设|{j1,j2,…,jn}|= t,则2 ≤t≤k.

不妨设{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 设 Tn是一棵n阶树,Km是m阶非平凡完全图,令 G=Tn×Km,则 gc(G)=n+m-1.

证明 设 S={(v1,u1),(v2,u1),…,(vn,u1),(vn,u2),(vn,u3),…,(vn,um)}.显然,G[S]连通,且|S|=n+m-1.下证 S是G=Tn×Km的测地集.

设(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的一个连通测地集,则由性质1,性质2,性质3及定理1知,gc(G)≥n+m-1.

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

推论1 设 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] 吕长虹.图和有向图的测地数[J].中国科学(A),2007,37(5):579-586.

[3] 叶永升,姚淑华,刘庆敏.关于圈与完全图的笛卡儿积的测地数[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] 叶永升,翟明清,莫艳红.树的笛卡尔积的测地数[J].应用数学学报,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-),女,江苏扬州人,硕士研究生,研究方向为图论.

[责任编辑:李春红]