Search

Abstract: For a connected graph , an edge set is a -restricted edge-cut if is disconnected and every component of has at least vertices. Graphs that allow -restricted edge-cuts are called -connected. The -edge-degree of a graph  is the minimum number of edges between a connected subgraph of order and its complement . A -connected graph is called -optimal if its -restricted edge-connectivity equals its minimum -edge-degree and super- if every minimum -restricted edge-cut isolates a connected subgraph of order . In this paper we consider the cases and . For triangle-free graphs that are not -optimal, we establish lower bounds for the order of components left by a minimum -restricted edge-cut in terms of the minimum -edge-degree. Sufficient conditions for a triangle-free graph to be -optimal and super- follow. [Copyright &y& Elsevier]

Abstract: Let be a -connected graph. is called -optimal, if its -restricted edge-connectivity equals its minimum -edge degree.  is called super- if every -cut isolates a connected subgraph of order . Firstly, we give a lower bound on the order of -fragments in triangle-free graphs that are not -optimal. Secondly, we present an Ore-type condition for triangle-free graphs to be -optimal. Thirdly, we prove a lower bound on the order of -fragments in triangle-free -connected graphs, and use it to show that triangle-free graphs with high minimum degree are -optimal and super-. [Copyright &y& Elsevier]

Abstract: An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph is super restricted edge connected if contains an isolated edge for every minimum restricted edge cut of . It is proved in this paper that a connected regular edge-transitive graph of valency at least 3 is not super restricted edge connected if and only if it is either the three dimensional hypercube, or a tetravalent edge-transitive graph of girth 3 and of order at least 6. As a result, there are infinitely many -regular Hamiltonian graphs with which are not super restricted edge connected. This answers negatively a question in [J. Ou, F. Zhang, Super restricted edge connectivity of regular graphs, Graphs & Combin. 21 (2005) 459–467] regarding the relationship between restricted edge connected graphs and Hamiltonian graphs. [Copyright &y& Elsevier]