摘 要：圖[G]的標(biāo)號(hào)是定義在[VG]或[EG]或[VG∪EG]上的具有特定性質(zhì)的映射。研究圖的各種特殊的標(biāo)號(hào)是當(dāng)前圖論中的一個(gè)熱點(diǎn)研究方向。該文討論有向圖的距離幻標(biāo)號(hào)，證明了兩個(gè)長(zhǎng)度分別為[m和 n]的有向圈的卡氏積是距離幻圖當(dāng)且僅當(dāng)[m， n形如N， 2N， 2N， N]或[2N， 2N]，其中N是奇數(shù)，并且此時(shí)該圖的任一距離幻標(biāo)號(hào)的幻常數(shù)必為0。

關(guān)鍵詞：距離幻標(biāo)號(hào)；距離幻圖；幻常數(shù)；有向圈；圖的卡氏積

中圖分類號(hào)：O157.5 文獻(xiàn)標(biāo)識(shí)碼：A

0" " 引言

判定一個(gè)簡(jiǎn)單無(wú)向圖是否為距離幻圖是圖論中的一個(gè)經(jīng)典問(wèn)題。Arumugam等［1］證明，距離幻圖的任何兩個(gè)幻標(biāo)號(hào)的幻常數(shù)都相等。Cichacz等［2］給出了一類4度循環(huán)圖是距離幻圖的充分條件，并提出如何刻畫(huà)4度循環(huán)圖何時(shí)是距離幻圖。Miklavi?等用特征和的技術(shù)給出了連通4度循環(huán)圖是距離幻圖的一個(gè)充分必要條件［3］；接著又將方法推廣到6度循環(huán)圖上，得到了一大類6度循環(huán)圖是距離幻圖的充分必要條件［4］；他們還考慮了Hamming圖上的群距離幻標(biāo)號(hào)，利用線性代數(shù)的工具得到了一類Hamming圖是距離幻圖［5］。Anholcer等［6］證明兩個(gè)長(zhǎng)度分別為m，n的圈的直積是距離幻圖當(dāng)且僅當(dāng)m = 4或n = 4或m ≡ n ≡ 0（mod 4）。Cichacz［7］給出了一類超圈是距離幻圖的充分條件，并且證明了在某些限制下這個(gè)條件也是必要的。Rao等［8］證明，兩個(gè)長(zhǎng)度分別為[m和 n]的圈的卡氏積是距離幻圖當(dāng)且僅當(dāng)[m， n]形如[N， 2N， 2N， N]或[2N， 2N]，其中N是奇數(shù)。

有向圖[G]與[H]的卡氏積，記作[G□H]，是以集合[VG×VH]為頂點(diǎn)集的有向圖，圖中從頂點(diǎn)[g1， h1]到頂點(diǎn)[g2， h2]有邊當(dāng)且僅當(dāng)[g1=g2]且[h1h2∈EH]，或[g1g2∈EG]且[h1=h2]。

含有[n]個(gè)頂點(diǎn)的有向圈記為[Cn]。本文證明了如下結(jié)果。

定理1 對(duì)[m， n≥3]，[Cm□Cn]是距離幻圖當(dāng)且僅當(dāng)[m， n]形如[N， 2N， 2N， N]或[2N， 2N]，其中[N]是奇整，并且此時(shí)[G]的任一個(gè)距離幻標(biāo)號(hào)的幻常數(shù)必為0。

1" " 定理1的必要性

以下取定整數(shù)[m， n≥3]，并總設(shè)[l和d]分別為m與n的最小公倍數(shù)和最大公因數(shù)。由圖的卡氏積的定義，集合V（[Cm□Cn]）等同于集合[?×?]關(guān)于如下等價(jià)關(guān)系的商集：

[i， j]所在的等價(jià)類仍記為[i， j]。由定義，圖[Cm□Cn]中從頂點(diǎn)[i， j]到[i'， j']有邊當(dāng)且僅當(dāng)[i=i']且[j'-j≡1mod n]，或[j=j']且[i'-i≡1mod m]。對(duì)[0≤k≤d-1]，記

[Dk? i， j ：j-i=k， 0≤i， j≤l-1]，

在初等數(shù)論中熟知，對(duì)任意整數(shù)[a， b]，同余方程組

有解當(dāng)且僅當(dāng)[d （a-b）]，且此時(shí)該方程組的任何兩個(gè)解都模[l]同余。特別地，當(dāng)[a=-2k，b=2k]時(shí)，該方程組有解當(dāng)且僅當(dāng)[d 4k]。

引理2 設(shè)k是滿足[d 4k]的最小正整數(shù)，t是同余方程組

的一個(gè)解，則

定理1的必要性的證明 設(shè)[φ ： VCm□Cn→1， mn]是一個(gè)距離幻標(biāo)號(hào)，其幻常數(shù)為c。令[xi，j=φi， j]，[ yi，j=xi，j-xi+1，j+1]，并記

我們先證明如下兩個(gè)事實(shí)：

（i） 對(duì)任意整數(shù)[i， j， ]序列[yi+k，j+kk∈?]以[d']為周期；" " （ii） [2" l" d']。

對(duì)于（i） ，由于[φ]是距離幻標(biāo)號(hào)，所以對(duì)任意[i，" j]都有

將上式中的[i 和 j]分別替換為[i-1 和 j+1]，得[yi-1， j+yi， j-1=yi-2， j+1+yi-1， j]，故有[yi， j-1=yi-2， j+1]。由歸納易知，對(duì)任意[k]都有

[yi， j=yi-2k， j+2k。]" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "（1）

再證明（ii） 。由（i），對(duì)任意整數(shù)[i， j， k]有

取[t]滿足[t≡-dmod m， t≡dmod n。]這樣有[yi-1， j+1=yi-d， j+d=yi+t， j+t]，從而

[c=yi， j+yi-1， j+1=yi， j+yi+t， j+t。]" " " " " " " " " " " " " " " " " " " " " " （2）

因[l]是奇數(shù)，由[d']的取法知此時(shí)[d'=d]。又由于[dt]，由（i）知[yi+t， j+t=yi， j]。結(jié)合式（2）得

[c=yi， j+yi+t， j+t=2yi， j]。

由（ii）可知

當(dāng)[l=d]時(shí)有[m=n=d≡2mod 4]；當(dāng)[l=2d]時(shí)有（m，n） = （d，2d）或（2d，d），其中d是奇數(shù)。

最后證明[c=0]。令[V=VCmCn]。對(duì)任意[v∈V]，令

2" " 定理1的充分性

對(duì)于整數(shù)[a， b]，記[[a， b]?" k∈Z ：a≤k≤b 。]

引理3 設(shè)[n]是奇數(shù)，令[Vi=r， s∈VC2n□C2n s-r≡imod 2， i=0， 1]。如果存在滿射[φ0 ：V0→1， 2n2]和整數(shù)[c]，使得對(duì)任意[v∈V1]有

則[C2nC2n]是距離幻圖。

證明 定義映射[φ ： V→1， 4n2]為

先證[φ]是雙射。對(duì)任意[N∈2n2+1， 4n2]，因[φ0]是滿射，存在[r， s∈V0]使得[φ0r， s=N-2n2]，故有

[φr-1， s=φ0r， s+2n2=N-2n2+2n2=N]。

所以[φ]是滿射。又因?yàn)閇V=1， 4n2=4n2]，所以[φ]是雙射。令[zi，j=φi， j]，由[φ]的定義，對(duì)任意[i， j∈V1]有

[zi， j-zi+1， j+1=zi+1， j+2n2-zi+2， j+1+2n2=zi+1， j-zi+2， j+1]。

然后取任意[v=r， s∈V0]，令[ω=r+1， s∈V1]，有

定理1的充分性的證明 由對(duì)稱性，只需證明[C2n□C2n]和[C2n□Cn]都是距離幻圖。

易知

進(jìn)而[φD2i=]" [2in+1， 2i+1n]，故

所以[φ]是滿的。又由于[V0=1， 2n2=2n2]，所以[φ]是雙射。注意到對(duì)任意整數(shù)i， j，其中[0≤i≤n-1]，有[-i+j， i+j=-i+j1， i+j1]，其中[j1]是[j]的模[2n]最小非負(fù)剩余。由[φ]的定義可得

它僅與[i]的奇偶性和[j]模[2n]的剩余有關(guān)。

[N+v=-i-1+j， i+j+1， -i+j， i+j]，" [N-v=-i+j， i+j+2， -i+j+1， i+j+1]，

并且[-i+j， i+j， -i+j+1， i+j+1∈D2i]，而

所以當(dāng)[i≤n-2]時(shí)，[x-i-1+j， i+j+1-x-i+j， i+j+2]與[x-i+j，i+j-x-i+j+1， i+j+1]相差一個(gè)符號(hào)；而當(dāng)[i=n-1]時(shí)，有

[-n+j， n+j，-n+j+1， n+j+1=n+j， n+j， n+j+1， n+j+1?D0]，

此時(shí)由φ的定義，[x-n+j， n+j-x-n+j+1， n+j+1=xn+j， n+j-xn+j+1， n+j+1]與[x-n-1+j，n-1+j-x-n-1+j+1，n-1+j+1]相差一個(gè)符號(hào)，故總有

進(jìn)而由引理3知[C2n□C2n]是距離幻圖。

再討論[C2n□Cn]。由初等數(shù)論知識(shí)，對(duì)任意[r， s∈V]，存在唯一的整數(shù)[0≤i≤n-1]和[0≤j≤2n-1]使得[r≡-i+jmod 2n， s≡i+jmod n。]定義標(biāo)號(hào)[φ ： V→1， 2n2]如下：

容易驗(yàn)證[φDk=2kn+1， 2kn+2n]，從而

這表明[φ]是滿射。結(jié)合[V=1， 2n2=2n2]，便知[φ]是雙射。

取定[v0=r， s+1∈V]，令[v=r， s， ω=r-1， s+1]，則存在唯一的[0≤iv≤n-1]和[0≤jv≤2n-1]使得[r≡-iv+jvmod 2n， s≡iv+jvmod n。]由[φ]的定義得

由于[r-1≡-iv-1+jvmod 2n， s+1≡iv+1+jvmod n，]故當(dāng)[iv≤n-2]時(shí)有[iω=iv+1，" jω=jv]，此時(shí)由式（3）可得

[xr-1， s+1-xr， s+2=-xr， s-xr+1， s+1]。

而當(dāng)[iv=n-1]時(shí)有

此時(shí)[iω=0]，且

同樣由式（3）可得

故總有

這表明[φ]是一個(gè)幻常數(shù)為0的距離幻標(biāo)號(hào)。證畢。

3" "結(jié)束語(yǔ)

無(wú)向圖的標(biāo)號(hào)是圖論研究的一個(gè)新熱點(diǎn)。距離幻標(biāo)號(hào)是幻標(biāo)號(hào)的一種重要類型，對(duì)于給定的圖，一個(gè)基本問(wèn)題是判斷它是否存在距離幻標(biāo)號(hào)。目前對(duì)完全二部圖、路、圈、樹(shù)、奇價(jià)的正則圖以及它們的一些乘積圖，該問(wèn)題都已有了明確的答案。

本文研究的有向圖的距離幻標(biāo)號(hào)是無(wú)向圖的距離幻標(biāo)號(hào)的自然推廣。從本文所得結(jié)果來(lái)看，一個(gè)圖的對(duì)稱性越好，它存在距離幻標(biāo)號(hào)的可能性越大。在此基礎(chǔ)上，我們可以對(duì)一些重要類型的有向圖，如正則圖、Cayley圖、頂點(diǎn)傳遞圖等，考慮其距離幻標(biāo)號(hào)的存在性。

參考文獻(xiàn)：

［1］ ARUMUGAM S， FRONCEK D， KAMATCHI N. Distance magic graphs—a survey［J］. Journal of Indones mathematical society， 2011：11-26.

［2］ CICHACZ S， FRONCEK D.Distance magic circulant graph［J］. Discrete mathematics， 2016， 339（1）：84-94.

［3］ MIKLAVI? ?， ?PARL P.Classification of tetravalent distance magic circulant graphs［J］. Discrete mathematics，2021，344（11）： 112557.

［4］ MIKLAVI? ?， ?PARL P.On distance magic circulants of valency 6［J］. Discrete applied mathematics， 2023， 329：35-48.

［5］ MIKLAVI? ?，?PARL P.On distance magic labelings of Hamming graphs and folded hypercubes［J］. Discussiones mathematicae graph theory， 2024， 44（1）：17-33.

［6］ ANHOLCER M，CICHACZ S，PETERIN I，et al.Distance magic labeling and two products of graphs［J］. Graphs and combinatorics， 2015， 31（5）：1125-1136.

［7］ CICHACZ S， Distance magic （r， t）-hypercycles［J］. Utilitas mathematica， 2016， 101：283-294.

［8］ RAO S B，SINGH T，PARAMESWARAN V.Some sigma labeled graphs： I，Graphs，combinatorics，algorithms and applications［M］. New Delhi：Narosa Publishing House，2004：125-133.