Summary: We give a new short proof of Koren's characterization of graphic lists, extended to multigraphs with bounded multiplicity \(,\) called \(p\)-graphs. The Edge-Count Criterion (ECC) for an integer \(n\)-tuple \(d\) and integer \(p\) is the statement that for all disjoint sets \(I\) and \(J\) of indices, \[ \sum_{i\in I}d_i+ \sum_{j\in J}[p(n-1)-d_j]\geq p|I||J|. \] An integer list \(d\) is the degree list of a \(p\)-graph if and only if it has even sum and satisfies ECC. Analogous statements hold for bipartite or directed graphs, and an old characterization of degree lists of signed graphs follows as a corollary of the extension to multigraphs.
- A short constructive proof of the Erdős-Gallai characterization of graphic lists
- Seven criteria for integer sequences being graphic
- Degree sequences in graphs
- Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps
- Constructive extensions of two results on graphic sequences
This page was built for publication: The edge-count criterion for graphic lists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612910)
