Paper Info
Title
The Edge-Count Criterion for Graphic Lists.
Abstract
We give a new short proof of Koren's characterization of graphic lists, extended to multigraphs with bounded multiplicity p, 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, Sigma(i is an element of I) d(i) + Sigma(j is an element of J)[p(n - 1) - d(j)] >= p broken vertical bar I broken vertical bar broken vertical bar J broken vertical bar. 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.
Year
DOI
Venue
2010
10.37236/485
ELECTRONIC JOURNAL OF COMBINATORICS
Keywords
DocType
Volume
2
Journal
17
Issue
ISSN
Citations 
1.0
1077-8926
0
PageRank 
References 
Authors
0.34
3
2
Name
Order
Citations
PageRank
Garth Isaak117224.01
Douglas B. West21176185.69