距離模式識別圖的判定

丁超

(安慶師范大學數學與計算科學學院,安徽安慶 246133)

距離模式識別圖的判定

丁超

(安慶師范大學數學與計算科學學院,安徽安慶 246133)

本文研究了幾類圖的距離模式識別性.利用構造法,求出了它們的距離模式識別集和距離模式識別數,提出距離模式識別率的概念,推廣了距離模式識別數的概念.

距離模式識別集;距離模式識別數;方格圖

1 引言

圖的距離模式識別集由Acharya在2006年向Germina提出,隨后Germina等人對此展開了研究,一些有意思的結論見文獻[1–8].圖的一個距離模式識別集是圖的一個自同構群,圖的每個頂點可由它與距離模式識別集的關系所唯一確定.圖可能存在距離模式識別集也可能不存在距離模式識別集,存在距離模式識別集的圖稱為距離模式識別圖,否則稱為非距離模式識別圖.圖G的距離模式識別集可能不唯一,階數最小的距離模式識別集的階數稱為圖的距離模式識別數(記為ρ(G)).如何判定圖的距離模式識別數是個有意思的問題.本文判定兩類非距離模式識圖,得到幾類圖的距離模式識別集和距離模式識別數,最后給出一個計算距離模式識別率的算法.

2 定義和引理

定義2.1[1]設v為圖G(V,E)的任意一個頂點,非空集合M?V(G),j為非負整數,記,稱集合fM(v)={d(u,v):u∈M}為v的M-距離模式.顯然,.如果是單射,那么稱M為G的距離模式識別集.記n×(dG+1)階矩陣為G的直徑),將中的非零元用1替換得矩陣

定義2.2設G1(V1,E1)和G2(V2,E2)為兩個簡單圖,它們的積圖G1×G2定義為

其中v1～v2表示v1與v2在G2中鄰接,u1～u2表示u1與u2在G1中鄰接,若G1和G2為兩條路,則它們的積圖為方格圖.

引理2.3[2]設圖為G(V,E),非空集合M?V(G),M為G的距離模式識別集的充分必要條件是的任意兩行互異.

例2.4圖1給出了兩個圖,其中G為距離模式識別圖,H為非距離模式識別圖.

圖1

在G中,令M={b,c,e},則

的任意兩行互異,所以M為G的距離模式識別集,即G為距離模式識別圖,且ρ(G)=3.H不存在距離模式識別集,即H為非距離模式識別圖.

引理2.5[2]設Cn為n階圈,則Cn為距離模式識別圖的充分必要條件是n≥7.

引理2.6[3]設G為距離模式識別圖,M為G的距離模式識別集.那么M的導出子圖G[M]是非連通的.

引理2.7[1](a)平凡圖K1是唯一的距離模式識別數為自身價數的圖.

(b)路是唯一的距離模式識別數為1的圖.

(c)不存在距離模式識別數為2的圖.

(d)若n≥7,則ρ(Cn)=3.

3 主要結論

定理3.1(a)設G為任意給定的圖,v為G的任一頂點,H1為G在點v粘三個懸掛點所得的圖,則H1為非距離模式識別圖.

(b)設樹T?如圖2所示,將T?粘到(在點v處)任一圖的任一頂點上得H2,則H2為非距離模式識別圖.

圖2

證(a)設粘到點v上的三個懸掛點分別為v1,v2,v3.假設H1有一個距離模式識別集M,對v1,v2,v3而言有以下兩種情形:

情形1v1,v2,v3中至少有兩個頂點屬于M.不失一般性,令v1,v2屬于M,那么在中對應于v1,v2的兩行相同,與M為距離模式識別集矛盾.

情形2v1,v2,v3中至少有兩個頂點不屬于M.不失一般性,令v1,v2屬于M,那么在

中對應于v1,v2的兩行也相同,與M為距離模式識別集矛盾.

(b)設樹T?的四個懸掛點分別為v1,v2,v3,v4.假設H2有一個距離模式識別集M,對v1,v2,v3,v4而言也有至少兩個頂點屬于M或者至少兩個頂點不屬于M的兩種情形,證明與(a)相同.所以結論成立.

定理3.2設Cn為n(n≥3)階圈,Pm為m(m≥2)階路,將Pm的一個懸掛點粘到Cn的一個頂點上得圖H.當m=2且n=3或者n=4時,H為非距離模式識別圖.其它情形H為距離模式識別圖,且ρ(H)=3.

證 情形1n=3且m=2.設C3=v1v2v3v1,P1=v1v4是粘到v1上的路.假設H有一個距離模式識別集M.由引理2.7知|M|≠1,2,4,那么M只能是{v2,v3,v4},但在中對應于v2,v3的兩行相同,與M為距離模式識別集矛盾,即H為非距離模式識別圖.

情形2n=3且m＞2.設C3=v1v2v3v1,Pm=v1v4v5···v2+m是粘到v1上的路.考察集合M={v1,v3,v5},則

情形3n=4且m=2.設C4=v1v2v3v4v1,P1=v1v5是粘到v1上的路.假設H有一個距離模式識別集M.由引理2.6和引理2.7知|M|≠1,2,4,5,那么M只能是{v1,v3,v5},{v3,v4,v5},{v2,v3,v5}和{v2,v4,v5}.容易驗證對應的中總有兩行相同,與M為距離模式識別集矛盾,即H為非距離模式識別圖.

情形4n=4且m＞2.設C4=v1v2v3v4v1,Pm=v1v5v6···v3+m是粘到v1上的路.考察集合M={v1,v2,v6},則

情形5n=5且m≥2.設C5=v1v2v3v4v5v1,Pm=v1v6v7···v4+m是粘到v1上的路.考察集合M={v1,v3,v6},則

情形6n=6且m≥2.設

是粘到v1上的路.考察集合M={v1,v3,v7},則

情形7n≥7且m≥2.設

由定理3.2的證明不難得出下面推論.

推論3.3設G為距離模式識別圖,Pm為m(≥2)階路,將Pm的一個懸掛點粘到G的一個頂點上得圖H,且dH=dG+m?1,則H為距離模式識別集,且ρ(H)=ρ(G).

定理3.4設Pm,Pn分別是m階和n階路,G=Pm×Pn是一個格子圖(m≥2,n≥4,n＞m),則G為距離模式識別圖,且ρ(G)=3.

證 設

如果M是G的一個距離模式識別集,則|M|≥3.考察集合M={v11,v12,v1n},有兩種情形.

情形1n為奇數.在中對應點v11,v12,···,v1n的行所形成的子矩陣記為D1,則D1為

D1中的任意兩行互異,記Di為中對應點vi1,vi2,···,vin的行所形成的子矩陣,則Di+1中的元素1的位置由Di中的元素1的位置向右移一個單位得到(i=1,2,···,m?1).所以的任意兩行互異,M為G的距離模式識別集,即G為距離模式識別圖,且ρ(G)=3.

情形2n為偶數.在中對應點v11,v12,···,v1n的行所形成的子矩陣記為D1,則D1為

后面的證明與情形1相同.所以結論成立.

4 算法

設圖G(V,E)為簡單圖,非空集合M?V(G),記rM為所有行構成的集合的階,稱為G的距離模式識別率,當μ(G)=1時G為距離模式識別圖,當μ(G)＜1時G為非距離模式識別圖.以下給出計算圖的距離模式識別率和距離模式識別數的算法:

第一步利用弗洛伊德算法計算G的距離矩陣D.

第二步求出G的所有n×k階子陣D′以及與D′對應的頂點集M(其中1≤k≤n且k≠2).

第三步求出M對應的以及rM.

第四步計算距離模式識別率,當μ(G)=1時,輸出所有距離模式識別集M,轉第五步.

第五步計算距離模式識別數ρ(G)=min|M|.

[1]Sona J,Germina K A.On the distance pattern distinguishing number of a graph[J/OL].J.Appl.Math.,Article ID 328703,8 pages,2014.

[2]Germina K A.Set-valuations of graphs and applications[R].Project Completion Report DST Grant-In-Aid Project No.SR/S4/277/05.Dpt.Sci.Tech.(DST),Government of India,2011.

[3]Germina K A,Joseph A.Some general results on distance pattern distinguishing graphs[J].Intern.J.Contem.Math.Sci.,2011,6(15):713–720.

[4]Chartrand G,Eroh L,Johnson M A,Oellermann O R.Resolvability in graphs and the metric dimension of a graph[J].Disc.Appl.Math.,2000,105(3):99–113.

[5]Khuller S,Raghavachari B,Rosenfeld A.Landmarks in graphs[J].Disc.Appl.Math.,1996,70(3):217–229.

[6]Germina K A,Joseph A,Sona J.Distance neighbourhood pattern matrices[J].Euro.J.Pure Appl.Math.,2010,3(4):748–764.

[7]Germina K A.Distance-Patterns of vertices in a graph[J].Intern.Math.Forum,2010,5(34):1697–1704.

[8]Chartrand G,Poisson C,Zhang P.Resolvability and the upper dimension of graphs[J].Comp.Math.Appl.,2000,39(12):19–28.

DETERMINATION OF DISTANCE PATTERN DISTINGUISHING GRAPHS

DING Chao
(School of Mathematics and Computational Science,Anqing Normal University,Anqing 246133,China)

In this paper,some classes of graphs are studied on distance pattern distinguishing.By the method of structuring,their distance pattern distinguishing sets and the distance pattern distinguishing numbers are given.The concept of distance pattern distinguishing rate is proposed,which extends the concept of distance pattern distinguishing number.

distance pattern distinguishing graph;distance pattern distinguishing number;grid

05C12

O157.5

A

0255-7797(2017)06-1220-07

2016-07-16接收日期:2016-10-31

安徽省高等學校自然科學基金資助(KJ2013186).

丁超(1979–),男,安徽蕪湖,講師,主要研究方向:圖論.