正则图

维普资讯

南宁职业技术学院学报

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

ｏｏｏｏｏｏ

一

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

２００７

Ｖｏ１．１２

Ｎｏ．３

类偶阶奇正则图边优美性的构造

郑学谦

罗海鹏

黎贞崇

（１．广西师范学院数学与计算机科学系，广西南宁 ５３０００１；２．广西科学院，广西南宁 ５３０００３）

【摘要】通过研究一类偶阶奇正则图的构造，证明了４ｎ ２ｒ＋１）一正则图，当ｒ＞１时，不是

边优美图，当ｒ＝１时，则是边优美图并且是ｋ一边优美图。

【关键词】正则图；边优美图；ｋ一边优美图 【中图分类号】Ｏ１５７．５

【文献标识码】Ａ

【文章编号】１００９・３６２１（２００７）０３－００９６・０４

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

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

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

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

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

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

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

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

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

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

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

的边优美性是图论紫藤盆景 中一个较新的课题，其中许多问题尚待研究，即使是对某些特殊图给出其边优 美标号也是较困难的…。根据给出的一类奇阶偶正则图边优美性的构造，本文研究了一类偶阶奇

正则图边优美性的构造，并给出了４凡阶（２ｒ＋１）正则图当时ｒ＞１，不是边优美图，当ｒ＝１时，是

边优美图并且是ｋ一边优美图。

１．定义与引理

定义１１ 】对于一个简单图Ｇｒ

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

，ｌ ＶＩ＝ Ｉ Ｅｌ＝ｑ。若存在双射 ，１，２，…，ｇ 使得边导出映射

ｆ项目基金】国家自然科学基金（６０５６３００８）和广西自然科学基金（桂科自０７２８０５１）资助项目。

【作者简介】郑学谦（１９７９一），男，山西运城人，广西师范学院数学与计算机系２００５级组合数学专业硕士研究生，主要从事组合数学研究。

罗海鹏（１９４７一），男，广东东莞人，广西科学院研究员，主要从事组合数学与算法研究。

ｏ

维普资讯

郑学谦罗海鹏黎贞崇 一类偶阶奇正则图边优美性的构造

厂 ： 一｛０，１，２，…，Ｐ一１｝为双射，此一字的成语 处厂 定义Ｖ ∈Ｖ，“是与 相邻的顶点，厂 （ ）＝（ ／（“ ））

（ｏｒｏｄ Ｐ），则称Ｇ为边优美图，并称厂为Ｇ的边优美标号，厂 为厂导出的顶点标号。

定义２［ 】对给定的正整数ｋ，若存在双射

厂：Ｅ（Ｇ）一｛走，走十１，…走＋ｑ一１｝，使得边导出映射．厂 ：

．

一｛０，１，２…，Ｐ一１｝为双射，此处厂 定义为：Ｖ ∈Ｖ，“是与 相邻的顶点，厂 （ ）＝（

Ｐ），则称Ｇ为ｋ一边优美图，并称厂为Ｇ的ｋ一边优美标号， 为厂导出的顶点标号。

定义３［３］如果一个图中每个顶点 的度都是常数ｋ，则称该图为ｋ一正则图。

若图的顶点数是偶数，ｋ为奇数，则称为偶阶奇正则图。

（“ ））（ｍｏｄ

１

引理１Ｌ４］ 简单图Ｇ（Ｖ，Ｅ）中，Ｉ ＶＩ：Ｐ，Ｉ Ｅ Ｉ＝ｑ，图Ｇ是边优美图的必要条件是ｑ（ｑ＋１）＝寺ｐ（Ｐ

一

１）（ｍｏｄ ｐ）。

引理２［５］简单图Ｇ（ ，Ｅ）中ｆ ｆ＝Ｐ，ｆＥｆ＝口，若图Ｇ是边优美图， 转学理由

则（１）当Ｐ为奇数时，Ｐ ｆ ｇ（ｑ＋１）ｆ；

（２）当Ｐ为偶数时，ｐ￣Ｏ（ｒｎｏｄ ４）。

引理３ ］图Ｇ是正则图，若Ｇ是边优美的，那么也是ｋ一边优美的。

２．主要结果

２．１一类偶阶奇正则图边优美性的构造

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

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

ｉ＝１，２，…，７ｚ｝，那么ｃ 是２ 阶３一正则连通图。

设２ 忌２ 忌ｌ：７ｚ，则在ｃｉ ’的基础上定义图类ｃ ｚ 如下：

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

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

ｉ＝１，２，…，７ｚ｝，那么Ｃ （ｋ１，ｋ２）是２ｎ阶５一正则连通图

’）Ｕ｛７３ｉ ＋

ｆ

Ｅ（Ｃ

（

Ｃ２ ｎ

－

…，

。

一

般的可以构造更高度数的奇正则连通图ｃ ：’…一ｒ，其中２ ｋ， … ｋ２ ｋｌ＝ ，易知

ｃ５ ：’… ｒ’的顶点数ｐ：２ｎ；当时ｒ＝１，边数ｑ＝３ｎ；当ｒ＞１时，ｑ＝２ｎ＋２ｎ（２ｒ一１）且为（２ｒ＋１）一正

则图

２．２定理 对于４ｎ阶（２ｒ＋１）一正则图来说：

（１）当ｒ＞１时，不是边优美图；

（２）当ｒ：１时，是边优美图；

（３）当ｒ＝１时，是ｋ一边优美图。

证明：（１）由偶阶奇正则图的构造知，当ｒ＞１时，４ ７ｚ阶（２ｒ＋１）一正则图的边数Ｐ＝４ｎ＋４ｎ（２ｒ一

ｏｏｏｏｏｏ

１），顶点数为ｑ＝４ｎ。则

（ｐ＋１）一旦

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

＝８ｎｒ（８ｎｒ＋１）一２ｎ（４ｎ一１）＝８ｎｒ（８ｎｒ＋１学习英语的app 雅丹地貌形成过程 ）一８ ７＂／ ＋２ｎ，

显然不能被４ｎ整除，由引理１可知当ｒ＞１时，４ｎ阶（２ｒ＋１）正则图不是边优美图。

（２）当ｒ＝１时，对于４ 阶３一正则图分两种情况讨论：

（ｉ）当 ＝１时（如图１所示），令ｆ（ｅ１）＝１，厂（ ２）＝２，ｆ（ ３）＝３，ｆ（ ４）＝６，ｆ（ ５）＝５，ｆ（ ６）＝４．容

易证明厂是该４阶３一正则图的边优美标号。

（ｉｉ）当 ＞１时，４ 阶３一正则图顶点和边的顺序如图２所示，

ｏ

维普资讯

南宁职业技术学院学报

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

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

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

２００７ Ｖｏ１．１２

Ｎｏ．３

Ｉ— 、 “

、 Ｖ

１．

《

Ｖ

一一， Ｖ，．＋２

Ｖ２ １

图１ ４阶３一正则图

图２ ４ｎ阶３一正则图

顶点数Ｐ＝４ｎ，边数为ｑ＝６ｎ

给出如下边标号

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

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

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

ｆ（

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

ｆ（ ４ Ｖ１）＝３ｎ．

当 为奇数时，

ｆ（

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

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

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

ｆ（

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

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

当 为偶数时，

ｆ（

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

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

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

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

ｆ（

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

下面分两种情况讨论：

１。证明当 为奇数时，厂是４ 阶３一正则图的边优美标号。

首先可知，当 是奇数时厂是从４ 阶３一正则图的边到集合｛１，２，３，…，４ ｝的双射。

其次证明当 为奇数时，边导出映射厂 是从４ 阶３一正则图的顶点集到集合Ｉｏ，１，２，…，４ｎ一１｝的

双射。

给出４ 阶３一正则图的顶点标号如下：

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

厂 （ ２）＝５ｎ＋３（ｒｏｏｄ ４ｎ）三 参考面 ＋３（ｒｏｏｄ ４ｎ）

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

中ｉ＝３，４，…，

厂 （ ＋１）＝７ｎ＋３（ｒｏｏｄ ４ｎ）三团建活动策划 ３ ＋３（ｒｏｏｄ ４ｎ）

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

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

１

ｏ

维普资讯

郑学谦罗海鹏黎贞崇 一类偶阶奇正则图边优美性的构造

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

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

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

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

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

４，５，…， ＋１

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

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

…

，

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

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

显然顶点取遍０，１，２，…，４ｎ一１并且互不相同。所以由边导出映射厂 是茧子是怎么形成的 从４ 阶３一正则图的顶点

到集合｛０，１，２，…，４ｎ一１｝的双射。由边优美标号的定义得，当 为奇数时，４ 阶３一正则图是边优美图。

２。对于当 为偶数时，同理可证。

综上所述当ｒ＝１时，４ｎ阶３一正则图是边优美图。

（３）由以上证明可知，４ 阶３一正则图是边优美图。由引理３得，４ 阶３一正则图是ｋ一边优美图。

下面给出４ｎ阶３一正则图的一些边优美标号：

当 ＝２时，１ ２ ３ ４ ５ ７ ８ ６ １１ １０ １２ ９

当 ＝３时，１ ２ ３ ４ ５ ６ ７ １０ １１ １２ ８ ９ １６ １５ １８ １７ １３ １４

当 ＝４时，１ ２ ３ ４ ５ ６ ７ ８ ９ １３ １４ １５ １６ １０ １１ １２ １９ １８ ２０ ２２ ２４ １７ ２１ ２３

当 ＝５时，１ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １６ １７ １８ １９ ２０ １２ １３ １４ １５ ２６ ２５ ３０ ２９ ２８ ２７ ２１ ２４ ２３ ２２

［参考文献］

［１］孙慧泉．图论及其应用［Ｍ］．北京：科学出版社，２００４．

［２］ 温一慧．关于若边优美图的存在性［Ｊ］．兰州大学学报（自然科学版），２００５（１０）．

［３］ 刘晓姗．ＣｎｘＣｍ的ｋ一边优美的图标号［Ｊ］．江汉大学学报（自然科学版），２ＯＯ６（３）

［责任编辑：曾广春】

［责任校对：黄桂婵】

ｏｏｏｏｏｏ

ｏ