It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed...It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed that any λ 4-connected graph G with order at least 11 has the property λ 4 (G)≤ξ 4 (G).In this paper,by investigating some structure properties of a λ m-connected graph G with λ m (G) 】 ξ m (G),we obtain easily the above result.Furthermore,we show that every λ m-connected graph G with order greater than m(m-1) satisfies the inequality λ m (G)≤ξm (G) for m≥5.And by constructing some examples,we illustrate that our conditions are the best possible.展开更多
A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connecte...A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].展开更多
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.10831001)
文摘It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed that any λ 4-connected graph G with order at least 11 has the property λ 4 (G)≤ξ 4 (G).In this paper,by investigating some structure properties of a λ m-connected graph G with λ m (G) 】 ξ m (G),we obtain easily the above result.Furthermore,we show that every λ m-connected graph G with order greater than m(m-1) satisfies the inequality λ m (G)≤ξm (G) for m≥5.And by constructing some examples,we illustrate that our conditions are the best possible.
基金Supported by National Natural Science Foundation of China(Grant No.11001287)Science Foundation Chongqing Education Committee(Grant Nos.KJ100725 and KJ120731)
文摘A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].
基金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.
