正則圖

維普資訊

南寧職業技術學院學報

Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｎｉｎｇ Ｐｏｌｙｔｅｃｈｎｉｃ

ｏｏｏｏｏｏ

一

２００７年第１２卷第３期

２００７

Ｖｏ１．１２

Ｎｏ．３

類偶階奇正則圖邊優美性的構造

鄭學謙

羅海鵬

黎貞崇

（１．廣西師范學院數學與計算機科學系，廣西南寧 ５３０００１；２．廣西科學院，廣西南寧 ５３０００３）

【摘要】通過研究一類偶階奇正則圖的構造，證明了４ｎ ２ｒ＋１）一正則圖，當ｒ＞１時，不是

邊優美圖，當ｒ＝１時，則是邊優美圖并且是ｋ一邊優美圖。

【關鍵詞】正則圖；邊優美圖；ｋ一邊優美圖 【中圖分類號】Ｏ１５７．５

【文獻標識碼】Ａ

【文章編號】１００９?３６２１（２００７）０３－００９６?０４

Ｏｎ ｔｈｅ Ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ Ｅｄｇｅ——ｇｒａｃｅｆｕｌｎｅｓｓ ｏｆ Ａ Ｋｉｎｄ

ｏｆ Ｅｖｅｎ——ｏｒｄｅｒ Ｏｄｄ Ｒｅｇｕｌａｒ Ｇｒａｐｈｓ

ＺＨＥＮＧ Ｘｕｅ—ｑｉａｎ ＬＵＯ Ｈａｉ—ｐｅｎｇ２ ＬＩ Ｚｈｅｎ—ｃｈｏｎｇ２

（１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ＆Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｇｕａｎｇｘｉ Ｔｅａｃｈｅｒｓ’Ｃｏｌｌｅｇｅ，

Ｎａｎｎｉｎｇ ５３０００１，Ｇａｎｇｘｉ，責任擔當作文素材 Ｃｈｉｎａ；２．Ｇｕａｎｇｘｉ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，

Ｎａｎｎｉｎｇ ５３０００３，Ｇｕａｎｇｘｉ，Ｃｈｉｎａ）

【Ａｂｓｔｒａｃｔ］Ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ，ｒｅｇｕｌａｒ ｇｒａｐｈｓ ｏｆ ｏｒｄｅｒ ４ｎ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｄ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ

ｓｔｕｄｙ ｏｎ ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｅｄｇｅ—－ｇｒａｃｅｆｕｌｎｅｓｓ ｏｆ ａ ｋｉｎｄ ｏｆ ｅｖｅｎ—－ｏｒｄｅｒ ｏｄｄ ｒｅｇｕｌａｒ

ｇｒａｐｈｓ．Ｗｈｅｎ ｒ＞１，ｉｔ ｉｓｎ’ｔ ｅｄｇｅ—ｇｒａｃｅｆｕｌ ｇｒａｐｈ．Ｗｈｅｎ ｒ＝１，ｉｔ ｉｓ ｅｄｇｅ—ｇｒａｃｅｆｕｌ

ｇｒａｐｈ ａｓ ｗｅｌｌ ａｓ ｋ—ｅｄｇｅ－－ｇｒａｃｅｆｕｌ ｇｒａｐｈ．

【Ｋｅｙ ｗｏｒｄｓ］ｒｅｇｕｌａｒ ｇｒａｐｈｓ；ｅｄｇｅ—ｇｒａｃｅｆｕｌ ｇｒａｐｈ；ｋ—ｅｄｇｅ—ｇｒａｃｅｆｕｌ ｇｒａｐｈ

的邊優美性是圖論紫藤盆景 中一個較新的課題，其中許多問題尚待研究，即使是對某些特殊圖給出其邊優 美標號也是較困難的…。根據給出的一類奇階偶正則圖邊優美性的構造，本文研究了一類偶階奇

正則圖邊優美性的構造，并給出了４凡階（２ｒ＋１）正則圖當時ｒ＞１，不是邊優美圖，當ｒ＝１時，是

邊優美圖并且是ｋ一邊優美圖。

１．定義與引理

定義１１ 】對于一個簡單圖Ｇｒ

【收稿日期Ｊ ２００７—０５—２６

，ｌ ＶＩ＝ Ｉ Ｅｌ＝ｑ。若存在雙射 ，１，２，…，ｇ 使得邊導出映射

ｆ項目基金】國家自然科學基金（６０５６３００８）和廣西自然科學基金（桂科自０７２８０５１）資助項目。

【作者簡介】鄭學謙（１９７９一），男，山西運城人，廣西師范學院數學與計算機系２００５級組合數學專業碩士研究生，主要從事組合數學研究。

羅海鵬（１９４７一），男，廣東東莞人，廣西科學院研究員，主要從事組合數學與算法研究。

ｏ

維普資訊

鄭學謙羅海鵬黎貞崇 一類偶階奇正則圖邊優美性的構造

廠 ： 一｛０，１，２，…，Ｐ一１｝為雙射，此一字的成語 處廠 定義Ｖ ∈Ｖ，“是與 相鄰的頂點，廠 （ ）＝（ ／（“ ））

（ｏｒｏｄ Ｐ），則稱Ｇ為邊優美圖，并稱廠為Ｇ的邊優美標號，廠 為廠導出的頂點標號。

定義２［ 】對給定的正整數ｋ，若存在雙射

廠：Ｅ（Ｇ）一｛走，走十１，…走＋ｑ一１｝，使得邊導出映射．廠 ：

．

一｛０，１，２…，Ｐ一１｝為雙射，此處廠 定義為：Ｖ ∈Ｖ，“是與 相鄰的頂點，廠 （ ）＝（

Ｐ），則稱Ｇ為ｋ一邊優美圖，并稱廠為Ｇ的ｋ一邊優美標號， 為廠導出的頂點標號。

定義３［３］如果一個圖中每個頂點 的度都是常數ｋ，則稱該圖為ｋ一正則圖。

若圖的頂點數是偶數，ｋ為奇數，則稱為偶階奇正則圖。

（“ ））（ｍｏｄ

１

引理１Ｌ４］ 簡單圖Ｇ（Ｖ，Ｅ）中，Ｉ ＶＩ：Ｐ，Ｉ Ｅ Ｉ＝ｑ，圖Ｇ是邊優美圖的必要條件是ｑ（ｑ＋１）＝寺ｐ（Ｐ

一

１）（ｍｏｄ ｐ）。

引理２［５］簡單圖Ｇ（ ，Ｅ）中ｆ ｆ＝Ｐ，ｆＥｆ＝口，若圖Ｇ是邊優美圖， 轉學理由

則（１）當Ｐ為奇數時，Ｐ ｆ ｇ（ｑ＋１）ｆ；

（２）當Ｐ為偶數時，ｐ￣Ｏ（ｒｎｏｄ ４）。

引理３ ］圖Ｇ是正則圖，若Ｇ是邊優美的，那么也是ｋ一邊優美的。

２．主要結果

２．１一類偶階奇正則圖邊優美性的構造

對于偶圈Ｃ２ ， （Ｃ２ ）＝｛７３ｌ，７３２，…， ２ ｝，Ｅ（Ｃ２ ）：｛＂Ｏｉ＇Ｏ ＋ｌ ｆ ｉ＝１，２．…，２ｎ一１｝Ｕ｛￣０＂２ｎ＂０ｌ｝

令ｃ５ （ｋ＝ ）表示如下圖類，Ｖ（ｃ５ ）＝Ｖ（Ｃ２ ）＝｛ ｌ， ２，…， ２ ｝，Ｅ（ｃ５ ）＝Ｅ（Ｃ２ ）Ｕ｛ＺｌｉＺＩ ＋ ｆ

ｉ＝１，２，…，７ｚ｝，那么ｃ 是２ 階３一正則連通圖。

設２ 忌２ 忌ｌ：７ｚ，則在ｃｉ ’的基礎上定義圖類ｃ ｚ 如下：

Ｖ（Ｃ （ｋ ’ ２ ）＝Ｖ（ｃ５ ’）：Ｖ（Ｃ２ ）＝｛ ｌ， ２，…， ２ ｝

ｋ１，ｋ２））＝Ｐ ｋ，１ｔ

ｉ＝１，２，…，７ｚ｝，那么Ｃ （ｋ１，ｋ２）是２ｎ階５一正則連通圖

’）Ｕ｛７３ｉ ＋

ｆ

Ｅ（Ｃ

（

Ｃ２ ｎ

－

…，

。

一

般的可以構造更高度數的奇正則連通圖ｃ ：’…一ｒ，其中２ ｋ， … ｋ２ ｋｌ＝ ，易知

ｃ５ ：’… ｒ’的頂點數ｐ：２ｎ；當時ｒ＝１，邊數ｑ＝３ｎ；當ｒ＞１時，ｑ＝２ｎ＋２ｎ（２ｒ一１）且為（２ｒ＋１）一正

則圖

２．２定理 對于４ｎ階（２ｒ＋１）一正則圖來說：

（１）當ｒ＞１時，不是邊優美圖；

（２）當ｒ：１時，是邊優美圖；

（３）當ｒ＝１時，是ｋ一邊優美圖。

證明：（１）由偶階奇正則圖的構造知，當ｒ＞１時，４ ７ｚ階（２ｒ＋１）一正則圖的邊數Ｐ＝４ｎ＋４ｎ（２ｒ一

ｏｏｏｏｏｏ

１），頂點數為ｑ＝４ｎ。則

（ｐ＋１）一旦

：｝［４ ７ｚ＋４ ７ｚ（２ｒ一１）］［４ ７ｚ＋４ｎ（２ｒ一１）＋１］｝一生絲

＝８ｎｒ（８ｎｒ＋１）一２ｎ（４ｎ一１）＝８ｎｒ（８ｎｒ＋１學習英語的app 雅丹地貌形成過程 ）一８ ７＂／ ＋２ｎ，

顯然不能被４ｎ整除，由引理１可知當ｒ＞１時，４ｎ階（２ｒ＋１）正則圖不是邊優美圖。

（２）當ｒ＝１時，對于４ 階３一正則圖分兩種情況討論：

（ｉ）當 ＝１時（如圖１所示），令ｆ（ｅ１）＝１，廠（ ２）＝２，ｆ（ ３）＝３，ｆ（ ４）＝６，ｆ（ ５）＝５，ｆ（ ６）＝４．容

易證明廠是該４階３一正則圖的邊優美標號。

（ｉｉ）當 ＞１時，４ 階３一正則圖頂點和邊的順序如圖２所示，

ｏ

維普資訊

南寧職業技術學院學報

２００７年第１２卷第３期

Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｎｉｏｏｏｏｏｏ

ｎｇ Ｐｏｌｙｔｅｃｈｎｉｃ

２００７ Ｖｏ１．１２

Ｎｏ．３

Ｉ— 、 “

、 Ｖ

１．

《

Ｖ

一一， Ｖ，．＋２

Ｖ２ １

圖１ ４階３一正則圖

圖２ ４ｎ階３一正則圖

頂點數Ｐ＝４ｎ，邊數為ｑ＝６ｎ

給出如下邊標號

ｆ（ＶｉＶ ＋１）＝ｉ，ｉ＝１，２，…，２ ＋１，

ｆ（Ｖ２ｎ＋２Ｖ２ｎ＋３）＝３ｎ＋１，

ｆ（ ｆ＋１）＝ｉ＋ 一１，ｉ＝２ｎ香菇瘦肉粥 ＋３，２ ＋４，…，３ ＋１，

ｆ（

＋１）＝ｉ一 ，ｉ＝３ｎ＋２，３ ＋３，…，４ｎ一１，

ｆ（ ４ Ｖ１）＝３ｎ．

當 為奇數時，

ｆ（

＋２ ）＝５ｎ＋２一ｉ，ｉ＝１，２

ｆ（ ｆ＋２ ）＝６ｎ—ｉ＋３，ｉ＝３，４，…， ＋１

ｆ（ ＋２ ＋２＋２ ）＝４ｎ＋１

ｆ（

＋２ ）＝６ｎ—ｉ＋２ ｉ＝ ＋３， ＋４，…，２ｎ一１

ｆ（Ｖ２ Ｖ２ ＋２ ）＝４ｎ＋２

當 為偶數時，

ｆ（

＋２ ）＝４ｎ＋４一ｉ，ｉ＝１，２

ｆ（ ｆ＋２ ）＝４ｎ＋２ 一２，ｉ＝３，４，…， ＋１

ｆ（ ｎ＋２ ｎ＋２＋２ｎ）＝４ｎ＋１

ｆ（ ＋２ ）＝６ｎ＋４一ｉ，ｉ＝ ＋３， ＋５，…，２ｎ一１

ｆ（

＋２ ）＝７ｎ—ｉ＋３，ｉ＝ ＋４， ＋６，…，２

下面分兩種情況討論：

１。證明當 為奇數時，廠是４ 階３一正則圖的邊優美標號。

首先可知，當 是奇數時廠是從４ 階３一正則圖的邊到集合｛１，２，３，…，４ ｝的雙射。

其次證明當 為奇數時，邊導出映射廠 是從４ 階３一正則圖的頂點集到集合Ｉｏ，１，２，…，４ｎ一１｝的

雙射。

給出４ 階３一正則圖的頂點標號如下：

廠 （ １）＝８ｎ＋２（ｒｏｏｄ ４ｎ）－－￣２（ｍｏｄ ４ｎ）

廠 （ ２）＝５ｎ＋３（ｒｏｏｄ ４ｎ）三 參考面 ＋３（ｒｏｏｄ ４ｎ）

廠 （ ）＝６ｎ＋ｉ＋２（ｒｏｏｄ ４ｎ）＝２ｎ＋５，２ｎ＋６，…，３ ＋２（ｏｒｏｄ ４ｎ），其

中ｉ＝３，４，…，

廠 （ ＋１）＝７ｎ＋３（ｒｏｏｄ ４ｎ）三團建活動策劃 ３ ＋３（ｒｏｏｄ ４ｎ）

廠 （ ＋２）＝６ｎ＋４（ｒｏｏｄ ４ｎ）三２ ＋４（ｒｏｏｄ ４ｎ）

ｆ＋（ ）＝６ｎ＋ｉ＋１（ｏｒｏｄ ４ｎ）＝３ｎ＋４，３ ＋５，…，４ｎ一１，Ｏ（ｍｏｄ ４ｎ），其中ｉ＝ ＋３， ＋４，…，２ 一

１

ｏ

維普資訊

鄭學謙羅海鵬黎貞崇 一類偶階奇正則圖邊優美性的構造

（ ２ ）＝８ｎ＋ｌ（ｍｏｄ ４ｎ）－－ｌ（ｍｏｄ ４ｎ）

（ ２ ＋１）＝９ｎ＋２（ｒｏｏｄ ４ｎ）－－ｎ＋２（ｒｏｏｄ ４ｎ）

（ ２ ＋２）＝ｌＯｎ＋２（ｒｏｏｄ ４ｎ）－－２ ＋２（ｒｏｏｄ ４ｎ）

（ ２ ＋３）＝１２ｎ＋３（ｒｏｏｄ ４ｎ）－－３（ｍｏｄ ４ｎ）

（ ｆ）＝８ｎ＋２ｉ—ｋ（ｒｏｏｄ ４ｎ）－－４，５，…， ， ＋ｌ（ｍｏｄ ４ｎ），其中ｉ＝２ｎ＋４，２ｎ＋５，…，２ ＋ｋ，ｋ＝

４，５，…， ＋１

（ ３ ＋２）＝ｌＯｎ＋３（ｒｏｏｄ ４ｎ）三２ ＋３（ｍｏｄ ４ｎ）

（ ｆ）＝４ｎ＋２ｉ—ｋ＋ｌ（ｍｏｄ ４ｎ）三 ＋４， ＋ｋ，…，２ｎ（ｒｏｏｄ ４ｎ），其中ｉ＝２ｎ＋ ＋３，２ｎ＋ ＋４，

…

，

２ｎ＋ｋ，ｋ＝ ＋３， ＋４，…，２ｎ一１

（＂０４ ）＝ｌＯｎ＋１（ｒｏｏｄ ４ｎ）－－２ ＋ｌ（ｍｏｄ ４ｎ）

顯然頂點取遍０，１，２，…，４ｎ一１并且互不相同。所以由邊導出映射廠 是繭子是怎么形成的 從４ 階３一正則圖的頂點

到集合｛０，１，２，…，４ｎ一１｝的雙射。由邊優美標號的定義得，當 為奇數時，４ 階３一正則圖是邊優美圖。

２。對于當 為偶數時，同理可證。

綜上所述當ｒ＝１時，４ｎ階３一正則圖是邊優美圖。

（３）由以上證明可知，４ 階３一正則圖是邊優美圖。由引理３得，４ 階３一正則圖是ｋ一邊優美圖。

下面給出４ｎ階３一正則圖的一些邊優美標號：

當 ＝２時，１ ２ ３ ４ ５ ７ ８ ６ １１ １０ １２ ９

當 ＝３時，１ ２ ３ ４ ５ ６ ７ １０ １１ １２ ８ ９ １６ １５ １８ １７ １３ １４

當 ＝４時，１ ２ ３ ４ ５ ６ ７ ８ ９ １３ １４ １５ １６ １０ １１ １２ １９ １８ ２０ ２２ ２４ １７ ２１ ２３

當 ＝５時，１ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １６ １７ １８ １９ ２０ １２ １３ １４ １５ ２６ ２５ ３０ ２９ ２８ ２７ ２１ ２４ ２３ ２２

［參考文獻］

［１］孫慧泉．圖論及其應用［Ｍ］．北京：科學出版社，２００４．

［２］ 溫一慧．關于若邊優美圖的存在性［Ｊ］．蘭州大學學報（自然科學版），２００５（１０）．

［３］ 劉曉姍．ＣｎｘＣｍ的ｋ一邊優美的圖標號［Ｊ］．江漢大學學報（自然科學版），２ＯＯ６（３）

［責任編輯：曾廣春】

［責任校對：黃桂嬋】

ｏｏｏｏｏｏ

ｏ