Degree sequences and edge connectivity
type: Item
instance of: scholarly article
title: Degree sequences and edge connectivity
zbMATH Open document ID: 1388.05040
author: Matthias Kriesell
published in: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
publication date: 2018-01-05T00:00:00Z
review text: For each positive integer \(k\), one can associate a finite list \(C\)(\(k\)) of Bondy-Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on \(n\) vertices with degree sequence at least \(d\) is \(k\)-edge-connected. These conditions are best possible in the sense that whenever one of them fails for \(d\) then there is a graph on \(n\) vertices with degree sequence at least \(d\) which is not \(k\)-edge-connected. In this connection, the author proves that \(C(k)\) is and must be large by showing that it contains \(p(k)\) many logically irredundant conditions, where \(p(k)\) is the number of partitions of \(k\). Furthermore, he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. It is also proved that any sublist equivalent to \(C(k)\) has length at least \(p(k)\), where \(p(k)\) is the number of partitions of \(k\), which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore,he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. Finally, he informally describes a simple and fast procedure which generates the list \(C(k)\). Specialized to \(k=3\), this verifies a conjecture of \textit{D. Bauer} et al. [Networks 54, No. 2, 95--98 (2009; Zbl 1207.05109)].
reviewed by: T. Tamizh Chelvam
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6822590
zbMATH Keywords: graphical partition
zbMATH Keywords: degree sequence
zbMATH Keywords: edge connectivity
zbMATH Keywords: Bondy-Chvátal type condition
zbMATH Keywords: bigraphical sequence pair
MaRDI profile type: Publication
full work available at URL: s12188-016-0171-0
OpenAlex ID: W2569644173
cites work: Sufficient degree conditions fork-edge-connectedness of a graph
cites work: The strongest monotone degree condition for \(n\)-connectedness of a graph
cites work: Q5576241
cites work: On Hamilton's ideals
cites work: Q5315023
cites work: A theorem on flows in networks
cites work: Combinatorial Properties of Matrices of Zeros and Ones
DOI: 10.1007/S12188-016-0171-0
Recommended article: Conditions for families of disjoint \(k\)-connected subgraphs in a graph
Recommended article: 3-connected graphs and their degree sequences
Recommended article: Q5252055
Recommended article: A sharp refinement of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences
Recommended article: A generalization of an edge-connectivity theorem of Chartrand
Recommended article: Q4355069
Recommended article: Connectivity keeping edges in graphs with large minimum degree
Recommended article: Q4882912
Recommended article: Q4405634
Recommended article: On \(O(n \log \log n)\) time algorithm for constructing a graph of maximum connective with prescribed degrees.
description: scientific article; zbMATH DE number 6822590