Degree sequences and edge connectivity

DOI10.1007/S12188-016-0171-0MaRDI QIDQ1688269zbMATH OpenOpenAlexFDO

Authors Matthias Kriesell

Publication date 5 January 2018

Published in Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s12188-016-0171-0

zbMATH Keywords

bigraphical sequence pairBondy-Chvátal type conditiondegree sequenceedge connectivitygraphical partition

Mathematics Subject Classification ID

Vertex degrees (05C07) Connectivity (05C40)

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)].

Recommendations

• Conditions for families of disjoint \(k\)-connected subgraphs in a graph
• 3-connected graphs and their degree sequences
• Component order connectivity and vertex degrees
• A sharp refinement of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences
• A generalization of an edge-connectivity theorem of Chartrand
• scientific article; zbMATH DE number 1062587
• Connectivity keeping edges in graphs with large minimum degree
• scientific article; zbMATH DE number 894357
• scientific article; zbMATH DE number 1933046
• On \(O(n \log \log n)\) time algorithm for constructing a graph of maximum connective with prescribed degrees.

Cites work

• A theorem on flows in networks
• Combinatorial Properties of Matrices of Zeros and Ones
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3293646 (Why is no real title available?)
• On Hamilton's ideals
• Sufficient degree conditions for k-edge-connectedness of a graph
• The strongest monotone degree condition for \(n\)-connectedness of a graph

Cited in

(10)

• Potentially 2-connected integer pair sequences
• A new sufficient degree condition for a graphic sequence to be forcibly \(k\)-edge-connected
• On forcibly \(k\)-connected and forcibly \(k\)-arc-connected digraphic sequences
• scientific article; zbMATH DE number 6386250 (Why is no real title available?)
• Sufficient degree conditions for k-edge-connectedness of a graph
• Degree sequences of geometric preferential attachment graphs
• Best monotone degree conditions for graph properties: a survey
• Edge realizability of connected simple graphs
• Component order connectivity and vertex degrees
• On forcibly k-connected uniform hypergraphic sequences

This page was built for publication: Degree sequences and edge connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688269)