3-方体的一个性质

2024年3月9日发(作者：万圣节是哪一天)

维普资讯

第２５卷第３期　

重庆工商大学学报（自然科学版）　

２００８年６月　

Ｖｏ１．２５　Ｎｏ．３　

Ｊ　Ｃｈｏｎｇｑｉｎｇ　Ｔｅｅｈｎｏｌ　Ｂｕｓｉｎｅｓｓ　Ｕｎｉｖ．（Ｎａｔ　Ｓｃｉ　Ｅｄ）　

Ｊｕｎ．２００８　

文章编号：１６７２—０５８Ｘ（２００８）０３—０２２９—０４　

３一方体的一个性质　

王斌　

（重庆工商大学数学与统计学院，重庆４０００６７）　

摘要：在相关文献中，引入了　一子图的概念来探索超欧拉图的极大欧拉生成子图的边　

数，并且证明了２一方体在加入一条新边的情况下是一个　一子图．研究了３一方体，证明了３一　

方体在加入一条新边的情况下是一个音一子图．

Ｕ　

关键词：超欧拉图；欧拉生成子图；　一子图；３一方体　

中图分类号：Ｏ　１５７．５　文献标识码：Ａ　

所涉及的图都是有限无环（１ｏｏｐｌｅｓｓ）图．未经定义的术语和符号参见文献［Ｉ］．设Ｇ是一个图，Ｖ（Ｇ）　

表示该图的顶点集合，Ｅ（Ｇ）表示该图的边集合，ｄ（＇３／）表示顶点＇／３在图中的度数．在Ｇ上添加边集Ｅ　（Ｅ　ｎ　

Ｅ（Ｇ）＝　）所得到的图记为Ｇ＋Ｅ　．特别地，如果Ｅ　＝｛ｅ｝，则简记为Ｇ＋ｅ．从图Ｇ去掉它的边集的一个　

子集　所得到的图记为Ｇ—Ｅ　．假定日是图Ｇ的一个子图，记为日　Ｇ．如果　（日）＝　（Ｇ），称日为图Ｇ　

的一个生成子图．令Ｏ（Ｇ）＝｛＇／３∈Ｖ（Ｇ）Ｉ　ｄ（＇／３）为奇数｝，即图Ｇ的奇顶点集合．图Ｇ称为欧拉图（ｅｕｌｅｒｉａｎ　

ｇｒａｐｈ），如果图Ｇ是连通的，并且Ｏ（Ｇ）＝　．图Ｇ称为超欧拉图（ｓｕｐｅｒｅｕｌｅｆｉａｎ　ｇｒａｐｈ）．如果Ｇ含有一个　

欧拉生成子图（ｓｐａｎｎｉｎｇ　ｅｕｌｅｒｉａｎ　ｓｕｂｇｒａｐｈ）．全体超欧拉图简记为ＳＬ，即ＳＬ＝｛超欧拉图｝．　

寻找超欧拉图的极大（边数最多）欧拉生成子图的边数，是一个有趣的问题．１９９５年，赖虹健、陈志宏　

提出如下问题：　

问题ｌ　设　＝ｒａ

ｉ

ｎ　ｍａ

。　乩

ＩＩＬｘ

￣　１日是Ｇ的欧拉生成子图），试决定厶　

Ｐ．Ａ．Ｃａｔｌｉｎ曾猜想Ｌ≥－５　－．文献［２］否定了这个猜想，指出应该有：Ｌ≥÷，并提出如下问题：　

问题２　求简单图Ｇ，使得Ｌ＝毒　

目前，问题１、问题２都是尚未解决的公开问题．在文献［３］中，作者提出了一个新的方法，其核心是引　

入　一子图的概念来探索超欧拉图的极大欧拉生成子图的边数．设　是Ｇ的子图，Ｇ／Ｘ≠Ｋ　．令Ｌ　＝ｒａｉｎ　

ｍａｘ

｛　ｌ　Ｋ是Ｇ／　的欧拉生成子图）．所谓的　一子图的定义如下：　

定义１【３　设Ｇ是超欧拉图，　是Ｇ的子图，Ｇ／Ｘ≠Ｋ　，　为给定的常数．若由Ｌ　≥　可推出Ｌ≥　，　

则称子图　是Ｇ的一个　一子图．　

由该定义，容易得到如下命题：　

命题１　设Ｇ是超欧拉图，　是Ｇ的　一子图，Ｇ／Ｘ≠Ｋ　，　为给定的常数．若Ｇ／Ｘ含有欧拉生成子图　

Ｋ满足ｌＥ（Ｋ）ｌ≥　ｌＥ（Ｇ／Ｘ）ｌ，那么Ｇ含有欧拉生成子图日，满足ｌＥ（日）ｌ≥　ｌＥ（Ｇ）１．　

由此可见，利用　一子图的概念可以简化上述的公开问题１，因为通常而言Ｇ／Ｘ比图Ｇ的边数要少，从　

收稿日期：２００８—０２—２２；修回日期：２００８—０３－２８．　

基金项目：重庆市自然科学基金（ＣＳＣＴ．２００７ＢＡ２００４）及重庆市教委项目资助（ＫＪ０７０７０１０）．　

作者简介：王斌（１９７４一），男，四川省德阳市人，硕士，讲师，从事图论研究．　

维普资讯

２３０　重庆工商大学学报（自然科学版）　第２５卷　

而问题１就较为简单一些．文献［３］还得到了以下定理：　

定理１　设Ｑ是一个２一方体，那么Ｑ＋ｅ是　３

一

子图．　

在此基础上，研究了３一方体，得到了如下结果：　

定理２　设Ｑ是一个３一方体，那么Ｑ＋ｅ是　一子图．　

１　准　备　

设日　Ｇ，图Ｇ关于子图日的收缩定义为：在Ｇ中，把日用一个新的点（通常记为　）来替换，原来Ｇ　

中与日关联的边，使其与新的点　关联，其余的边不变．这样得到的图称为Ｇ关于日的收缩，记为Ｇ／Ｈ．图　

Ｇ称为可折叠子图（ｃｏｌｌａｐｓｉｂｌｅ），如果对于任意含有偶数个顶点的子集Ｒ　ｃ　（Ｇ），Ｇ都有一个连通的生成　

子图日满足Ｄ（日）＝Ｒ．用收缩法来判断图的超欧拉性，有以下著名的结果：　

定理３【４　设日是图Ｇ的可折叠子图，则Ｇ是超欧拉图当且仅当Ｇ／Ｈ是超欧拉图．　

因为欧拉图的收缩仍然是欧拉图，所以有下面的结论：　

定理４　设日是图Ｇ的子图，Ｇ是超欧拉图，则Ｇ／日是超欧拉图．　

所谓ｋ一方体（ｋ—ｃｕｂｅ）是指这样的图，它的顶点是０和１组成的有序ｋ元组，两个顶点相邻当且仅　

当它们恰有一个坐标不同．４一圈　就是一个２一方体通常的立方体的顶点和边组成的图就是这里所谓　

的３一方体（３一ｃｕｂｅ）．由定义容易看出ｋ一方体具有很好的对称性．关于ｋ一方体，有如下的定理：　

定理５…ｋ一方体是有２　个顶点，ｋ×２　条边的ｋ正则图．其中ｋ≥２为正整数．　

２　主要结果及其证明　

定理２　设Ｑ是一个３一方体，那么Ｑ＋ｅ是　一子图．　

１Ｊ　

证明　设Ｑ是一个３一方体，为了叙述的方便，不妨标记Ｖ（Ｑ）　

＝

｛１，２，３，４，１　，２　，３　，４　｝，顶点的连接情况如图１．由３一方体的对１　

称性，不妨取ｅ＝（１，４）．根据ｏｌ一子图的定义，假定图Ｇ是一个超欧　

拉图．Ｘ＝Ｑ＋ｅ　Ｇ，并且Ｇ／Ｘ有一个欧拉生成子图日，使得　

０　，　

ｌ　Ｅ（日）ｌ／ｌ　Ｅ（Ｇ／Ｘ）ｌ≥南　

为了证明图Ｇ有欧拉生成子图Ｍ，使得ｌ　Ｅ（Ｍ）ｌ≥素Ｉｑ　　Ｅ（Ｇ）ｌ・　

－１￣Ｉ　Ｅ（Ｘ）ｌ・　

图　１　

以下先证明，对于　中任意偶数个顶点的集合Ａ，　含有连通的生成子图　使得０（Ｋ）＝Ａ，并且ｌＥ（Ｋ）ｌ≥　

情形１　Ａ＝ｆ２ｊ．令Ｋ＝Ｘ一（２，２　）一（１　，３　）一（４，４　）一（４，３），则Ｏ（Ｋ）＝Ａ，Ｋ是　的连通生成　

子图，并且ｌＥ（Ｋ）ｌ≥素ｌＥ（　）ｌ・　

情形２　ＩＡ　Ｉ＝２．由ｋ一方体的对称性，在去掉重复情况后如表１．　

维普资讯

第３期　王斌：３一方体的一个性质‘　

表１　情形２　

令Ｋ＝　—Ｅ　，则Ｄ（Ｋ）＝Ａ，Ｋ是　的连通生成子图，并且Ｉ　（Ｋ）Ｉ≥　Ｉ　Ｅ（　）Ｉ．　

情形３　ＩＡｌ＝４．由ｋ一方体的对称性，在去掉重复情况后如表２。　

表２　情形３　

令Ｋ＝　—Ｅ’，则Ｄ（Ｋ）＝Ａ，Ｋ是　的连通生成子图，并且Ｉ　Ｅ（Ｋ）Ｉ≥若Ｉ　Ｅ（　）Ｉ．　

情形４　ｌＡ　ｌ＝６．由ｋ一方体的对称性，在去掉重复情况后如表３。　

２３１　

维普资讯

２３２　重庆工商大学学报（咱然科学版）　第２５卷　

表３　情形４　

令　＝　—Ｅ　，则Ｄ（　）＝Ａ，Ｋ是Ｘ的连通生成子图，并且ｌ　Ｅ（Ｋ）ｌ≥云ｌ　Ｅ（Ｘ）１．　

情形５　Ａ＝Ｖ（Ｘ）．取Ｅ　＝｛（１，４）｝，令Ｋ＝Ｘ—Ｅ　，则０（Ｋ）＝Ａ，Ｋ是　的连通生成子图，并且　

０　

ｌ　Ｅ（　）ｌ≥云ｌ　Ｅ（Ｘ）１．　

令Ｗ＝Ｇ［Ｅ（Ｈ）］表示Ｇ／Ｘ中欧拉生成子图日在Ｇ中的导出子图．令Ａ＝０（　，则Ａ　ｏ（ｘ），并且是偶　

顶点集．由前述情形１至隋形５可知，无论在何种隋况下，只要令Ｍ＝Ｗ　ｕ　Ｋ，都可以得到　是图Ｇ的欧拉生成　

子图，并且Ｉ　Ｅ（　）Ｉ＝Ｉ　Ｅ（Ｗ）Ｉ＋Ｉ　Ｅ（Ｋ）Ｉ≥苦Ｉ　Ｅ（Ｇ）Ｉ．从而Ｑ＋ｅ就是超欧拉图Ｇ的—个告一子图．证毕．　

参考文献：　

［１］ＢＯＮＤＹ　Ｊ　Ａ，ＭＵＲＴＹ　Ｕ　Ｓ　Ｒ．Ｇｒａｐｈ　Ｔｈｅｏｒｙ　ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．ＮｏｎＩＩ—Ｈｏｌｌａｎｄ，Ｎｅｗ　Ｙｏｒｋ，１９７６　

［２］ｕ　Ｄ　Ｘ，ｕ　Ｄ　Ｙ，ＭＡＯ　Ｊ　Ｚ．Ｍａｘｉｍｕｍ　ｎｕｍｂｅｒ　ｏｆｅｄｇｅｓ　ｉｎ　ｓｐａｎｎｉｎｇ　ｅｕｌｅｒｉｎａ　ｓｕｂｇｒａｐｈ［Ｊ］．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，２００４，２７４　

（１）：２９９—３０２　

［３］李登信．寻找欧拉生成子图最大边数的一个方法［Ｊ］．重庆工商大学学报：自然科学版，２００７，２４（３）：２１５—２１７　

［４］ＣＡＴＬＩＮ　Ｐ　Ａ．Ａ　ｒｅｄｕｃｔｉｏｎ　ｍｅｔｈｏｄ　ｔｏ　ｉｆｎｄ　ｓｐａｎｎｉｎｇ　ｅｕｌｅｒｉｎａ　ｓｕｂｇｒａｐｈｓ［Ｊ］．Ｊ．Ｇｒａｐｈ　Ｔｈｅｏｒｙ，１９８８，１２（１）：２９—４５　

Ａ　ｐｒｏｐｅｒｔｙ　ｏｆ　３——ｃｕｂｅ　

ＷＡＮＧ　Ｂｉｎ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｓｔａｔｉｓｔｉｃｓ，Ｃｈｏｎｇｑｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｂｕｓｉｎｅｓｓ　Ｕｎｉｖｅｒｓｉｔｙ，　

Ｃｈｏｎｇｑｉｎｇ　４０００６７，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｓｏｍｅ　ｒｅｆｅｒｅｎｃｅｓ．ｔｈｅ　ａｕｔｈｏｒ　ｈａｓ　ｉｎｔｒｏｄｕｃｅｄ　ａ　ｎｅｗ　ｃｏｎｃｅｐｔ　ｏｆ　一ｓｕｂｇｒａｐｈ　ｔｏ　ｅｘｐｌｏｒｅ　ｔｈｅ　ｎｕｍ—　

ｂｅｒ　ｏｆ　ｅｄｇｅｓ　ｏｆ　ｉｔｓ　ｍａｘｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｅｕｌｅｒｉａｎ　ｓｕｂｇｒａｐｈ　ｏｆ　ａ　ｓｕｐｅｒｅｕｌｅｒｉａｎ　ｇｒａｐｈ．Ｔｈｅ　ａｕｔｈｏｒ　ａｌｓｏ　ｐｒｏｖｅｄ　ａ　２一　

ｃｕｂｅ　ａｄｄｅｄ　ｗｉｔｈ　ａ　ｎｅｗ　ｅｄｇｅ　ｉｓ　ａ　一ｓｕｂｇｒａｐｈ．Ｉｎ　ｔ｝ｌｉｓ　ｐａｐｅｒ

，

３一ｃｕｂｅ　ｈａｓ　ｂｅｅｎ　ｓｔｕｄｉｅｄ　ａｎｄ　ａ　ｐｒ０ｐｅｒｔｙ。ｆ　ｉｔ　ｔ｝ｌａｔ　

３一ｃｕｂｅ　ａｄｄｅｄ　ｗｉｔｈ　ａ　ｎｅｗ　ｅｄｇｅ　ｉｓ　西９

一

ｓｕｂｇｒａｐｈ　ｈａｓ　ｂｅｅｎ　ｆ０ｕｎｄ．　

Ｋｅｙｗｏｒｄｓ：ｓｕｐｅｒｅｕｌｅｒｉａｎ　ｇｒａｐｈｓ；ｍａｘｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｅｕｌｅｒｉａｎ　ｓｕｂｇｒａｐｈ；　一ｓｕｂｇｒａｐｈ；３一ｃｕｂｅ　

责任编辑：李翠薇