On Minimum Critically $n$-Edge-Connected Graphs

Let $n$ be an integer with $n\geqq 2$. A graph $G$ is called critically $n$-edge-connected if the edge-connectivity $\lambda (G) = n$ and for any vertex $v$ of $G$, $\lambda (G - \upsilon ) = n - 1$. The sizes of critically $n$-edge-connected graphs are important and interesting in applications in c...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 1987-10, Vol.8 (4), p.659
Main Authors: Cozzens, Margaret B, Wu, Shu-Shih Y
Format: Article
Language:English
Subjects:
Applied mathematics
Connectivity
Graphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let $n$ be an integer with $n\geqq 2$. A graph $G$ is called critically $n$-edge-connected if the edge-connectivity $\lambda (G) = n$ and for any vertex $v$ of $G$, $\lambda (G - \upsilon ) = n - 1$. The sizes of critically $n$-edge-connected graphs are important and interesting in applications in communication networks. The maximum graphs with this property have been characterized [2]. In this paper, we first discuss some properties of minimum graphs, then show that the problem of finding a minimum critically $n$-edge-connected spanning subgraph of a given graph $G$ is NP-complete.
ISSN:0895-4798
1095-7162
DOI:10.1137/0608054