一類積圖的測(cè)地?cái)?shù)

王 兵，呂長(zhǎng)虹，張 梅

（1.華東師范大學(xué) 數(shù)學(xué)系，上海200062；2.滁州學(xué)院 數(shù)學(xué)系，安徽 滁州239000）

一類積圖的測(cè)地?cái)?shù)

王 兵1，2，呂長(zhǎng)虹1，張 梅2

（1.華東師范大學(xué) 數(shù)學(xué)系，上海200062；2.滁州學(xué)院 數(shù)學(xué)系，安徽 滁州239000）

圖中的度量空間是（V（G），d），測(cè)地?cái)?shù)是其中的一個(gè)重要參數(shù).強(qiáng)積圖是圖與圖之間通過一種乘積運(yùn)算得到的圖.文中得到了極點(diǎn)測(cè)地圖的強(qiáng)積圖的測(cè)地?cái)?shù)，由此得到了樹的強(qiáng)積圖的測(cè)地?cái)?shù)。

測(cè)地?cái)?shù)；強(qiáng)積圖

0 引言

對(duì)于u∈V（G），若u的閉鄰域是一個(gè)團(tuán)，則稱u為圖G的一個(gè)極點(diǎn).我們記Ext（G）為G中的極點(diǎn)集，顯然Ext（G）必須包含在G的任一測(cè)地集中，從而｜Ext（G）｜≤g（G）.若圖G滿足｜Ext（G）｜＝g（G），則稱G為極點(diǎn)測(cè)地圖（extreme geodesic graph）.為了方便，將所有的極點(diǎn)測(cè)地圖構(gòu)成的集合記為Γ.這類圖被G.Chartrand，P.Zhang等人在文獻(xiàn)［2］中提到和研究.

下面介紹圖的一種積運(yùn)算：也稱為圖G，H的強(qiáng)積圖［3］，記為G?H，它的頂點(diǎn)集為：

并滿足兩頂點(diǎn)（u1，v1），（u2，v2）（ui∈V（G），vj∈V（H）；i，j＝1，2）在G?H鄰接當(dāng)且僅當(dāng)

（1）u1＝u2且v1，v2在H中鄰接，或

（2）v1＝v2且u1，u2在G中鄰接，或

（3）u1，u2在G中鄰接且v1，v2在H中鄰接.

在本文中，我們主要研究一類特殊的圖即極點(diǎn)測(cè)地圖（extreme geodesic graph）的結(jié)構(gòu)，給出兩個(gè)極點(diǎn)測(cè)地圖的強(qiáng)積圖的測(cè)地?cái)?shù)，由此推出任意兩個(gè)樹的強(qiáng)積圖的測(cè)地?cái)?shù).

1 預(yù)備知識(shí)

這一節(jié)，我們介紹一些測(cè)地?cái)?shù)的相關(guān)結(jié)果和強(qiáng)積圖的測(cè)地集的一些性質(zhì).

引理1［1］圖G的極點(diǎn)屬于G的任一個(gè)測(cè)地集.特別地，度為1的點(diǎn)屬于G的任一個(gè)測(cè)地集.

引理2［3］設(shè)圖G1，G2為連通圖，且（u，v），（u′，v′）為G1?G2中的任意兩頂點(diǎn)，則有：

2 主要結(jié)果

我們首先研究?jī)蓸O點(diǎn)測(cè)地圖G1，G2的強(qiáng)積圖G1?G2的測(cè)地?cái)?shù)，然后給出它的一些應(yīng)用.

定理3 設(shè)G1，G2∈Γ且｜G1｜，｜G2｜≥2.m1，m2分別為G1，G2的極點(diǎn)數(shù)，分別記：

為對(duì)應(yīng)于G1，G2中的極點(diǎn)集.則有：

（1）（e1i，e2j）（i＝1，2，…，m1；j＝1，2，…，m2）為G1?G2的極點(diǎn).

（2）g（G1?G2）＝m1×m2，且S＝｛（e1i，e2j）｜（i＝1，2，…，m1；j＝1，2，…，m2）｝為G1?G2的最小測(cè)地集.

證明 （1）考慮G1?G2中的頂點(diǎn)（e1i，e2j），因?yàn)閑1i，e2j分別為G1，G2中的極點(diǎn)，不妨設(shè)e1i，e2j在G1，G2中的鄰居分別為u1，…，up；v1，…，vq（p，q≥1）.則（e1i，e2j）在G1?G2中的鄰居為三類點(diǎn)：（e1i，vt），（us，e2j），（us，vt）（s＝1，…，p；t＝1，…，q）.由強(qiáng)積圖的定義，這三類點(diǎn)中任兩個(gè)點(diǎn)都鄰接.所以（e1i，e2j）為G1?G2中的極點(diǎn).

（2）由（1）和引理1的結(jié)果，可知g（G1?G2）≥m1×m2＝｜S1×S2｜＝｜S｜，下面我們證明S為G1?G2的一個(gè)測(cè)地集.為此，只需證明G1?G2中的任意頂點(diǎn)x，都位于某條端點(diǎn)在S中的測(cè)地線上.分四種情形討論：

（a）存在某個(gè)1≤i≤m1，1≤j≤m2使得：x＝（e1i，e2j），這時(shí)有x∈S，結(jié)論顯然成立；

（b）存在某個(gè)1≤i≤m1使得：x＝（e1i，v），其中v∈V（G2）＼｛e21，e22，…，e2m2｝，這時(shí)v在G2中必位于某條以G2中兩極點(diǎn)為端點(diǎn)的測(cè)地線上，不妨設(shè)位于e2s－e2t（1≤s≠t≤m2）測(cè)地線上.結(jié)合引理2有：

又由v位于e2s－e2t（1≤s≠t≤m2）測(cè)地線上，我們可以得到：

即x位于（e1i，e2s）－（e1i，e2t）測(cè)地線上.

（c）存在某個(gè)1≤j≤m2使得：x＝（u，e2j），其中u∈V（G1）＼｛e11，e12，…，e1m1｝.類似（b）可證.

（d）x＝ （u，v），u∈V（G1）＼｛e11，e12，…，e1m1｝，v∈V（G2）＼｛e21，e22，…，e2m2｝.我們考慮G1中所有過u點(diǎn)且端點(diǎn)均為極點(diǎn)的測(cè)地線族，記S′1為這個(gè)測(cè)地線族的所有端點(diǎn)的并，顯然S′1?S1.類似地記G2中對(duì)應(yīng)的集合S′2.令

不失一般性，設(shè)對(duì)某個(gè)1≤i≤m1，有dG1（u，e1i）＝p.G2中存在e2s，e2t∈S′2，使得v位于e2s－e2t測(cè)地線上.下證x位于（e1i，e2s）－（e1i，e2t）測(cè)地線上.

結(jié)合引理2與r的最小性，得：

又由于v位于e2s－e2t測(cè)地線上，我們可以得到：

則x位于（e1i，e2s）－（e1i，e2t）測(cè)地線上.結(jié)合四種情形，結(jié)論得證.

定理4［4］設(shè)樹T有m個(gè)葉子l1，l2，…，lm，則g（T）＝m且｛l1，l2，…，lm｝為它的最小測(cè)地集.

推論5 設(shè)T1，T2為階數(shù)不小于2的樹，m1，m2分別為T1，T2的葉子數(shù)，則g（T1?T2）＝m1m2.

證明 結(jié)合引理1和定理4可知T1，T2∈Γ，極點(diǎn)數(shù)分別為m1，m2，由定理3可得結(jié)論.

［1］G..Chartrand，P.Zhang，The geodetic number of an oriented graph［J］，European J Combin，2000（21）：181－189.

［2］G.Chartrand，P.Zhang，Extreme geodesic graphs［J］，Czechoslovak Mathematical Journal，2002（52）：771－780.

［3］W.Imrich，S.Klavzar.Product graphs：Structure and Recognition［M］，Wiley－Interscience，New York，2000.

［4］M.Farber，R.E.Jamison.Convexity in graphs and hypergraphs［J］，SIAM J.Algorithn Disc Math.1986（7）：433－444.

［5］呂長(zhǎng)虹.圖和有向圖的測(cè)地?cái)?shù)［J］.中國(guó)科學(xué) A輯.2007（37）：579－586.

The Geodesic Number of Strong Product Graphs

Wang Bing1，2，Lu Changhong1，Zhang Mei2
（1.Department of Mathematics，East China Normal University，Shanghai 200062，China；2.Department of Mathematics，Chuzhou University，Chuzhou 239000，China）

It is known that（V（G），d）is a metric space on a graph G，where geodesic number is an important parameter.A strong product graph is obtained from two graphs by aproduct operation.This paper obtains the geodesic numbers of strong product of two extreme geodesic graphs.As a corollary，the geodesic number of strong product of two trees is given.

geodesic number；strong product graphs

O157

：A

：1673－1794（2010）05－0016－02

王 兵（1982－），男，華東師范大學(xué)在職研究生，研究方向：圖論。

安徽省教育廳自然科學(xué)研究項(xiàng)目（kj2009B002）

2010－11－12