The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle
The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle
复制标题
DOI：
10.1007/s00373-010-0927-8
复制
发表时间：
2010-07
影响因子：
0.7
通讯作者：
Iwao Mizukai;Seiya Negami;Yusuke Suzuki
中科院分区：
文献类型：
--
作者：
Iwao Mizukai;Seiya Negami;Yusuke Suzuki
如果任何独立的边集扩展至完美匹配，则称图是可扩展的。我们将证明嵌入在射影平面上的每一个偶数阶 5 连通图和嵌入在环面和克莱因瓶上的每一个 6 连通图都是 2-可扩展的，并刻画 5-连通环形图的禁止结构是 2-可扩展的。
A graph is said to bek-extendableif any independent set ofkedges extends to a perfect matching. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable.