|国家预印本平台
首页|二部和非二部三正则点可迁图的 2-可扩性

二部和非二部三正则点可迁图的 2-可扩性

2-extendability of bipartite and cubic non-bipartite vertex-transitive graphs

中文摘要英文摘要

han 等刻画了 2-可扩可交换群上的凯莱图, 并且提出了刻画 2-可扩凯莱图的问题. 我们首先证明了一个二部凯莱图 (点可迁图) 是 2-可扩的当且仅当它不同构于圈. 对非二部凯莱图而言, 当它的最小度至少为 5 时, 它是 2-可扩的. 我们接着刻画了 2-可扩的非二部三正则凯莱图并且得到如下结果: 一个围长为 $g$ 的三正则非二部凯莱图是 2-可扩的当且仅当 $ggeq 4$ 并且不同构于 $Z_{4n}(1,4n-1,2n)$ 或者 $Z_{4n+2}(2,4n,2n+1)$, $ngeq 2$. 实际上, 我们证明了一个更强的结论, 即一个围长为 $g$ 的三正则非二部点可迁图是 2-可扩的当且仅当 $ggeq 4$ 并且不同构于 $Z_{4n}(1,4n-1,2n)$, $Z_{4n+2}(2,4n,2n+1)$, $ngeq 2$, 或者 Petersen 图.

han et al. classified the2-extendable abelian Cayley graphs and posed the problem ofcharacterizing all 2-extendable Cayley graphs. We first show that a connected bipartite Cayley (vertex-transitive) graph is 2-extendable if and only if it is not a cycle. %Thereafter, the 2-extendability of Cayley graphs on specific groups, such as Dihedral group, Dicylic group, Generalized xing{generalized} dihedral group, Quasi-abelian groups and etc, has been investigated. We first show that all $k$-regular ($kgeq 3$) bipartite Cayley graphs are 2-extendable. It is known that a non-bipartite Cayley (vertex-transitive) graph is 2-extendable when it is of minimum degree at least 5. %Hence the 2-extendability of Cayley graphs of minimum degrees 3 and 4 are left.We next characterize all 2-extendable cubic non-bipartite Cayley graphs and obtain that: a cubic non-bipartite Cayley graph with girth $g$ is2-extendable if and only if $ggeq 4$ and it doesn't isomorphic to $Z_{4n}(1,4n-1,2n)$ or $Z_{4n+2}(2,4n,2n+1)$ with $ngeq 2$. Indeed, we prove a more stronger result that a cubic non-bipartite vertex-transitive graph with girth $g$ is2-extendable if and only if $ggeq 4$ and it doesn't isomorphic to $Z_{4n}(1,4n-1,2n)$ or $Z_{4n+2}(2,4n,2n+1)$ with $ngeq 2$ or the Petersen graph.

高兴、李秋丽

数学

凯莱图点可迁图2-可扩性匹配边连通性.

ayley graphvertex-transitive graph$2$-extendablilitymatchingedge-connectivity.

高兴,李秋丽.二部和非二部三正则点可迁图的 2-可扩性[EB/OL].(2016-12-09)[2025-08-11].http://www.paper.edu.cn/releasepaper/content/201612-180.点此复制

评论