二部图的四圈覆盖.PDF

第１９卷第６期 江 苏 科 技 大 学 学 报（自然科学版） Ｖｏ１１９ Ｎｏ６ 　 ２００５年１２月 ＪｏｕｒｎａｌｏｆＪｉａｎｇｓｕＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）　 Ｄｅｃ．２００５ 　　　　　　 文章编号：１６７３－４８０７（２００５）０６－００３６－０５ 二部图的四圈覆盖 １ ２ 卞秋香 ，孙志人 （１．江苏科技大学 数理学院，江苏 镇江２１２００３；２．南京师范大学 数学与计算机科学学院，江苏 南京２１００９７） 摘　要：设ｋ是正整数，Ｇ＝（Ｖ，Ｖ；Ｅ）是一个二部图，满足｜Ｖ｜＝｜Ｖ｜ ２ｋ＋１，若对Ｇ中任意的 １ ２ １ ２ ≥ ８ 两个顶点ｘ Ｖ，ｙ Ｖ，都有ｄ（ｘ）＋ｄ（ｙ） ｋ，则Ｇ恰好被ｋ个独立的四圈所覆盖。 ∈ １ ∈ ２ ≥ ３ 关键词：平衡二部图；四圈；覆盖 中图分类号：Ｏ１５７．５　　　　　　　　文献标识码：Ａ ＣｏｖｅｒｉｎｇａＢｉｐａｒｔｉｔｅＧｒａｐｈｗｉｔｈＩｎｄｅｐｅｎｄｅｎｔＱｕａｄｒｉｌａｔｅｒａｌｓ １ ２ ＢＩＡＮＱｉｕｘｉａｎｇ，ＳＵＮＺｈｉｒｅｎ （１．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＰｈｙｓｉｃｓ，ＪｉａｎｇｓｕＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＺｈｅｎｊｉａｎｇＪｉａｎｇｓｕ２１２００３，Ｃｈｉｎａ； ２．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＮａｎｊｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，ＮａｎｊｉｎｇＪｉａｎｇｓｕ２１００９７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＬｅｔｋｂｅａｐｏｓｉｔｉｖｅｉｎｔｅｇｅｒａｎｄＧ＝（Ｖ，Ｖ；Ｅ）ｂｅａｂｉｐａｒｔｉｔｅｇｒａｐｈｗｉｔｈ｜Ｖ｜＝｜Ｖ｜２ｋ＋１．Ｉｆｄ １ ２ １ ２ ≥ ８ （ｘ）＋ｄ（ｙ） ｋｆｏｒｅａｃｈｐａｉｒｏｆｖｅｒｔｉｃｅｓｘ Ｖ，ｙ Ｖ，ｔｈｅｎＧｉｓｃｏｖｅｒｅｄｂｙｋｉｎｄｅｐｅｎｄｅｎｔｑｕａｄｒｉｌａｔｅｒａｌｓ． ≥ ∈ ∈ ３ １ ２ Ｋｅｙｗｏｒｄｓ：ｂｉｐａｒｔｉｔｅｇｒａｐｈ；ｉｎｄｅｐｅｎｄｅｎｔｑｕａｄｒｉｌａｔｅｒａｌｓ；ｃｏｖｅｒｉｎｇ ０　引　言 图的子图覆盖问题是图论学科一个重要的研究课题。圈覆盖是子图覆盖研究的一个重要方向。著 名“四色问题”的一个等价形式是：无割边平面图可被两个偶子图（圈的并）覆盖。圈覆盖中研究较多的 是关于平衡二部图的圈覆盖问题的。文献［１－３］给出了一些结果，笔者对这一问题进行了研究，给出 了二部图四圈覆盖一个充分条件。 １　相关概念和主要结果 这里只考虑有限简单图。设Ｇ是一个图，用Ｖ（Ｇ）表示其顶点集，｜Ｖ（Ｇ）｜表示其顶点数，Ｅ（Ｇ）表 示其边集，｜Ｅ（Ｇ）｜表示其边数，简单地Ｅ（Ｇ）记为Ｅ。（Ｇ）表示Ｇ的最小度，对于ｕ Ｖ（Ｇ）和Ｈ Ｇ， δ ∈  Ｎ（ｕ，Ｈ）＝Ｎ（ｕ） Ｖ（Ｈ）表示Ｈ中ｕ的邻点，ｄ（ｕ，Ｈ）＝｜Ｎ（ｕ，Ｈ）｜，用〈Ｕ〉表示Ｇ的子图Ｕ在Ｇ Ｇ ∩ 收稿日期：２００５－０３－３１ 作