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-...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.展开更多
基金supported by National Natural Science Foundation of China (Grant No.11271012)the Fundamental Research Funds for the Central Universities (Grant Nos.2011JBM127,2011JBZ012)+1 种基金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.
