# 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 . gisaak@ Douglas B. West Mathematics Department University of Illinois Urbana IL . west@ 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 . 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 .

TÀI LIỆU LIÊN QUAN
32    57    0
45    42    0
6    65    0
4    53    0
6    55    0
6    52    0
6    45    0
5    59    0
7    58    0
6    64    0
TÀI LIỆU XEM NHIỀU
13    32419    1640
3    19334    204
25    18618    3682
20    16737    1476
16    15733    2475
14    14308    2540
37    13032    2802
1    11307    401
3    10951    211
23    10537    384
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
134    140    1    30-06-2022
14    18    2    30-06-2022
8    9    1    30-06-2022
16    12    1    30-06-2022
213    109    4    30-06-2022
8    5    1    30-06-2022
68    6    1    30-06-2022
16    17    1    30-06-2022
54    37    1    30-06-2022
10    6    1    30-06-2022
5    16    2    30-06-2022
11    14    1    30-06-2022
18    52    2    30-06-2022
29    10    1    30-06-2022
46    9    1    30-06-2022
6    18    1    30-06-2022
30    6    1    30-06-2022
10    15    1    30-06-2022
32    7    1    30-06-2022
69    7    1    30-06-2022
TÀI LIỆU HOT
3    19334    204
13    32419    1640
3    1487    75
580    3625    343
62    4375    1
584    1955    80
171    3980    620
2    1735    72
51    2466    150
53    3329    175
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.