Sufficient Conditions for Graphicality of Bidegree Sequences

DOI10.1137/15M102527XzbMATH Open1352.05077arXiv1511.02411OpenAlexW2963971663MaRDI QIDQ2953405

Author name not available (Why is that?)

Publication date: 4 January 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: There are a variety of existing conditions for a degree sequence to be graphic. When a degree sequence satisfies any of these conditions, there exists a graph that realizes the sequence. We formulate several novel sufficient graphicality criteria that depend on the number of elements in the sequence, corresponding to the number of nodes in an associated graph, and the mean degree of the sequence. These conditions, which are stated in terms of bidegree sequences for directed graphs, are easier to apply than classic necessary and sufficient graphicality conditions involving multiple inequalities. They are also more flexible than more recent graphicality conditions, in that they imply graphicality of some degree sequences not covered by those conditions. The form of our results will allow them to be easily used for the generation of graphs with particular degree sequences for applications.

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

zbMATH Keywords

Could not fetch data.

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Special sequences and polynomials (11B83) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• A note on the characterization of digraphic sequences
• A theorem on flows in networks
• Zero-one matrices with zero trace
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• Contributions to the theory of graphic sequences
• On the realization of a (p,s)-digraph with prescribed degrees
• Graphical basis partitions
• Efficient generation of graphical partitions
• Confirming two conjectures about the integer partitions
• Connected components in random graphs with given expected degree sequences
• A recurrence for counting graphical partitions
• Reduced criteria for degree sequences
• A sharp refinement of a result of Zverovich-Zverovich
• On graphical partitions
• On the degrees of the vertices of a directed graph
• Algorithms for constructing graphs and digraphs with given valences and factors
• A remark concerning graphical sequences
• A note on regular Ramsey graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• Properties of a Class of (0,1)-Matrices Covering a given Matrix
• Maximum-Entropy Networks
• Constructing and sampling directed graphs with given degree sequences
• Directed random graphs with given degree distributions

Related Items (9)

Planar bipartite biregular degree sequences ⋮ On vertex-weighted realizations of acyclic and general graphs ⋮ Graph realizations: maximum degree in vertex neighborhoods ⋮ Degree realization by bipartite multigraphs ⋮ An extension of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences ⋮ Graphic Sequences Have Realizations Containing Bisections of Large Degree ⋮ Composed degree-distance realizations of graphs ⋮ Composed degree-distance realizations of graphs ⋮ Relaxed and approximate graph realizations

This page was built for publication: Sufficient Conditions for Graphicality of Bidegree Sequences

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