(s,k)-连通图

第８卷第１６期２００８年８月　１６７１—１８１９（２００８）１６—４６０７—０３　科学技术与工程　Ｓｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｏ１．８　Ｎｏ．１６　Ａｕｇ．２００８　＠２００８　Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ．　

（　，ｋ）一连通图　

张　燕　

（山东师范大学数学科学学院，济南２５００１４）　

摘要　图Ｇ为（　，ｊ｝）一连通图，如果Ｇ中任意ｓ个顶点的导出子图是ｊ｝一连通的。证明了：如果ｓ—ｊ｝≤　，则（ｓ，ｊ｝）一连　

通图Ｇ是完全圈可扩的。由此推出，若图Ｇ的连通度，ｃ（Ｇ）≥　，则Ｇ是完全圈可扩的。　

关键词（ｓ，ｋ）一连通图　连通度　完全圈可扩图　

中图法分类号０１５７．５；　文献标志码Ａ　

考虑的图是有限，无向，简单图，所使用的记号　和术语约定如下，其中未加说明的部分请参看文献　

［１］。　设Ｇ是一个图，　（Ｇ），Ｅ（Ｇ）分别表示Ｇ的顶点　

集和边集。对Ｊｓｃ　（Ｇ），口∈Ｖ（Ｇ）以及Ｇ的子图日，　令　Ⅳ　（口）＝｛　∈Ｖ（Ｈ）：　口∈Ｅ（Ｇ）｝，Ⅳ　（Ｓ）＝　

ｕ一　（　），　

１日Ｉ＝Ｉ　（日）Ｉ，６（Ｇ）＝ｍｉｎ｛ＩⅣ（　）Ｉ：　∈　（Ｇ）｝。　

Ⅳｃ（　）也简记为Ｎ（　），Ｉ　Ｇ　Ｉ称为图Ｇ的阶。Ｇ　的由Ｊｓ导出的子图记为Ｇ［Ｊｓ］。如果Ｇ—Ｊｓ不连通，　

则称Ｊｓ为Ｇ的一个顶点割。Ｇ中含顶点最少的顶点　割叫Ｇ的最小顶点割，最小顶点割中顶点的数目称　为Ｇ的连通度，记为，ｃ（Ｇ）。完全图　的连通度定　

义为，ｃ（Ｋｎ）＝／＇ｔ一１。如果，ｃ（Ｇ）≥ｋ，则称Ｇ是ｋ一　

连通的。１一连通图也叫连通图。显然，若Ｇ是ｋ一　连通的，则Ｖ　∈Ｖ（Ｇ），Ｇ一　是（ｋ一１）一连通的。　图Ｇ叫做局部连通的，如果Ｖ　∈Ｖ（Ｇ），Ｇ［Ｎ（　）］是　连通的。　如果图Ｇ满足：　

ｉ）Ｃ的每个顶点都在长度为３的圈上；　

２００８年４月１７日收到　作者简介：张燕，山东师范大学数学科学学院副教授。研究方　向：图论与组合优化。　ｉｉ）对Ｇ中任意一个圈Ｃ，只要Ｉ　（Ｃ）Ｉ＜　

Ｉ　Ｖ（Ｇ）Ｉ，就存在Ｇ的圈Ｃ　，使　（Ｃ）ｃ　（Ｃ　）且Ｉ　（Ｃ　）Ｉ＝Ｉ　（Ｃ）Ｉ＋１，　则称Ｇ是完全圈可扩的，同时称Ｃ　为Ｃ的　

扩圈。　设ｓ，ｋ是满足ｓ＞ｋ≥１的整数。如果对任意满　足ＩＪｓＩ＝ｓ的子集ＪｓｃＶ（Ｇ），Ｇ［Ｓ］是ｋ一连通的，则　

图Ｇ叫做（ｓ，ｋ）一连通图。　设Ｃ＝Ｕ１　２…　１为Ｇ的一个圈，　，　∈Ｖ（Ｃ），　

用　，，　，分别表示Ｃ的顶点　和　…（这里点的　

下标模ｍ）。设Ｇ　，Ｇ２是两个无公共顶点的图，它们　的顶点集分别为　

Ｖ（Ｇ　）＝｛　，　２，…，　｝，　（Ｇ２）＝｛“　，“２，…，　“　｝。　

用符号Ｇ　；Ｇ２表示一个图，该图的顶点集和边　

集分别为：　

Ｖ（Ｇ　；Ｇ２），Ｅ（Ｇ　；Ｇ２）＝Ｅ（Ｇ　）Ｕ　Ｅ（Ｇ２）Ｕ　｛Ｕｉ“　Ｉｉ＝１，２，…，／／，｝。　弓Ｉ理１－ｌ　（Ｇ）≥，ｃ（Ｇ）。　

引理２（１）（ｓ，ｋ）一连通图是（ｓ一１，ｋ一１）一　连通图；　

（２）（ｓ，ｋ）一连通图是（ｓ＋１，ｋ）一连通图。　证明设Ｇ是（ｓ，ｋ）一连通图。　

（１）对Ｖ　ＴＣ　（Ｇ），Ｉ　Ｉ＝ｓ一１，取　∈　（Ｇ）一　Ｔ，则Ｇ［　ｕ｛

　｝］是ｋ一连通的，于是Ｇ［Ｔ］＝Ｇ［ＴＵ　维普资讯 http://www.cqvip.com 科学技术与工程　４卷　

｛　｝］一１３是（后一１）一连通的，所以Ｇ是（ｓ一１，后一　１）一连通图。　

（２）否则，存在　ｃ　（Ｇ），Ｉ　Ｉ＝ｓ＋１，使　，ｃ（Ｇ［Ｕ］）＜后。于是有　ｃ　，Ｉ　Ｉ：后一１，使　Ｇ［Ｕ］一　不连通。在Ｇ［Ｕ］一　的不同分支中取　

ｓ一（后一１）＝ｓ一后＋１（≥２）个顶点，构成集合ｓ，易　见　也是Ｇ［　ｕ　Ｓ］的顶点割，但是Ｉ　ｕ　Ｓ　Ｉ＝Ｉ　Ｉ　

＋ＩＳ　Ｉ＝ｓ，这与Ｇ是（ｓ，后）一连通图矛盾。引理２　

证完。　由引理２之（２），（ｓ，后）一连通图是后一连通的。　

引理３　设Ｇ是凡阶（ｓ，后）一连通图，则　

，ｃ（Ｇ）≥凡一ｓ＋后。　证明由引理２之（１），Ｇ是（ｓ一（后一１），１）一　

连通图，即Ｇ中任意ｓ一后＋１个顶点的导出子图是　连通的，换言之，对Ｖ　Ｓｃ　（Ｇ），ｌ　Ｓ　ｌ＝／１，一（ｓ一　＋１）　

＝凡一ｓ＋后一１，Ｇ—Ｓ是连通的，所以，ｃ（Ｇ）≥ｎ—ｓ＋　

后。引理３证完。　定理设Ｇ是凡阶（ｓ，后）一连通图，若ｓ一后≤　

，则Ｇ是完全圈可扩的。　二　

此定理中的条件ｓ一后≤　是最好可能的。　二　图　一　一　就是一个反例，此图是Ｉｔ，＝２（ｓ一　）阶　

（ｓ，后）一连通图，且ｓ一后＝　１７，，而它不是完全圈可　二　扩的。　

以下是定理的证明。　论断１　Ｖ　ＴＣ　Ｖ（Ｇ），若ｆ　ＴＩ≥　（Ｇ），则Ｇ［Ｔ］　是连通的。　证明　由引理２之（１），Ｇ是（ｓ一（后一１），１）一　连通图，结合引理２之（２）可知，Ｖ　ＴＣ　Ｖ（Ｇ），当Ｉ　７１Ｉ　

≥ｓ一　＋１时，Ｇ［Ｔ］是连通的。另一方面，由已知条　件ｒ￣２（ｓ一　）＋１，结合引理１和引理３，有　

ｆ　ＴＩ≥　（Ｇ）≥，ｃ（Ｇ）≥凡一（ｓ一后）≥２（ｓ一后）＋　

１一（ｓ一　）：ｓ一　＋１．　所以Ｇ［Ｔ］是连通的。论断１证毕。　由论断１，Ｇ是局部连通的。在定理的条件下，　

有凡≥２（ｓ一后）＋１≥３，由此易得，Ｇ的每个顶点都　在长度为３的圈上。　设Ｃ是Ｇ之一圈，且Ｉ　（Ｃ）Ｉ＜Ｉ　Ｖ（Ｇ）Ｉ。以下　假定ｃ没有扩圈。令　Ｈ＝Ｇ—　（ｃ），Ｒ＝　（日），Ｅ（日，Ｒ）＝｛　Ｉ　∈　

Ｈ，Ｙ∈Ｒ｝，　因为Ｇ连通，所以尺≠西≠Ｅ（Ｈ，Ｒ）。　论断２设　。，ｘｙ：∈Ｅ（日，尺）（　∈Ｖ（Ｈ），Ｙ。，　Ｙ２∈Ｒ），则　

（１）Ｙ。Ｙ２隹Ｅ（Ｃ）；　

（２）ｙｌ—Ｙ２一，ｙ　隹Ｅ（Ｇ）。　证明否则易得ｃ的扩圈。论断２证毕。　

取Ｙ∈Ｒ，则％（Ｙ）≠咖。现考虑％（Ｙ）和　

％（ｙ　）的关系。　

情况１　Ｉ％（ｙ）Ｉ≥Ｉ％（ｙ　）Ｉ　

令Ａｒｃ（Ｙ　）＝｛　一Ｉ　∈Ｎｃ（Ｙ　）｝，则　

ＩⅣ　（），　）Ｉ＝ＩⅣｃ（，，　）Ｉ。　取Ｔ＝％（ｙ）ｕＮｃ（Ｙ　），由论断２，Ｅ（％（Ｙ），　

Ⅳ　（Ｙ　））＝咖，所以Ｇ［７１］不连通。但是，因为　

％（ｙ）ｎⅣ　（Ｙ　）＝咖，所以　

ＩＴＩ＝Ｉ％（ｙ）ｕ　（Ｙ　）ｆ＿Ｉ％（ｙ）ｆ＋Ｉ　（Ｙ　）Ｉ　

≥Ｉ％（ｙ　）Ｉ＋Ｉ　（Ｙ　）Ｉ＝Ｉ％（ｙ　）Ｉ＋ＩⅣｃ（ｙ　）Ｉ＝　

ｆ％（ｙ　）ＵＮｃ（Ｙ　）Ｉ＝ＩＮ（ｙ　）Ｉ≥　（Ｇ），　此与论断１相矛盾。　情况２　Ｉ％（ｙ）Ｉ＜％（ｙ　）　

此时％（Ｙ　）≠咖，令Ⅳ　（Ｙ）＝｛　Ｉ　∈　Ⅳｃ（ｙ）｝，则ＩＮｃ（Ｙ）Ｉ＝ＩＮｃ（Ｙ）Ｉ。　

取Ｔ＝ＮＨ（ｙ　）ｕ　（ｙ），由论断２，　

Ｅ（％（ｙ　），Ｎｃ（Ｙ））＝咖，所以Ｇ［７１］不连通。但　

是，因为％（ｙ　）ｎＮｃ（Ｙ）＝咖，所以　

Ｉ　７１　Ｉ＝Ｉ％（Ｙ　）ｕ　（Ｙ）Ｉ＝Ｉ％（Ｙ　）Ｉ＋　

Ｉ　（Ｙ）Ｉ＞Ｉ％（Ｙ）Ｉ＋Ｉ　（Ｙ）Ｉ＝Ｉ％（Ｙ）Ｉ＋　

ＩＮｃ（Ｙ）Ｉ＝Ｉ％（ｙ）ｕⅣｃ（Ｙ）Ｉ＝ＩＮ（ｙ）Ｉ≥　（Ｇ），　此与论断１相矛盾。　定理证完。　

推论１若，ｃ（Ｇ）≥　，则凡阶图Ｇ是完全圈　二　可扩的。　前文中所举例图　一　；Ｋ一　也可以说明，这里　

，ｃ（Ｇ）的下界是最好可能的。

　维普资讯 http://www.cqvip.com １６期　张燕：（Ｓ，ｋ）－连通图　４６０９　

证明由，ｃ（Ｇ）的定义可知，对Ｇ中任意一个　

含，ｃ（Ｇ）一１个顶点的集合ｓ　ｃ　Ｖ（Ｇ），Ｇ—Ｓ一定是　

连通的。换言之，Ｇ中任意ｎ一（，ｃ（Ｇ）一１）　，ｃ（Ｇ）＋１个顶点的导出子图是连通的，即Ｇ是（ｓ，　

ｋ）一连通图，这里ｓ＝ｎ—　（Ｇ）＋１，ｋ＝１。　

因为　

ｓ—ｋ＝（ｎ一，ｃ（Ｇ）＋１）一１＝ｎ一，ｃ（Ｇ）≤ｎ—　ｎ＋ｌ　ｎ—ｌ　丁　丁，　

由定理，Ｇ是完全圈可扩的。推论５证毕。　

参考文献　

１　Ｂｏｎｄｙ　Ｊ　Ａ，Ｍｕｒｔｙ．Ｕ　Ｓ　Ｒ．Ｇｒａｐｈ　Ｔｈｅｏｒｙ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ，Ｎｅｗ　Ｙｏｒｋ，　Ｍａｃｍｉｌｌａｎ　Ｌｏｎｄｏｎ　ａｎｄ　Ｅｌｓｅｖｉｅｒ，Ｎｅｗ　Ｙｏｒｋ；１９７６　

（Ｓ，ｋ）－ｃｏｎｎｅｃｔｅｄ　Ｇｒａｐｈｓ　

ＺＨＡＮＧ　Ｙａｎ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｅ　Ｓｃｉｅｎｃｅ，Ｓｈａｎｄｏｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ　２５００１４，　ＩＬ　Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ａ　ｇｒａｐｈ　Ｇ　ｉｓ　ｃａｌｌｅｄ　ａ（ｓ，ｋ）一ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　ｉｆ，ｆｏｒ　ａｎｙ　ＳｃＶ（Ｇ）ｗｉｔｈｌＳｌ＝ｓ，ｔｈｅ　ｉｎｄｕｃｅｄ　ｓｕｂｇｒａｐｈ　

ｂｙ　Ｓ　ｉｓ｜ｌ｝－ｃｏｎｎｅｃｔｅｄ．Ｉｔ　ｉｓ　ｐｒ。ｖｅ　ｔｈａｔ　ａ（ｓ，｜ｌ｝）－ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　Ｇ　ｉｓ　ｆｕｌｌｙ　ｃｙｃｌｅ　ｅｘｔｅｎｄａｂｌｅ　ｉｆ　ｓ一｜ｌ｝≤　．Ｆｍｍ　ｔｈｉｓ　

ｒｅｓｕｌｔ，ｔｈａｔ　ｅＶｅｒｙ　ｇｒａｐｈ　ｉｓ。ｂｔａｉｎｅｄ　ｗｈ。ｓｅ　ｖｅｒｔｅｘｃ。ｎｎｃｃｔｉｖｉｔｙ　（Ｇ）≥　ｉｓ　ｆｕｌｌｙ　ｃｙｃｌｅ　ｅｘｔｅｎｄａｂｌｅ．　

［Ｋｅｙ　ｗｏｒｄｓ］　（ｓ，ｋ）一ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈｓ　ｖｅｒｔｅｘｃｏｎｎｅｃｔｉｖｉｔｙ　ｆｕｌｌｙ　ｃｙｃｌｅ　ｅｘｔｅｎｄａｂｌｅ　ｇｒａｐｈｓ　

（上接第４６０３页）　）　

Ｏｎ　Ｏｒｄｅｒ－ｐｒｅｓｅｒｖｉｎｇ　Ｐａｒｔｉａｌ　Ｔｒａｎｓｆｏｒｍａｔｉｏｎ　Ｓｅｍｉｇｒｏｕｐｓ　

ＬＩＵ　Ｙｕ—ｃｈｕｎ，ＱＩＮ　Ｍｅｉ—ｑｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｓｃｉｅｎｃｅｓ，Ｓｈａｎｄｏｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，ｊｉ’ｎａｎ，２５００１４．　Ｒ．Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ｔｈｅ　ｓｕｆｆｉｃｉｅｎｔ　ａｎｄ　ｎｅｃｅｓｓａｒｙ　ｃｏｎｄｉｔｉｏｎｓ　ｆｏｒ　ａ　ｏｒｄｅｒ—ｐｅｒｓｅｒｖｉｎｇ　ｐａｒｔｉａｌ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ｓｅｍｉｇｒｏｕｐｓ　ｏｎ　ａ　

ｔｏｔａｌ　ｏｒｄｅｒｅｄ　ｆｉｎｉｔｅ　ｓｅｔ　ｔｏ　ｂｅ　ａ　ｌｅｆｔ（ｒｉｇｈｔ）ｇｒｏｕｐ　ａｒｅ　ｇｉｖｅｎ．　［Ｋｅｙ　ｗｏｒｄｓ］　ｏｒｄｅｒ—ｐｒｅｓｅｒｖｉｎｇ　ｐａｒｔｉａｌ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ｉｄｅｍｐｏｔｅｎｔ　ｌｅｆｔ（ｒｉｇｈｔ）ｚｅｒｏ　ｓｅｍｉｇｒｏｕｐ　ｌｅｆｔ　（ｒｉｇｈｔ）ｇｒｏｕｐ，ｔｅｃｔａｎｇｕｌａｒ

　ｂａｎｄ　维普资讯 http://www.cqvip.com