Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651043 | Discrete Mathematics | 2007 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ou Jianping,