			Home About us Contact

Edge-connected Graphs (edge-connected + graph)

Distribution by Scientific Domains

Mathematics and Statistics	100%

Selected Abstracts

Sufficient conditions for a graph to be super restricted edge-connected

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2008
Shiying Wang
Abstract Restricted edge connectivity is a more refined network reliability index than edge connectivity. A restricted edge cut F of a connected graph G is an edge cut such that G - F has no isolated vertex. The restricted edge connectivity ,, is the minimum cardinality over all restricted edge cuts. We call G ,,-optimal if ,, = ,, where , is the minimum edge degree in G. Moreover, a ,,-optimal graph G is called a super restricted edge-connected graph if every minimum restricted edge cut separates exactly one edge. Let D and g denote the diameter and girth of G, respectively. In this paper, we first present a necessary condition for non-super restricted edge-connected graphs with minimum degree , , 3 and D , g , 2. Next, we prove that a connected graph with minimum degree , , 3 and D , g , 3 is super restricted edge-connected. Finally, we give some sufficient conditions on the conditional diameter and the girth for super restricted edge-connected graphs. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source]

Nowhere-zero 3-flows in locally connected graphs

JOURNAL OF GRAPH THEORY, Issue 3 2003
Hong-Jian Lai
Abstract Let G be a graph. For each vertex v ,V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k -edge-connected if for each vertex v ,V(G), Nv is k -edge-connected. In this paper we study the existence of nowhere-zero 3-flows in locally k -edge-connected graphs. In particular, we show that every 2-edge-connected, locally 3-edge-connected graph admits a nowhere-zero 3-flow. This result is best possible in the sense that there exists an infinite family of 2-edge-connected, locally 2-edge-connected graphs each of which does not have a 3-NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211,219, 2003 [source]

Connected (g, f)-factors

JOURNAL OF GRAPH THEORY, Issue 1 2002
M. N. Ellingham
Abstract In this paper we study connected (g, f)-factors. We describe an algorithm to connect together an arbitrary spanning subgraph of a graph, without increasing the vertex degrees too much; if the algorithm fails we obtain information regarding the structure of the graph. As a consequence we give sufficient conditions for a graph to have a connected (g, f)-factor, in terms of the number of components obtained when we delete a set of vertices. As corollaries we can derive results of Win [S. Win, Graphs Combin 5 (1989), 201,205], Xu et al. [B. Xu, Z. Liu, and T. Tokuda, Graphs Combin 14 (1998), 393,395] and Ellingham and Zha [M. N. Ellingham and Xiaoya Zha, J Graph Theory 33 (2000), 125,137]. We show that a graph has a connected [a, b]-factor (b>a,,,2) if the graph is tough enough; when b,,,a,+,2, toughness at least suffices. We also show that highly edge-connected graphs have spanning trees of relatively low degree; in particular, an m -edge-connected graph G has a spanning tree T such that degT (,),,,2,+,, degG(,)/m, for each vertex ,. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62,75, 2002 [source]