Generalizaions of critical connectivity of graphs
type: Item
instance of: scholarly article
title: Generalizaions of critical connectivity of graphs
zbMATH Open document ID: 0664.05028
DOI: 10.1016/0012-365X(88)90216-6
author: W. Mader
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Let \(\mu\) (G) denote the connectivity of a graph G. If T is a vertex separating set of G with \(| T| =\mu (G)\), then T is called a smallest separating set of G. Let \({\mathfrak T}(G)\) be the collection of all subgraphs of G induced by the smallest separating sets of G. For \(T\in {\mathfrak T}(G)\), a T-fragment is a union of at least one, but not all components of G-T. A subgraph F of G that is a T-fragment for some \(T\in {\mathfrak T}(G)\) is called a fragment of G. For a graph G, let \({\mathfrak S}\) be a non-empty set of subsets of V(G) and define \({\mathfrak T}_{{\mathfrak S}}(G)=\{T\in {\mathfrak T}(G)|\) there is an \(S\in {\mathfrak S}\) with \(S\subseteq T\}\). An \({\mathfrak S}\)-fragment of G is a T-fragment of G for some \(T\in {\mathfrak T}_{{\mathfrak S}}(G)\). An \({\mathfrak S}\)-fragment of G that does not properly contain another \({\mathfrak S}\)-fragment is called an \({\mathfrak S}\)-end of G while one with the smallest number of vertices is called an \({\mathfrak S}\)-atom. The order of an \({\mathfrak S}\)-atom is denoted by \(a_{{\mathfrak S}}(G)\). The graph G is called \({\mathfrak S}\)-critical if and only if every \(S\in {\mathfrak S}\) is contained in some \(T\in {\mathfrak T}(G)\) and for every \({\mathfrak S}\)-fragment F, there is a \(T\in {\mathfrak T}(G)\) such that \(T\cap F\neq \emptyset\) and \(T\cap (F\cup T_ F)\) contains some \(S\in {\mathfrak S}\) (where \(T_ F\) is the unique element of \({\mathfrak T}(G)\) that determines the fragment F). It is shown that if A is an \({\mathfrak S}\)-atom of G for which there exists a \(T\in {\mathfrak T}(G)\) with \(T\cap A=\emptyset\) and such that \(T\cap (A\cup T_ A)\) contains \(S\in {\mathfrak S}\), then \(A\subseteq T\) and \(| A| \leq | T-T_ A|\). As a consequence it is deduced that for every \({\mathfrak S}\)- critical graph G, \(a_{{\mathfrak S}}(G)\leq \mu (G)\) holds and that every \({\mathfrak S}\)-critical graph is 2-connected. For \(T\subseteq V(G)\) let \(N(T;G)=\cu…
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4085683
zbMATH Keywords: connectivity
zbMATH Keywords: \({\mathfrak S}\)-fragment
zbMATH Keywords: \({\mathfrak S}\)-end
zbMATH Keywords: \({\mathfrak S}\)-atom
zbMATH Keywords: contraction-critical
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4]\)
cites work: Contractible edges in triangle-free graphs
cites work: Q4166780
cites work: Untersuchungen über minimale \(n\)-fach zusammenhängende Graphen
cites work: On multiply critically h-connected graphs
cites work: Eine Eigenschaft der Atome endlicher Graphen
cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
cites work: Endlichkeitssätze für k-kritische Graphen
cites work: Q3220626
cites work: Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
cites work: Über \((k+1)\)-kritisch \((2k+1)\)-fach zusammenhängende Graphen. (On \((k+1)\)-critically \((2k+1)\)-connected graphs)
cites work: On k-critical, n-connected graphs
cites work: Nonseparating cycles inK-Connected graphs
cites work: Q3284374
description: scientific article; zbMATH DE number 4085683