Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The edge-count criterion for graphic lists"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:The edge-count criterion for graphic lists. | The edge-count criterion for graphic lists Garth Isaak Department of Mathematics Lehigh University Bethlehem PA 18015 U.S.A. gisaak@lehigh.edu Douglas B. West Mathematics Department University of Illinois Urbana IL U.S.A. west@math.uiuc.edu Submitted Sep 14 2009 Accepted Jan 28 2010 Published Nov 19 2010 Mathematics Subject Classification 05C07 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 52ieI di 52jeJ p n 1 - dj 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. The problem of characterizing degree lists also called degree sequences of simple graphs is well studied. The sum is twice the number of edges and hence must be even but this condition is not sufficient. Sierksma and Hoogeveen 11 summarized seven characterizations. With additional results these also appear in 7 . The various characterizations have been proved in many ways we will not attempt to survey the proofs. We give a new short proof of another natural characterization due to Koren 6 which we call the Edge-Count Criterion. Koren used it to characterize the polytope of degree lists 10 . We prove the characterization in the more general setting of multigraphs with bounded multiplicity p. The idea also works for bipartite or directed graphs and the multigraph characterization applies to give an immediate characterization of degree lists for signed graphs using a transformation due to T.S. Michael . A multigraph G with bounded multiplicity p is a pair consisting of a set V G of vertices and a multiset E G of unordered pairs of vertices where .