一類r-(d0,d1,…,dt-1)-泛圈圖的結(jié)果

張耀靜

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建漳州363000；2.數(shù)字福建氣象大數(shù)據(jù)研究所,福建 漳州363000）

若n階簡單圖G中長為t(3≤t≤n)的圈恰好有1 個(gè)，則稱圖G為唯一泛圈圖.1973年，Entringer[1]提出確定唯一泛圈圖的問題.1986年shi[2]證明了在n個(gè)頂點(diǎn)的哈密頓圖中G，若所有唯一泛圈圖的邊數(shù)為v+m(m≤3)，那么它們只有7 個(gè)，而且當(dāng)邊數(shù)為v+4 時(shí)，唯一泛圈圖不存在，在這個(gè)基礎(chǔ)上他提出猜想當(dāng)圖的邊數(shù)為v+m(m≥4)時(shí)，唯一泛圈圖不存在[2].2009年，Markstr?m[3]證明了唯一泛圈圖的邊數(shù)的新上下界，而且還通過計(jì)算機(jī)查找證實(shí)施的猜想對(duì)點(diǎn)數(shù)較小的圖是正確的：當(dāng)階小于或等于59 時(shí)邊數(shù)v+m(m≥4)的唯一泛圈圖不存在.2015年，Phillips 等[4]運(yùn)用計(jì)算機(jī)發(fā)現(xiàn)了所有32 階唯一偶泛圈.2016年，Wallis[5]證明了所有階數(shù)小于30的唯一偶泛圈圖.與唯一偶泛圈圖的相關(guān)結(jié)果可以在文獻(xiàn)[3,6-8]中查看.與Entringer問題相關(guān)的結(jié)果可以在文獻(xiàn)[9-12]中查看.

若n階簡單圖G中長為t(r≤t≤n)的圈恰好有k個(gè)，則稱圖G為r-(k)-泛圈圖.2013年，Zamfirescu[13]研究了一類(2)-泛圈圖并擴(kuò)展到r-(2)-泛圈圖，給出了r-(2)-泛圈圖的定義以及構(gòu)造的方法.2018年Liu[14]根據(jù)Zamfirescu[13]構(gòu)造了一類r-(k)-泛圈圖，并證明了r與n的關(guān)系.

1975年，Erd?s[1]提出確定f(n)的問題，其中f(n)是表示沒有等長圈n階圖的最大可能邊數(shù).顯然可以看出Erd?s問題和Entringer問題都沒有等長圈.相關(guān)結(jié)果可以在文獻(xiàn)[15-22]中查看.

若對(duì)每一個(gè)r+tj+i(r+tj+i≤n)，n階簡單圖G中長為r+tj+i的圈恰好有di個(gè)，0≤i≤t?1，其中t是di的周期數(shù)，j是t重復(fù)的次數(shù)，則稱圖G為r?(d0,…,dt?1)-泛圈圖.若對(duì)每一個(gè)奇（偶）數(shù)r+tj+i(r+tj+i≤n)，n階簡單圖G中長為r+tj+i的圈恰好有di個(gè)，0≤i≤t?1，其中t是di的周期數(shù)，j是t重復(fù)的次數(shù)，則稱圖G為r?(d0,…,dt?1)-奇（偶）泛圈圖.2015年陳錦麗[23]構(gòu)造了一類r?(P0,P1,…,Pt?1)-泛圈圖.本文主要構(gòu)造了r?(6?2μ1,6?2μ1,8?2μ1,6?2μ1)-泛圈圖，r?(6?2μ1,8?2μ1,6?2μ1,6?2μ1)-奇（偶）泛圈圖.

1 主要結(jié)果

約定簡單圖G都是n階哈密頓圖,其中Cn=v1v2…vivi+1…vjvj+1…vnv1是n階哈密頓圈.稱在E(G)?E(Cn)內(nèi)部區(qū)域添加的邊為弦.若一對(duì)弦在Cn的內(nèi)部是形如vavc與vbvd的形式,則稱該對(duì)弦為交錯(cuò)弦，其中頂點(diǎn)va,vc,vb,vd不一定相鄰.稱vivj與vi+1vj+1(1≤i,j≤n)為一對(duì)纏繞弦(如圖1所示).經(jīng)過vivj,vi+1vj+1和Cn的某些邊可以得到一個(gè)與Cn等長的不同圈.

圖1 泛圈圖的纏繞弦與交錯(cuò)弦Fig.1 The interwined and staggered chord of pancyclic graph

定理1設(shè)u=u1+2，u1∈N，n≥12，λ≥6，若2λ?u?1+λ?2≤n<2λ?u+λ?1且n?r(n,λ,μ)+1 ≡s(mod4)，s=0,1,2,3，那么存在一個(gè)n階r?(6?2u1,6?2u1,8?2u1,6?2u1)-泛圈圖，其中

證明(構(gòu) 造法)考 慮在Cn內(nèi)部添加弦:c1=v1v3，c2=v2v4，c3=v2v6，c4=v4v7，c5=v5v8，…，c2i=v2i1+2i?2v2i+2i?1，c2i+1=v2i?1+2i?1v2i+2i，其中i=2，…，u，c2u+2=v2u+2uv2u+1+2u+1，…，cλ=v2λ?u?2+2λ?2u?4v2λ?u?1+2λ?2u?3，重復(fù)這種操作，直到在Cn內(nèi)部不能添加弦為止，允許cλ與v1關(guān)聯(lián)，易知c1，c2跳過1個(gè)頂點(diǎn)，c3跳過3個(gè)頂點(diǎn)，當(dāng)4≤j≤2u+1時(shí)，cj跳過個(gè)頂點(diǎn)，當(dāng)2u+2≤j≤λ時(shí)，cj跳過2j?u?2個(gè)頂點(diǎn).如圖2.

圖2 r-(6·2μ1,6·2μ1,8·2μ1,6·2μ1)-泛圈圖Fig.2 The r-(6·2μ1,6·2μ1,8·2μ1,6·2μ1)-pancyclic graph

若cλ與v1關(guān)聯(lián)，則

若cλ的最后的一個(gè)端點(diǎn)與v1之間有2λ?u?1?1個(gè)頂點(diǎn)，則

因此2λ?u?1+λ?2≤n<2λ?u+λ?1.

設(shè)Ψ 是圖G的所有圈的集合.對(duì)于任一條弦，圖G中恰有兩個(gè)長度不等的圈僅過該弦，設(shè)Ψ0表示為G中長度較短圈及由u對(duì)纏繞弦產(chǎn)生的所有4圈的集合，設(shè)N為這些圈的長度的集合，

設(shè)S∈ΨΨ0，那么S必定有一條按照順時(shí)針方向從v1到v2u+2u的路.由于在構(gòu)造弦的時(shí)候，除了有u對(duì)纏繞弦，還增加一些交錯(cuò)弦：f1=c1c3c4，f2=c1c3c4c5，f3=c1c2c3，f4=c1c2c3c5，f5=c3c4c5，f6=c3c4，f7=c1c3c5，f8=c1c3，f9=c3c5，其中它們跳過的頂點(diǎn)數(shù)分別為0，0，1，1，1，1，2，2，3.

①只考慮經(jīng)過纏繞弦產(chǎn)生的與S等長圈的個(gè)數(shù)，其中c3?E(S).對(duì)任意的vivj，vi+1vj+1∈E(S)，若vivj∈E(S)，vi+1vj+1?E(S)(vi+1vj+1∈E(S),vivj?E(S))，那么有S'=S?vivj?vjvj+1+vivi+1+vi+1vj+1(S'=S?vivi+1?vi+1vj+1+vivj+vjvj+1)，若vivj，vi+1vj+1∈E(S)(vivj∈E(S),vi+1vj+1?E(S))，則有S'=S?vivj?vi+1vj+1+vivi+1+vjvj+1(S=S'?vivi+1?vjvj+1+vivj+vi+1vj+1)，從而可知過一對(duì)纏繞弦可以產(chǎn)生一個(gè)與S等長的不同圈S'.對(duì)剩下的u?1 對(duì)纏繞弦類似討論可得與S等長的圈個(gè).

②考慮經(jīng)過纏繞弦以及交錯(cuò)弦產(chǎn)生的與S1等長圈的個(gè)數(shù)，其中纏繞弦vivj，vi+1vj+1∈E(S1)，8≤i

③經(jīng)過c3與u?2對(duì)纏繞弦產(chǎn)生的與S2等長圈的個(gè)數(shù).與①一樣進(jìn)行類似討論得到經(jīng)過c3與u?2對(duì)纏繞弦產(chǎn)生的與S2等長圈的個(gè)數(shù)為

設(shè)m∈N是ΨΨ0中圈不經(jīng)過Cn的頂點(diǎn)的數(shù)目，m可以表示成a1?20+a2?21+…+aλ?u?12λ?u?2，其中ai=0或1，i=1,…,λ?u?1.因?yàn)閏1，c2跳過1個(gè)頂點(diǎn)，c3跳過3個(gè)頂點(diǎn)，cj(4≤j≤2u+1)跳過頂點(diǎn)數(shù)為跳過頂點(diǎn)數(shù)為2j?u?2，所以0≤m≤2λ?u?1?1.設(shè)M是ΨΨ0中圈的圈長之集，那么M={n?2λ?u?1+1,…,n?2,n?1,n}，從而所有的圈長之集為M∪N.

考慮r(n,λ,μ)滿足r(n,λ,μ)≥minM，r(n,λ,μ)>maxN，顯然有

若12≤n≤15，則r(n,λ,μ)=9.

若15

若n>3?2λ?u?2+2，則r(n,λ,μ)=minM=n?2λ?u?1+1.

因?yàn)樵赟中等長圈的數(shù)目是以4 為周期，按照6?2u1,6?2u1,8?2u1,6?2u1的形式重復(fù)出現(xiàn)的，所以n?r+1 ≡0(mod4)，有n?r(n,λ,μ)+1+s≡0(mod4)，即n?r(n,λ,μ)+1 ≡s(mod4)，s=0,1,2,3.從 而 設(shè)u=u1+2，u1∈N，n≥12，λ≥6，若2λ?u?1+λ?2≤n<2λ?u+λ?1且n?r(n,λ,μ)+1 ≡s(mod4)，s=0,1,2,3，那么存在一個(gè)n階r?(6?2u1,6?2u1,8?2u1,6?2u1)-泛圈圖，其中

證畢.

定理2設(shè)u=u1+2，u1∈N，n≥11，λ≥5，若2λ?u+λ?3≤n<2λ?u+1+λ?2 且n?r(n,λ,μ)+1 ≡s(mod8)，s=0,2,4,6，那么

1)若n=2m,m∈N?，則存在n階r?(6?2u1,8?2u1,6?2u1,6?2u1)-偶泛圈圖，其中

2)若n=2m+1,m∈N?，則存在n階r?(6?2u1,8?2u1,6?2u1,6?2u1)-奇泛圈圖，其中

證明(構(gòu)造法)考慮在Cn內(nèi)部添加弦:c1=v1v4，c2=v2v5，c3=v3v10，c4=v5v10，c5=v6v11，…，c2i=v2i+2i?3v2i+1+2i?2，c2i+1=v2i+2i?2v2i+1+2i?1(i=2,…,μ)，c2u+2=v2u+1+2u?1v2u+2+2u，…，cλ=v2λ?u?1+2λ?2u?5v2λ?u+2λ?2u?4，重復(fù)這種操作，直到在Cn內(nèi)部不能添加弦為止，允許cλ與v1關(guān)聯(lián)，易知c1，c2跳過2 個(gè)頂點(diǎn)，c3跳過6 個(gè)頂點(diǎn)，當(dāng)4≤j≤2u+1時(shí)，cj跳過個(gè)頂點(diǎn)，當(dāng)2u+2≤j≤λ時(shí)，cj跳過2j?u?1個(gè)頂點(diǎn).如圖3所示.

圖3 r-(6·2μ1,8·2μ1,8·2μ1,6·2μ1)-泛圈圖Fig.3 The r-(6·2μ1,8·2μ1,8·2μ1,6·2μ1)-pancyclic graph

若cλ與v1關(guān)聯(lián)，則

若cλ的最后的一個(gè)端點(diǎn)與v1之間有2λ?u?1個(gè)頂點(diǎn)，則

因此2λ?u+λ?3≤n<2λ?u+1+λ?2.

設(shè)Ψ 是圖G的所有圈的集合.對(duì)于任一條弦，圖G中恰有兩個(gè)長度不等的圈僅過該弦，設(shè)Ψ0表示為G中長度較短圈及由u對(duì)纏繞弦產(chǎn)生的所有4圈的集合，設(shè)N為這些圈的長度的集合，

設(shè)S∈ΨΨ0，那么S必定有一條按照順時(shí)針方向從v1到v2u+1+2u?1的路.由于在構(gòu)造弦的時(shí)候，除了有u對(duì)纏繞弦，還增加一些交錯(cuò)弦：f1=c2c3c5，f2=c1c2c3c5，f3=c1c3c5，f4=c3c5，f5=c2c3，f6=c1c2c3，f7=c3c4c5，f8=c1c3c4c5f9=c1c3，其中它們跳過的頂點(diǎn)數(shù)分別為0，0，2，2，4，4，4，4，6.

①只考慮經(jīng)過纏繞弦產(chǎn)生的與S等長圈的個(gè)數(shù)，其中c3?E(S).對(duì)任意的vivj，vi+1vj+1∈E(S)，若vivj∈E(S)，vi+1vj+1?E(S)(vi+1vj+1∈E(S),vivj?E(S))，那么有S'=S?vivj?vjvj+1+vivi+1+vi+1vj+1(S'=S?vivi+1?vi+1vj+1+vivj+vjvj+1)，若vivj，vi+1vj+1∈E(S)(vivj∈E(S),vi+1vj+1?E(S))，則有S'=S?vivj?vi+1vj+1+vivi+1+vjvj+1(S'=S?vivi+1?vjvj+1+vivj+vi+1vj+1)，從而可知進(jìn)過一對(duì)纏繞弦可以產(chǎn)生一個(gè)與S等長的不同圈S'，對(duì)剩下的u?1 纏繞弦類似討論可得與S等長的圈有個(gè).

②考慮經(jīng)過纏繞弦以及交錯(cuò)弦產(chǎn)生的與S1等長圈的個(gè)數(shù)，其中纏繞弦vivj，vi+1vj+1∈E(S1)，8≤i

③經(jīng)過c3與u?2對(duì)纏繞弦產(chǎn)生的與S2等長圈的個(gè)數(shù)，與①一樣進(jìn)行類似討論得到經(jīng)過c3與u?2對(duì)纏繞弦產(chǎn)生的與S2等長圈的個(gè)數(shù)為

設(shè)m∈N是ΨΨ0中圈不經(jīng)過Cn的頂點(diǎn)的數(shù)目，m可以表示成a1?21+a2?22+…+aλ?u?12λ?u?1，其中ai=0或1，i=1,…,λ?u?1.因?yàn)閏1，c2跳過2個(gè)頂點(diǎn)，c3跳過6個(gè)頂點(diǎn)，cj(4≤j≤2u+1)跳過頂點(diǎn)數(shù)為，cj(2u+2≤j≤λ)跳過頂點(diǎn)數(shù)為2j?u?1，所以0≤m≤2λ?u?2.設(shè)M是ΨΨ0中圈的圈長之集，那么M={n?2λ?u+2,…,n?2,n}，從而所有的圈長之集為M∪N.

考慮r(n,λ,μ)滿足r(n,λ,μ)≥minM，r(n,λ,μ)>maxN，顯然有

1)當(dāng)n=2m,m∈N?時(shí)，

若20≤n≤3?2λ?u?1+2，則r(n,λ,μ)=2λ?u?1+4.

若n>3?2λ?u?1+2，則r(n,λ,μ)=n?2λ?u+2.

2)當(dāng)n=2m+1,m∈N?時(shí)，r(n,λ,μ)=n?2λ?u+2.

又因?yàn)樵赟中相等圈的數(shù)目是以4為周期，按照6?2u1,8?2u1,6?2u1,6?2u1的形式重復(fù)出現(xiàn)，即以4為周期，且在圖3中所得的每個(gè)圈的長度是以2 為公差的等差數(shù)列，因此n?r+2 ≡0(mod8)，故有n?r(n,λ,μ)+2+s≡0(mod8)，即n?r(n,λ,μ)+2 ≡s(mod8)，s=0,2,4,6.設(shè)u=u1+2，u1∈N，n≥11，λ≥5，若2λ?u+λ?3≤n<2λ?u+1+λ?2且n?r(n,λ,μ)+2 ≡s(mod8)，s=0,2,4,6，那么

1)若n=2m,m∈N?，則存在n階r?(6?2u1,8?2u1,6?2u1,6?2u1)-偶泛圈圖，其中

2)若n=2m+1,m∈N?，則存在n階r?(6?2u1,8?2u1,6?2u1,6?2u1)-奇泛圈圖，其中

證畢.