Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
type: Item
instance of: scholarly article
title: Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
zbMATH Open document ID: 0591.05047
DOI: 10.1016/S0195-6698(85)80048-2
author: W. Mader
published in: European Journal of Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: A graph G is called critically n-connected if G is n-connected and for any vertex x of G the induced subgraph G-\(\{\) \(x\}\) is n-1 connected. Let T be a separating set in G of order n then any union of components of G-T is called a fragment of G. The author proved that every finite, non- complete, critically n-connected graph contains two disjoint fragments F such that \(| F| \leq n/2\). This implies the results of \textit{Y. O. Hamidoune} [Discrete Math. 32, 257-262 (1980; Zbl 0452.05043)] and \textit{H. J. Veldman} [Discrete Math. 44, 105-110 (1983; Zbl 0542.05043)] that each such graph encloses two vertices of degree \(\leq (3/2)n-1\). Secondly the author shows that there are at least four disjoint fragments of any order in such a graph. This improves a result of \textit{L. Nebeský} [J. Graph Theory 1, 69-74 (1977; Zbl 0359.05030)] on the existence of 4 vertices of degree \(\geq 2\) in a critically 2-connected graph.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3948317
zbMATH Keywords: critically n-connected graph
zbMATH Keywords: disjoint fragments
reviewed by: Michael Hager
MaRDI profile type: Publication
cites work: Critically n-Connected Graphs
cites work: A Note on k-Critically n-Connected Graphs
cites work: Q3879253
cites work: On critically h-connected simple graphs
cites work: Eine Eigenschaft der Atome endlicher Graphen
cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
cites work: Über minimal n-fach zusammenhängende, unendliche Graphen und ein Extremalproblem. (On minimal n-fold connected infinite graphs and an extremal problem)
cites work: Q3220626
cites work: On induced subgraphs of a block
cites work: Non-\(\kappa\)-critical vertices in graphs
description: scientific article; zbMATH DE number 3948317