Article ID Journal Published Year Pages File Type
4651043 Discrete Mathematics 2007 9 Pages PDF
Abstract

An edge cut of a connected graph is 4-restricted if it disconnects this graph with each component having order at least four. The size of minimum 4-restricted edge cuts of graph G   is called its 4-restricted edge connectivity and is denoted by λ4(G)λ4(G). Let ξ4(G)=min{∂(F):Fis a connected vertex-induced subgraph of order four of graphG}, where ∂(F)∂(F) denotes the number of edges of graph G with exactly one endpoint in F  . For connected graphs that contain 4-restricted edge cuts, ξ4(G)ξ4(G) is proved to be an upper bound on λ4(G)λ4(G) if G has order at least 11. If G is a k  -regular vertex-transitive graph of girth at least five, then λ4(G)=ξ4(G)λ4(G)=ξ4(G) when k⩾4k⩾4.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,