丁超

(安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽安慶 246133)

距離模式識別圖的判定

丁超

(安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽安慶 246133)

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

距離模式識別集;距離模式識別數(shù);方格圖

1 引言

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

2 定義和引理

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

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

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

引理2.3[2]設(shè)圖為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]設(shè)Cn為n階圈,則Cn為距離模式識別圖的充分必要條件是n≥7.

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

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

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

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

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

3 主要結(jié)論

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

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

圖2

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

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

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

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

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

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

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

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

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

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

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

情形6n=6且m≥2.設(shè)

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

情形7n≥7且m≥2.設(shè)

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

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

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

證 設(shè)

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

情形1n為奇數(shù).在中對應(yīng)點(diǎn)v11,v12,···,v1n的行所形成的子矩陣記為D1,則D1為

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

情形2n為偶數(shù).在中對應(yīng)點(diǎn)v11,v12,···,v1n的行所形成的子矩陣記為D1,則D1為

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

4 算法

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

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

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

第三步求出M對應(yīng)的以及rM.

第四步計(jì)算距離模式識別率,當(dāng)μ(G)=1時,輸出所有距離模式識別集M,轉(zhuǎn)第五步.

第五步計(jì)算距離模式識別數(shù)ρ(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

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

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