Semester

Fall

Date of Graduation

1998

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai.

Abstract

The edge-connectivity l of a connected graph is the minimum number of edges whose deletion produces a graph with two components. For an integer l > 1, the l-edge connectivity of a graph with | V| ≥ l, denoted by l l, is the smallest number of edges whose removal results in a graph with l components. The strength of G, denoted by l&d1; (G), is the maximum value of l (H), where H runs over all subgraphs of G. In this dissertation we study lower bounds of l l and optimal graphs that reach the lower bound. Former results in [SIAM J. Appl. Math., 34 (1978) 657--665] are extended. We also present an optimal model of interconnection network G with a given l l(G) such that l (G) is maximized while |E( G)| is minimized. Further we investigate the relationship between lambda l and l&d1; , especially the extremal cases. A structural characterization of the extremal when l 2 = 2 and arbitrary l ≥ 2 is found.;For an integer k > 1, a graph is (k, l)-edge-connected if the l-edge-connectivity of G is at least k. A graph G is minimally ( k, l)-edge connected if l l(G) ≥ k but for edge e ∈ E(G), l l(G - e ) < k. In this work we present a structural characterization of minimally (k, k)-edge-connected graph, for graphs without bridges. As a result, former characterization of minimally (2,2)-edge connected graph in [J. of Graph Theory, 3 (1979) 15--22) are extended.

Download

Share

COinS