Premium
Minimally ( k, k )‐edge‐connected graphs
Author(s) -
Hennayake Kamal,
Lai HongJian,
Li Deying,
Mao Jingzhong
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10132
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , enhanced data rates for gsm evolution , symmetric graph , connectivity , line graph , voltage graph , computer science , artificial intelligence
For an integer l > 1, the l ‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is ( k , l )‐edge‐connected if the l ‐edge‐connectivity of G is at least k . In this paper, we present a structural characterization of minimally ( k , k )‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003