An Efficient Algorithm to Test Forcibly-connectedness of Graphical Degree Sequences

DOI10.20429/TAG.2018.050202zbMATH Open1416.05073arXiv1803.00673OpenAlexW2962787338WikidataQ129130847 ScholiaQ129130847MaRDI QIDQ5225547FDOQ5225547

Authors:

Publication date: 22 July 2019

Published in: Theory and Applications of Graphs (Search for Journal in Brave)

Abstract: We present an algorithm to test whether a given graphical degree sequence is forcibly connected or not and prove its correctness. We also outline the extensions of the algorithm to test whether a given graphical degree sequence is forcibly $k$-connected or not for every fixed $kge2$. We show through experimental evaluations that the algorithm is efficient on average, though its worst case run time is probably exponential. We also adapt Ruskey et al's classic algorithm to enumerate zero-free graphical degree sequences of length $n$ and Barnes and Savage's classic algorithm to enumerate graphical partitions of even integer $n$ by incorporating our testing algorithm into theirs and then obtain some enumerative results about forcibly connected graphical degree sequences of given length $n$ and forcibly connected graphical partitions of given even integer $n$. Based on these enumerative results we make some conjectures such as: when $n$ is large, (1) almost all zero-free graphical degree sequences of length $n$ are forcibly connected; (2) almost none of the graphical partitions of even $n$ are forcibly connected.

Full work available at URL: https://arxiv.org/abs/1803.00673

Recommendations

• Forcibly-biconnected Graphical Degree Sequences: Decision Algorithms and Enumerative Results
• On forcibly connected graphic sequences
• Efficient counting of degree sequences
• Forcibly bipartite and acyclic (uni-)graphic sequences
• On \(O(n \log \log n)\) time algorithm for constructing a graph of maximum connective with prescribed degrees.

zbMATH Keywords

graphical partitiongraphical degree sequenceco-NPforcibly $k$-connectedforcibly connected

Mathematics Subject Classification ID

Vertex degrees (05C07) Connectivity (05C40)

Cited In (4)

• Rao's theorem for forcibly planar sequences revisited
• A new sufficient degree condition for a graphic sequence to be forcibly \(k\)-edge-connected
• On \(O(n \log \log n)\) time algorithm for constructing a graph of maximum connective with prescribed degrees.
• Forcibly-biconnected Graphical Degree Sequences: Decision Algorithms and Enumerative Results

This page was built for publication: An Efficient Algorithm to Test Forcibly-connectedness of Graphical Degree Sequences

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