Geodesic
The edge-count criterion for graphic lists
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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, $\sum_{i\in I} d_i+\sum_{j\in J} [p(n-1)-d_j]\ge 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.
DOI : 10.37236/485
Classification : 05C07, 05C22
Mots-clés : graphic list, degree list, signed graphs 
@article{10_37236_485,
     author = {Garth Isaak and Douglas B. West},
     title = {The edge-count criterion for graphic lists},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/485},
     zbl = {1204.05038},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/485/}
}
TY  - JOUR
AU  - Garth Isaak
AU  - Douglas B. West
TI  - The edge-count criterion for graphic lists
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/485/
DO  - 10.37236/485
ID  - 10_37236_485
ER  - 
%0 Journal Article
%A Garth Isaak
%A Douglas B. West
%T The edge-count criterion for graphic lists
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/485/
%R 10.37236/485
%F 10_37236_485
Garth Isaak; Douglas B. West. The edge-count criterion for graphic lists. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/485

Cité par Sources :