二面体群的双凯莱图的匹配可扩性

第４２卷第５期　２０１　５年９月　浙江大学学报（理学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　ｈｔｔｐ：／／ｗｗｗ．ｊｏｕｒｎａｌｓ．ｚｊｕ．ｅｄｕ．ｃｎ／ｓｃｉ　Ｖｏ１Ｓ．４２　Ｎｏ．５　ｅｐ．２０１５　ＤＯＩ：１０．３７８５／ｊ．ｉｓｓｎ．１００８—９４９７．２０１５．０５．００５　ｉｌｉｔｙ　ｏｆ　ｂｉ－Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐｓ　ＧＡＯ　Ｘｉｎｇ　，ＬＹＵ　Ｈｕａｚｈｏｎｇ。，ＷＡＮＧ　Ｗｅｉｚｈｏｎｇ。　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｓｔａｔｉｓｔｉｃｓ，Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｌｅｘ　Ｓｙｓｔｅｍｓ，Ｌａｎｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００００，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ，Ｃｂｅｎｇｄｕ　６１１７３１，Ｃｈｉｎａ；３。Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ，Ｌａｎｚｈｏｕ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｌｅｔ　Ｇ　ｂｅ　ａ　ｆｉｎｉｔｅ　ｇｒｏｕｐ　ａｎｄ　Ｓ　ａ　ｎｏｎｅｍｐｔｙ　ｓｕｂｓｅｔ（ｐｏｓｓｉｂｌｙ　ｃｏｎｔａｉｎｉｎｇ　ｔｈｅ　ｉｄｅｎｔｉｔｙ　ｅｌｅｍｅｎｔ）ｏｆ　Ｇ．Ｔｈｅ　ｂｉ—　Ｃａｙｌｅｙ　ｇｒａｐｈ　ＢＣ（Ｇ，Ｓ）ｏｆ　Ｇ　ｗｉｔｈ　ｒｅｓｐｅｃｔ　ｔｏ　Ｓ　ｉｓ　ｄｅｆｉｎｅｄ　ａｓ　ｔｈｅ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｗｉｔｈ　ｖｅｒｔｅｘ　ｓｅｔ　Ｇ×｛０，１）ａｎｄ　ｅｄｇｅ　ｓｅｔ｛（ｇ，Ｏ）（ｓｇ，１）Ｉｇ∈Ｇ，ｓ∈Ｓ｝．Ａ　ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　Ｐ　ａｄｍｉｔｔｉｎｇ　ａ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｉｓ　ｃａｌｌｅｄ　—ｅｘｔｅｎｄａｂｌｅ　ｗｈｅｎｅｖｅｒ　Ｐ　ｈａｓ　ａｔ　ｌｅａｓｔ　２ｎ＋２　ｖｅｒｔｉｃｅｓ，ａｎｄ　ｅｖｅｒｙ　ｍａｔｃｈｉｎｇ　ｏｆ　ｓｉｚｅ　ｃａｎ　ｂｅ　ｅｘｔｅｎｄｅｄ　ｔｏ　ａ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｏｆ　Ｐ．Ｔｈｅ　２－ｅｘ—　ｔｅｎｄａｂｌｅ　ｂｉ　Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐｓ　ａｒｅ　ｃｈａｒａｃｔｅｒｉｚｅｄ．　Ｋｅｙ　Ｗｏｒｄｓ：ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈ；ｅｘｔｅｎｄａｂｉｌｉｔｙ；ｄｉｈｅｄｒａｌ　ｇｒｏｕｐ　高兴　，吕华众　，王维忠。（１．兰州大学数学与统计学院应用数学与复杂系统重点实验室，甘肃兰州７３００００；　２．电子科技大学数学科学学院，四川成都６１１７３１；３．兰州交通大学数学系，甘肃兰州７３００７０）　二面体群的双凯莱圈的匹配可扩性．浙江大学学报（理学版），２０１５，４２（５）：５２６—５２８　摘　要：令Ｇ为有限群，ｓ为Ｇ的非空有限子集，Ｇ关于ｓ的双凯莱图ＢＣ（Ｇ，ｓ）是一个二部图，其顶点集是Ｇ×｛０，　ｌ｝，边集是｛（ｇ，Ｏ）（ｓｇ，１）ｆｇ∈Ｇ，５∈Ｓ）．若有完美匹配的连通图ｒ至少有２　＋２个顶点，且每一个大小为７２的匹配　都可以扩充为一个完美匹配，则称此完美匹配的连通图Ｉ１是　可扩的，并对二面体群的双凯莱的２一可扩性进行了　刻画．　关键词：双凯莱图；可扩性；二面体群　中图分类号：Ｏ１５７．５　文献标志码：Ａ　文章编号：１００８—９４９７（２０１５）０５—５２６—０３　Ｍ　ｓｈａｒｅ　ａ　ｃｏｍｍｏｎ　ｖｅｒｔｅｘ．Ａ　ｍａｔｃｈｉｎｇ　Ｍ　ｉｓ　ｐｅｒｆｅｃｔ　１　Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｉｆ　ｅｖｅｒｙ　ｖｅｒｔｅｘ　ｏｆ　Ｐ　ｉｓ　ｃｏｖｅｒｅｄ　ｂｙ　ａｎ　ｅｄｇｅ　ｏｆ　ＭＩ　Ｔｈｅ　ｃｏｎｃｅｐｔ　ｏｆ，２一ｅｘｔｅｎｄａｂｌｅ　ｇｒａｐｈｓ　ｗａｓ　ｉｎｔｒｏｄｕｃｅｄ　ｂｙ　Ｇｒａｐｈｓ　ｃｏｎｓｉｄｅｒｅｄ　ａｒｅ　ｆｉｎｉｔｅ　ａｎｄ　ｓｉｍｐｌｅ．Ｆｏｒ　ａ　ＰＩ　ＵＭＭＥＲ［　］ｉｎ　１　９８０　ａｎｄ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｇｒａｐｈ　ｒ，ｉｔｓ　ｖｅｒｔｅｘ　ｓｅｔ　ａｎｄ　ｅｄｇｅ　ｓｅｔ　ａｒｅ　ｄｅｎｏｔｅｄ　ｂｙ　ｔｈｅ　—ｅｘｔｅｎｄａｂｉｌｉｔｙ　ａｎｄ　ｔｈｅ　ｏｔｈｅｒ　ｇｒａｐｈ　ｐｒｏｐｅｒｔｉｅｓ　Ｖ（ｒ）ａｎｄ　Ｅ（ｒ），ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｔｈｅ　ｍｉｎｉｍｕｍ　ｗａｓ　ｓｔｕｄｉｅｄｌｌ＿　．Ａ　ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　Ｉ１　ａｄｍｉｔｔｉｎｇ　ａ　ｄｅｇｒｅｅ　ｏｆ　Ｐ　ｉｓ　ｄｅｎｏｔｅｄ　ｂｙ　（Ｉ１）．Ｔｈｅ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｉｓ　ｃａｌｌｅｄ　一ｅｘｔｅｎｄａｂｌｅ　ｗｈｅｎｅｖｅｒ　Ｉ１　ｏｆ　Ｆ　ｄｅｎｏｔｅｄ　ｂｙ忌（ｒ），ｉｓ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｉｚｅ　ｏｆ　ａ　ｈａｓ　ａｔ　ｌｅａｓｔ　２ｎ＋２　ｖｅｒｔｉｃｅｓ，ａｎｄ　ｅｖｅｒｙ　ｍａｔｃｈｉｎｇ　ｏｆ　ｓｉｚｅ　ｖｅｒｔｅｘ　ｓｅｔ　Ｓ　ｓｕｃｈ　ｔｈａｔ　ｒ＼Ｓ　ｉｓ　ｄｉｓｃｏｎｎｅｃｔｅｄ　ｏｒ　ｈａｓ　ｃａｎ　ｂｅ　ｅｘｔｅｎｄｅｄ　ｔｏ　ａ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｏｆ　ｒ．　ｏｎｌｙ　ｏｎｅ　ｖｅｒｔｅｘ．Ａ　ｇｒａｐｈ　Ｐ　ｉｓ　ｈ－ｃｏｎｎｅｃｔｅｄ　ｉｆ　ｉｔｓ　ＰＬＵＭＭＥＲ［。］ｓｔｕｄｉｅｄ　ｔｈｅ　ｅｘｔｅｎｄａｂｉｌｉｔｙ　ｏｆ　ｂｉｐａｒｔｉｔｅ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ｉｓ　ａｔ　ｌｅａｓｔ　ｋ．Ａ　ｓｅｔ　Ｍ　ｏｆ　ｅｄｇｅｓ　ｏｆ　ａ　ｇｒａｐｈｓ　ａｎｄ　ＣＨＡＮ　ｅｔ　ａｌ［　ｃｈａｒａｃｔｅｒｉｚｅｄ　ｔｈｅ　ｇｒａｐｈ　Ｐ　ｉｓ　ｃａｌｌｅｄ　ａ　ｍａｔｃｈｉｎｇ　ｉｆ　ｎｏ　ｔｗｏ　ｍｅｍｂｅｒｓ　ｏｆ　２－ｅｘｔｅｎｄａｂｌｅ　Ａｂｅｌｉａｎ　Ｃａｙｌｅｙ　ｇｒａｐｈｓ．　Ｒｅｃｅｉｖｅｄ　ｄａｔｅ：Ｆｅｂ．９，２Ｏ１　５。　Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍ：Ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（１１２０１２０１），ｔｈｅ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　ＦｏｕｎｄａｔｉＯｎ　ｏｆ　Ｇａｎｓｕ　Ｐｒｏｖｉｎｃｅ（１３０８ＲＪＺＡ１１２）ａｎｄ　ｔｈｅ　Ｆｕｎｄａｍｅｎｔａｌ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄｓ　ｆｏｒ　ｔｈｅ　Ｃｅｎｔｒａｌ　Ｕｎｉｖｅｒｓｉｔｉｅｓ（１ｚｕｊｂｋｙ一２０１５－７６）．　Ａｂｏｕｔ　ｔｈｅ　ａｕｔｈｏｒ：ＧＡＯ　Ｘｉｎｇ（１　９８２一），ｍａｌｅ，ｄｏｃｔｏｒ，ａｓｓｏｃｉａｔｅ　ｐｒｏｆｅｓｓｏｒ，ｔｈｅ　ｆｉｅｌｄｓ　ｏｆ　ｉｎｔｅｒｅｓｔ　ａｒｅ　ａｌｇｅｂｒａ　ａｎｄ　ａｌｇｅｂｒａｉｃ　ｇｒａｐｈ　ｔｈｅｏｒｙ，Ｅ－　ｍａｉｌ：ｇａｏｘｉｎｇ＠ｌｚｕ．ｅｄｕ．ｃｎ．　第５期　高兴，等：二面体群的双凯莱图的匹配可扩性　５２７　Ｒｅｃａｌｌ　ｔｈａｔ　ａ　ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　Ｐ　ｗｈｉｃｈ　ｉｓ　ｅｄｇｅ—ｔｒａｎｓｉｔｉｖｅ　ｎｅｅｄ　ｎｏｔ　ｂｅ　ｖｅｒｔｅｘ—ｔｒａｎｓｉｔｉｖｅ．Ｉｎ　ｔｈｉｓ　ｃａｓｅ，Ｐ　ｍｕｓｔ　ｂｅ　ｂｉｐａｒｔｉｔｅ　ａｎｄ　Ａｕｔ（ｒ）ｈａｓ　ｔｗｏ　ｏｒｂｉｔｓ　ｏｎ　ｔｈｅ　ｖｅｒｔｉｃｅｓ　ｆｏｒｍｉｎｇ　ｔｈｅ　ｂｉｐａｒｔｉｔｉｏｎ．Ｓｕｃｈ　ａ　ｒｅｇｕｌａｒ　ｇｒａｐｈ　ｉｓ　ｃａｌｌｅｄ　ｓｅｍｉ—ｓｙｍｍｅｔｒｉｃ．Ｔｏ　ｓｔｕｄｙ　ｓｅｍｉ—ｓｙｍｍｅｔｒｉｃ　ｇｒａｐｈｓ，ＸＵ［　］　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　ｃｏｎｃｅｐｔ　ｏｆ　ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ．Ｌｅｔ　Ｇ　ｂｅ　ａ　ｆｉｎｉｔｅ　ｇｒｏｕｐ　ａｎｄ　Ｓ　ａ　ｓｕｂｓｅｔ（ｐｏｓｓｉｂｌｙ　ｃｏｎｔａｉｎｉｎｇ　ｔｈｅ　ｉｄｅｎｔｉｔｙ　ｅｌｅｍｅｎｔ）ｏｆ　Ｇ．Ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈ　ＢＣ（Ｇ，Ｓ）ｏｆ　Ｇ　ｗｉｔｈ　ｒｅｓｐｅｃｔ　ｔｏ　Ｓ　ｉｓ　ｄｅｆｉｎｅｄ　ａｓ　ｔｈｅ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｗｉｔｈ　ｖｅｒｔｅｘ　ｓｅｔ　Ｇ×｛０，１｝ａｎｄ　ｅｄｇｅ　ｓｅｔ｛（ｇ，Ｏ）（　，１）ｌ　ｇ∈Ｇ，ｓ　Ｅ　Ｓ｝．Ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ａｒｅ　ｇｅｎｅｒａｌｉｚａｔｉｏｎ　ｏｆ　Ｃａｙｌｅｙ　ｇｒａｐｈｓ．　Ｈａｍｉｌｔｏｎｉａｎ　ｃｙｃｌｅｓ　ｏｆ　ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｗｅｒｅ　ｃｈａｒａｃｔｅｒｉｚｅｄ　ｉｎ　Ｅ　６－１　ａｓ　ｗｅｌｌ　ａｓ　ｓｏｍｅ　ａｌｇｅｂｒａｉｃ　ｐｒｏｐｅｒｔｉｅｓ［　．Ｔｈｅ　ｅｘｔｅｎｄａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｆｉｎｉｔｅ　Ａｂｅｌｉａｎ　ｇｒｏｕｐｓ　ｗａｓ　ｓｔｕｄｉｅｄ　ｉｎ　Ｅ８３．Ｉｔ　ｉｓ　ｎａｔｕｒａｌ　ｔｏ　ｓｔｕｄｙ　ｔｈｅ　ｅｘｔｅｎｄａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ｂｉ－Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｎｏｎ－Ａｂｅｌｉａｎ　ｇｒｏｕｐｓ．Ｃｌｅａｒｌｙ，ａｌｌ　ｃｏｎｎｅｃｔｅｄ　ｔｈｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｆｉｎｉｔｅ　ｇｒｏｕｐｓ　ａｒｅ　１－ｅｘｔｅｎｄａｂｌｅ　ｂｅｃａｕｓｅ　ａ　ｒｅｇｕｌａｒ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｉｓ　ｌ—ｆａｃｔｏｒｉｚａｔｉｏｎＥ　．　Ｗｅ　ｃｈａｒａｃｔｅｒｉｚｅ　２一ｅｘｔｅｎｄａｂｌｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐｓ．Ｔｈｅ　ｍａｉｎ　ｒｅｓｕｌｔ　ｉｓ　Ｔｈｅｏｒｅｍ　１　Ｌｅｔ　Ｓ　ｂｅ　ａ　ｓｕｂｓｅｔ　ｏｆ　ａ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐ　Ｄ　ｓｕｃｈ　ｔｈａｔ＜Ｓ＞一Ｄ　．Ｔｈｅｎ　ＢＣ（Ｄ　，Ｓ）ｉｓ　２一ｅｘｔｅｎｄａｂｌｅ　ｉｆ　ａｎｄ　ｏｎｌｙ　ｉｆ　ｌ　Ｓ　ｌ≥３．　Ｒｅａｄｅｒｓ　ａｒｅ　ｒｅｆｅｒｒｅｄ　ｔｏ　ＥｌＯ］ｆｏｒ　ａｌｌ　ｔｅｒｍｉｎｏｌｏｇｉｅｓ　ａｎｄ　ｎｏｔａｔｉｏｎｓ　ｔｈａｔ　ａｒｅ　ｎｏｔ　ｄｅｆｉｎｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．　２　Ｐｒｏｏｆ　ｏｆ　ｔｈｅ　ｍａｉｎ　ｒｅｓｕｌｔ　Ｉｎ　ｔｈｉｓ　ｓｅｃｔｉｏｎ，ｗｅ　ｓｈａｌｌ　ｃｈａｒａｃｔｅｒｉｚｅ　２一ｅｘｔｅｎｄａｂｌｅ　ｂｉ－Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐｓ．　Ｌｅｍｍａ　１　Ｅｖｅｒｙ　—ｅｘｔｅｎｄａｂｌｅ　ｇｒａｐｈ　ｉｓ（　一　１）一ｅｘｔｅｎｄａｂｌｅ　ａｎｄ（　＋１）一ｃｏｎｎｅｃｔｅｄ．　Ｌｅｍｍａ　２　Ｉｆ　Ｐ　ｉｓ　ａ　ｓｉｍｐｌｅ　ｇｒａｐｈ，ｔｈｅｎ　（Ｉ１）≥尼（ｒ）．　Ｔｈｅ　ｆｏｌｌｏｗｉｎｇ　ｒｅｓｕｌｔｓ　ｗｉｌｌ　ｂｅ　ｕｓｅｄ　ｉｎ　ｔｈｅ　ｐａｐｅｒ．　Ｌｅｍｍａ　３　Ｌｅｔ　Ｇ　ｂｅ　ａ　ｇｒｏｕｐ，Ｓ　ａ　ｎｏｎｅｍｐｔｙ　ｓｕｂｓｅｔ　ｏｆ　Ｇ　ａｎｄ　ｓ　Ｅ　Ｓ．Ｔｈｅｎ　ＢＣ（Ｇ，１ｓ）　ＢＣ（Ｇ，ｓ　Ｓ）．　Ｐｒｏｏｆ　Ｄｅｆｉｎｅ　ａ　ｍａｐ　∞　ｆｒｏｍ　ＢＣ（Ｇ，Ｓ）ｔｏ　ＢＣ（Ｃ，ｓ　Ｓ）ｂｙ　：（ｇ，０）一（ｇ，Ｏ），　（ｇ，１）一（ｓ　ｇ，１），　ｇ∈Ｇ．　Ｔｈｅｎ　ｉｓ　ａ　ｂｉｊｅｃｔｉｏｎ　ｆｒｏｍ　Ｖ（ＢＣ（Ｇ，Ｓ））ｔｏ　（ＢＣ（Ｇ，　Ｓ））．Ｔ０　ｓｈｏｗ　ｔｈａｔ∞ｉｓ　ａｎ　ｉｓｏｍｏｒｐｈｉｓｍ，　ｌｅｔ（ｇ１，Ｏ）（ｇ２，１）Ｅ　Ｅ（ＢＣ（Ｇ，Ｓ））ｗｉｔｈ　ｇ１，ｇ２　Ｅ　Ｇ．　Ｔｈ　ｎ　（ｇｌ，Ｏ）（ｇ２，１）Ｅ　Ｅ（ＢＣ（Ｇ，Ｓ））甘ｇ２ｇ１　Ｅ　Ｓ甘　ｓ　ｇ２ｇＴ　Ｅ　ｓ　Ｓ甘　（ｇｌ，０）（ｓ一　ｇ２，１）Ｅ　Ｅ（ＢＣ（Ｇ，ｓ　Ｓ））∞　（（ｇｌ，Ｏ））　（（ｇ２，１））Ｅ　Ｅ（ＢＣ（Ｇ，ｓ　Ｓ））．　Ｈｅｎｃｅ∞ｉｓ　ａｎ　ｉｓｏｍｏｒｐｈｉｓｍ．　Ｉｎ　ｔｈｅ　ｖｉｅｗ　ｏｆ　ｌｅｍｍａ　３。ｗｉｔｈｏｕｔ　ｔｈｅ　ｌＯＳＳ　ｏｆ　ｇｅｎｅｒａｌｉｔｙ，ｗｅ　ｍａｙ　ｓｕｐｐｏｓｅ　ｔｈａｔ　１　Ｅ　Ｓ　ｆｏｒ　ａｎｙ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈ　ＢＣ（Ｇ，Ｓ）ｉｎ　ｔｈｅ　ｆｏｌｌｏｗｉｎｇ．Ｉｔ　ｉｓ　ｓｈｏｗｎ　ｉｎ［８］ｔｈａｔ　ａ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈ　ＢＣ（Ｇ，ｓ）ｏｆ　ａｎ　Ａｂｅｌｉａｎ　ｇｒｏｕｐ　Ｇ　ｉｓ　ｃｏｎｎｅｃｔｅｄ　ｉｆ　ａｎｄ　ｏｎｌｙ　ｉｆ＜Ｓ＞　一Ｇ．Ｔｈｅ　ｎｅｘｔ　ｌｅｍｍａ　ｇｅｎｅｒａｌｉｚｅｓ　ｔｈｉｓ　ｒｅｓｕｌｔ．　Ｌｅｍｍａ　４　Ｌｅｔ　Ｇ　ｂｅ　ａ　ｇｒｏｕｐ　ａｎｄ　Ｓ　ａ　ｎｏｎｅｍｐｔｙ　ｓｕｂｓｅｔ　ｏｆ　Ｇ．Ｔｈｅｎ　ＢＣ（Ｇ，Ｓ）ｉｓ　ｃｏｎｎｅｃｔｅｄ　ｉｆ　ａｎｄ　ｏｎｌｙ　ｉｆ＜Ｓ＞一Ｇ．　Ｐｒｏｏｆ　Ｎｅｃｅｓｓｉｔｙ：Ｉｆ（Ｓ＞≠Ｇ，ｔｈｅｎ（Ｓ＞ｉｓ　ａ　ｐｒｏｐｅｒ　ｓｕｂｇｒｏｕｐ　ｏｆ　Ｇ．Ｌｅｔ　ｇ（Ｓ＞ｂｅ　ａ　ｌｅｆｔ　ｃｏｓｅｔ　ｏｆ　（Ｓ）ｓｕｃｈ　ｔｈａｔ　ｇ＜Ｓ）≠（Ｓ），ｗｈｅｒｅ　ｇ∈Ｇ．Ｔｈｅｎ　ｔｈｅｒｅ　ｉｓ　ｎｏ　ｅｄｇｅ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｖｅｒｔｉｃｅｓ＜Ｓ＞×｛Ｏ，１｝　ａｎｄ　ｇ（Ｓ＞×｛０，１｝，ｗｈｉｃｈ　ｃｏｎｔｒａｄｉｃｔｓ　ｔｈｅ　ｆａｃｔ　ｔｈａｔ　ＢＣ（Ｇ，Ｓ）ｉｓ　ｃｏｎｎｅｃｔｅｄ．　Ｓｕｆｆｉｃｉｅｎｃｙ：Ｉｔ　ｉｓ　ｓｕｆｆｉｃｉｅｎｔ　ｔｏ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅｒｅ　ｉｓ　ａ　ｐａｔｈ　ｆｒｏｍ　ｔｈｅ　ｖｅｒｔｅｘ（１，０）ｔｏ　ａｎｙ　ｏｔｈｅｒ　ｖｅｒｔｅｘ（ｇ，　），ｗｈｅｒｅ　ｇ　Ｅ　Ｇ　ａｎｄ　ｉ一０　ｏｒ　１．Ｓｉｎｃｅ　（Ｓ＞＝＝：Ｇ，ｉｔ　ｉｍｐｌｉｅｓ　ｔｈａｔ　ｇ—ｓ１　ｓ２…ｓ　ｆｏｒ　ｓｌ，ｓ２，…，　ｓ＾∈Ｓ．Ｉｆ　ｉ一１，ｔｈｅｎ　（１，Ｏ）（　，１）（ｓｋ，０）（　一１　Ｓｋ，１）（ｓ　一１　，０）…（ｓｌ　Ｓ２…　，１）　ｉｓ　ｔｈｅ　ｒｅｑｕｉｒｅｄ　ｐａｔｈ．Ｉｆ　ｉ一０，ｔｈｅｎ　（１，Ｏ）（Ｓ　）（　，０）（　＾一１　Ｓ　，１）（Ｓ　一ｌ　Ｓ　，０）…　（Ｓｌ　Ｓ２…Ｓ＾，１）（Ｓ１　Ｓ２…Ｓ　，０）　ｉｓ　ｔｈｅ　ｒｅｑｕｉｒｅｄ　ｐａｔｈ．　Ｎｏｗ，ｗｅ　ａｒｅ　ｒｅａｄｙ　ｔｏ　ｃｈａｒａｃｔｅｒｉｚｅ　２－ｅｘｔｅｎｄａｂｌｅ　ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐｓ．Ｌｅｔ　Ｄ　一　＜ｎ，ｚ　ｌ　ｎ　＝＝＝ｚ　一１，ｚ～　船一ａ一　）ｂｅ　ａ　ｄｉｈｅｄｒａｌ　ｇｒｏｕｐ．　Ｐｒｏｏｆ　ｏｆ　ｔｈｅ　ｔｈｅｏｒｅｍ　１　Ｎｅｃｅｓｓｉｔｙ：Ａ　２－ｅｘｔｅｎｄａｂｌｅ　ｇｒａｐｈ　ｍｕｓｔ　ｂｅ　３－ｃｏｎｎｅｃｔｅｄ　ｂｙ　ｌｅｍｍａ　１．Ｔｈｉｓ　ｉｍｐｌｉｅｓ　ｔｈａｔ　ｌ　Ｓ　ｌ≥３　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｌｅｍｍａ　２，ａｓ　ＢＣ（Ｇ，Ｓ）ｉｓ　ａ　ｒｅｇｕｌａｒ　ｇｒａｐｈ　ｗｉｔｈ　ｄｅｇｒｅｅ　ｌ　Ｓ　１．　Ｓｕｆｆｉｃｉｅｎｃｙ：Ｌｅｔ　ｌ　Ｓ　ｌ≥３　ａｎｄ　ｔａｋｅ　ｔｗｏ　ｅｄｇｅｓ　ｅ１一（ｇ，０）（ｓ１ｇ，１）ａｎｄ　ｅ２一（　，０）（ｓ２ｈ，１）ｉｎ　ＢＣ（Ｇ，Ｓ）ｓｕｃｈ　ｔｈａｔ　ｇ≠ｈ　ａｎｄ　ｓ１ｇ≠ｓ２ｈ．Ｉｆ　ｓ１一ｓ２　ｔｈｅｎ｛（ｆ，Ｏ）（５１ｔ，１）ｌ　Ｅ　Ｄ　｝ｉｓ　ａ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｏｆ　ＢＣ（Ｇ，Ｓ）ｃｏｎｔａｉｎｉｎｇ　ｅｌ　ａｎｄ　ｅ２．Ｔｈｕｓ，ａｓｓｕｍｅ　ｔｈａｔ　ｓ１≠ｓ２．Ｔｏ　ｆｉｎｉｓｈ　ｔｈｅ　ｐｒｏｏｆ　ｏｆ　ｔｈｅ　２－ｅｘｔｅｎｄａｂｉｌｉｔｙ，ｓｉｎｃｅ　１∈Ｓ，ｗｅ　ｏｎｌｙ　ｎｅｅｄ　ｔｏ　ｆｉｎｄ　５２８　浙江大学学报（理学版）　第４２卷　ａｎ　ｅｄｇｅ　ｓｅｔ　Ｅ　ｗｉｔｈ　ｓｍａｌｌ　ｃａｒｄｉｎａｌｉｔｙ　ｓｕｃｈ　ｔｈａｔ　Ｅ　Ｕ｛（￡，０）（ｔ，１）ｌ　ｔ∈Ｄ　，（￡，０）ａｎｄ（　，１）ａｒｅ　ｎｏｔ　ｉｎｃｉｄｅｎｔ　ｔｏ　ａｎｙ　ｅｄｇｅ　ｉｎ　Ｅ｝ｉｓ　ａ　ｐｅｒｆｅｃｔ　ｍａｔｃｈｉｎｇ　ｏｆ　ＢＣ（Ｇ，Ｓ）ｃｏｎｔａｉｎｉｎｇ　ｅ１　ａｎｄ　ｅ２．Ｉｎ　ｗｈａｔ　ｆｏｌｌｏｗｓ　ｗｅ　ｃｏｎｓｔｒｕｃｔ　Ｅ．Ｔｈｅｒｅ　ａｒｅ　ｔｈｒｅｅ　ｃａｓｅｓ　ｔｏ　ｃｏｎｓｉｄｅｒ．　Ｃａｓｅ　１　ｓ１＝＝＝口　＿ｚ　ａｎｄ　ｓ２一ａｌｘ　ｗｉｔｈ　０≤ｉ，Ｊ≤　一　１．Ｉｆ　ｈ≠ａ＇ｇ　ａｎｄ　ａｊｘｇ，ｔａｋｅ　Ｅ一｛ｅ１，ｅ２，（ｎ　ｘｇ，０）（ｇ，１），（口　ｘｈ，Ｏ）（　，１））．　Ｉｆ　ｈ—ａｉｘｇ　ｏｒ口　ｘｇ，ｔａｋｅ　Ｅ一｛（（　２　ｓ２）ｍｇ，０）（ｓｌ（ｓ２　ｓ１）ｍｇ，１），（ｓｌ（ｓ２　５１）　ｇ，０）×　（（ｓ２　ｓ１）　ｇ，１｝ｌ　０≤ｍ＜０（ｓ２　ｓ１）），　ｗｈｅｒｅ　ｏ（ｓ２　ｓ１）ｄｅｎｏｔｅｓ　ｔｈｅ　ｏｒｄｅｒ　ｏｆ　ｓ２　ｓ１　ｉｎ　Ｄ　．　Ｃａｓｅ　２　ｓＩ一＆　ａｎｄ　ｓ２一ａｊ　ｗｉｔｈ　０≤ｉ，Ｊ≤　一１．　Ｆｏｒ　ａ　＝１，ｔａｋｅ　Ｅ一｛ｅ１，ｅ２，（ａｊｘｈ，０）（　，１））．Ｆｏｒ　ａ　≠１，ｓｅｔ　Ｅｌ一｛ｅ１，（ｎ　ｇ，０）（口，。　ｘｇ，１），　（＆Ｊ－＇ｘｇ，Ｏ）（ｎ　ｘｇ，１），（ｎ　ｘｇ，Ｏ）（ｇ，１）｝．　Ｎｏｔｅ　ｔｈａｔ　ｈ≠ｇ　ａｎｄ　ｎ　ｇ≠ａｊｘｈ．Ｔｈｕｓ，ｈ≠ｇ　ａｎｄ　ａｊ　ｉｘｇ．Ｉｔ　ｆｏｌｌｏｗｓ　ｔｈａｔ　ｅｉｔｈｅｒ　ｅ２∈Ｅ１　ｏｒ　ｅ２　ｈａｓ　ｎｏ　ｃｏｍｍｏｎ　ｖｅｒｔｅｘｗｉｔｈＥ】．Ｉｆ　ｅ２∈Ｅ１，ｔａｋｅＥ—Ｅ１，ａｎｄ　ｉｆ　ｅ２　Ｅ１，ｔａｋｅ　Ｅ—Ｅ１　Ｕ｛ｅ２，（ａｊｘｈ，０）（　，１））．　Ｃａｓｅ　３　５１一ａ　ａｎｄ　５２一ｎ　ｗｉｔｈ　０≤ｉ，Ｊ≤　一１．　Ｓｉｎｃｅ（Ｓ＞一Ｄ　，ｔｈｅｒｅ　ｅｘｉｓｔｓ　ａｎ　ｉｎｖｏｌｕｔｉｏｎ　ｉｎ　Ｓ，　ｓａｙ　ａｋ３ｃ　ｗｉｔｈ　０≤ｋ≤　—１．Ｆｏｒ　ａ　一１，ｗｅ　ｈａｖｅ　ａ　≠　１　ｓｉｎｃｅ　８ｌ≠ｓｚ．Ｉｆ　ｈ≠ａｋｘｇ　ａｎｄ　ａｋ－ｉｘｇ，ｔａｋｅ　Ｅ一｛ｅ１，（ｎ　ｇ，Ｏ）（口　一　ｘｇ，１），　（口　）ｘｇ，Ｏ）（ｎ　ｘｇ，１），（ｎ　ｘｇ，０）（ｇ，１）｝，　ａｎｄ　ｉｆ　ｈ—ａｋｘｇ　ｏｒ　ａｋ￣ｘｇ，ｔａｋｅ　Ｅ一｛（（ｎ　）　ｇ，Ｏ）（（ｎ　）　ｇ，１）ｌ　０≤ｍ＜０（口　）｝．　Ｆｏｒ　ａ　≠１，ｓｅｔ　Ａ一｛ｇ，ａｉｇ，ａｋｘｇ，ａｋ－ｉｘｇ｝，　Ｂ一｛ｈ，ｄ　，ａｋｘｈ，ａｋ－Ｊｘｈ｝，　Ｅｌ一｛ｅ１，（ｎ　ｇ，０）（ｎ　～ｘｇ，１），（＆　ｘｇ，Ｏ）（以　ｘｇ，１），　（ｎ　ｘｇ，０）（ｇ，１）｝，　Ｅ２一｛ｅ２，（ｎ　，０）（ａｋ－Ｊｘｈ，１），（＆　ｘｈ，０）（＆　ｘｈ，１），　（ｎ　ｘｈ，０）（　，１））．　Ａｓｓｕｍｅ　ｔｈａｔ　Ａ　Ｎ　Ｂ一　．Ｔｈｅｎ　ｔａｋｅ　Ｅ—Ｅｌ　Ｕ　Ｅ２．Ｔｈｕｓ，ａｓｓｕｍｅ　ｔｈａｔ　Ａ　Ｎ　Ｂ≠ｊ２『．Ｉｎ　ｔｈｉｓ　ｃａｓｅ，　ｈ—ａｌｇ，ａｋｘｇ，ａｋ　ｉｘｇ，ａ－Ｊｇ，ａｋ　Ｊｘｇ　ｏｒ　ａｋ－－ｉ－－ｊｘｇ　ｂｅｃａｕｓｅ　ｇ≠ｈ，ａｋｘｇ≠ａｋｘｈ　ａｎｄ　ａ＇ｇ≠ａｓｈ．Ｉｆ　ｈ—　ａ　ｇ　ｏｒ　ａｋ－－ｉ－ｊｘｇ，ｔａｋｅ　Ｅ一｛ｅ１，（ｎ　ｇ，０）（ｄ＋Ｊｇ，１），（ａｉ＋ｊｇ，Ｏ）（ｎ　ｘｇ，１），　（“　ｘｇ，０）（ｎ　ｘｇ，１），　（口　ｘｇ，Ｏ）（Ⅱ　ｘｇ，１），（口　ｘｇ，Ｏ）（ｇ，１）｝．　Ｉｆ　ｈ—ａｋｘｇ　ｏｒ　ａ　ｊｇ，ｔａｋｅ　Ｅ一｛ｅｌ，（ｎ　ｇ，０）（“　ｘｇ，１），　（口　ｘｇ，０）（口　ｘｇ，１），（口　ｘｇ，０）（ｎ　＋Ｊｓｃｇ，１），　（ａ　＋Ｊｘｇ，０）（Ⅱ　ｇ，１），（ｎ一　ｇ，０）（ｇ，１）｝．　Ｉｆ　ｈ—ａｋ　ｉｘｇ．ｔａｋｅ　Ｅ一｛ｅ１，（以　ｇ，０）（ｎ　～ｘｇ，１），（　ｘｇ，０）（。　ｉ＋Ｊｘｇ，１），　（口　汁　ｘｇ，０）（Ⅱ　＋　ｘｇ，１），（ａ　＋Ｊｘｇ，０）（口一　ｇ，１），　（口－ｊｇ，０）（ｇ，１）｝．　Ｉｆ　ｈ—ａｋ　Ｊｘｇ，ｔａｋｅ　Ｅ一｛ｅｌ，（ｎ　ｇ，０）（以　＋　ｇ，１），（以计　ｇ，Ｏ）（乜　ｒ　ｘｇ，１），　（＆　一　ｘｇ，０）（以虹一　ｘｇ，１），（ｎ卜　ｘｇ，Ｏ）（口　ｘｇ，１），　（ａ　ｘｇ，０）（ｇ，１）｝．　参考文献（Ｒｅｆｅｒｅｎｃｅｓ）：　［１］ＰＩ　ｕＭＭＥＲ　Ｍ　Ｄ．Ｏｎ　—ｅｘｔｅｎｄａｂｌｅ　ｇｒａｐｈｓ［＝Ｊ］．Ｄｉｓ—　ｃｒｅｔｅ　Ｍａｔｈ，１９８０，３１：２Ｏ１—２１Ｏ．　［２２　ＰＬＵＭＭＥＲ　Ｍ　Ｄ．Ｍａｔｃｈｉｎｇ　ｅｘｔｅｎｓｉｏｎ　ａｎｄ　ｔｈｅ　ｇｅｎｕｓ　ｏｆ　ａ　ｇｒａｐｈ［Ｊ］．Ｊ　Ｃｏｍｂｉｎ　Ｔｈｅｏｒｙ：Ｓｅｒ　Ｂ，１９８８，４４：３２９—　３３７．　［３］ＰＬＵＭＭＥＲ　Ｍ　Ｄ．Ｍａｔｃｈｉｎｇ　ｅｘｔｅｎｓｉｏｎ　ｉｎ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈｓ　［Ｊ］．Ｃｏｎｇｒ　Ｎｕｍｅｒ，１９８６，５４：２４５—２５８．　［４］　ＣＨＡＮ　０，ＣＨＥＮ　Ｃ　Ｃ，ＹＵ　Ｑ　Ｌ．Ｏｎ　２－ｅｘｔｅｎｄａｂｌｅ　ａｂｅ—　ｌｉａｎ　Ｃａｙｌｅｙ　ｇｒａｐｈｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈ，１９９５，１４６：１９—３２．　Ｅ５］ｘｕ　Ｍ　Ｙ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　Ｆｉｎｉｔｅ　Ｇｒｏｕｐｓ［Ｍ］．Ｂｅｉｊｉｎｇ：　Ｓｃｉｅｎｃｅ　Ｐｒｅｓｓ，１９９９．　－Ｉ６］　ＷＡＮＧ　Ａ　Ｍ，ＭＥＮＧ　Ｊ　ｘ．Ｈａｍｉｌｔｏｎｉａｎ　ｃｙｃｌｅｓ　ｉｎ　ｂｉ—　Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｆｉｎｉｔｅ　Ａｂｅｌｉａｎ　ｇｒｏｕｐｓ［Ｊ￣．Ｊｏｕｒｎａｌ　ｏｆ　ｘｉｎｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ，２００６，２３：　１５６—１５８．　［７］　ＺＯＵ　Ｈ，ＭＥＮＧ　Ｊ　Ｘ．Ｓｏｍｅ　ａｌｇｅｂｒａｉｃ　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｂｉ　Ｃａｙｌｅｙ　ｇｒａｐｈｓ［Ｊ］．Ａｃｔａ　Ｍａｔｈｅｍａｔｉｃａ　Ｓｉｎｉｃａ：Ｃｈｉｎｅｓｅ　Ｓｅｒｉｅｓ，２００７，５０（５）：１０７５　１０８０．　ｆ８］ＬＵＯ　Ｙ　Ｆ，ＧＡＯ　Ｘ．Ｏｎ　ｔｈｅ　ｅｘｔｅｎｄａｂｉｌｉｔｙ　ｏｆ．ｂｉ—Ｃａｙｌｅｙ　ｇｒａｐｈｓ　ｏｆ　ｆｉｎｉｔｅ　Ａｂｅｌｉａｎ　ｇｒｏｕｐｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈ，　２００９，３０９：５９４３—５９４９．　［９］ＨＡＲＡＲＹ　Ｆ．Ｇｒａｐｈ　Ｔｈｅｏｒｙ［Ｍ］．ＭＡ：Ａｄｄｉｓｏｎ—ｗｅｓ—　ｌｅｙ，１９６９．　［１Ｏ］　ＷｌＩ　ＳＯＮ　Ｒ　Ｊ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　Ｇｒａｐｈ　ＴｈｅＯｒｙ［Ｍ］．　Ｎｅｗ　Ｙｏｒｋ：Ｌｏｎｇｍａｎ　Ｉｎｃ，１９８２．