王 兵，呂長虹，張 梅

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

一類積圖的測地數(shù)

王 兵1，2，呂長虹1，張 梅2

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

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

測地數(shù)；強積圖

0 引言

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

下面介紹圖的一種積運算：也稱為圖G，H的強積圖［3］，記為G?H，它的頂點集為：

并滿足兩頂點（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中鄰接.

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

1 預(yù)備知識

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

引理1［1］圖G的極點屬于G的任一個測地集.特別地，度為1的點屬于G的任一個測地集.

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

2 主要結(jié)果

我們首先研究兩極點測地圖G1，G2的強積圖G1?G2的測地數(shù)，然后給出它的一些應(yīng)用.

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

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

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

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

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

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

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

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

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

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

（c）存在某個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點且端點均為極點的測地線族，記S′1為這個測地線族的所有端點的并，顯然S′1?S1.類似地記G2中對應(yīng)的集合S′2.令

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

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

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

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

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

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

證明 結(jié)合引理1和定理4可知T1，T2∈Γ，極點數(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］呂長虹.圖和有向圖的測地數(shù)［J］.中國科學(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é)研究項目（kj2009B002）

2010－11－12