Super Cyclically Edge-connected Vertex-transitive Graphs of Girth at Least 5  

作　　者：Jin Xin ZHOU Yan Tao LI 

机构地区：[1]Department of Mathematics,Beijing Jiaotong University [2]Department of Basic Teaching,Beijing Union University

出　　处：《Acta Mathematica Sinica,English Series》2013年第8期1569-1580,共12页数学学报（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No.11271012);the Fundamental Research Funds for the Central Universities (Grant Nos.2011JBM127,2011JBZ012);supported by National Natural Science Foundation of China (Grant No.11101035);the Subsidy for Outstanding People of Beijing (Grant No.2011D005022000005)

摘　　要：A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.： Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549–562 （2011）], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.： Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549–562 （2011）], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.

关 键 词：Cyclic edge-cut cyclic edge-connectivity super cyclically edge-connected vertex-transit-ive graphs 

分 类 号：O157.5[理学—数学] TQ545[理学—基础数学]