Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    Graphic Sequence

    Uploaded by

    marshallcheung
    1. If a degree sequence is graphic, then the sum of all degrees must be even. 2. The sum of the degrees of the first k vertices must be less than or equal to k(k-1) plus the sum of the minimum of k and the remaining degrees. 3. This is because the first k vertices can only be adjacent to each other k times each, and adjacent to the remaining vertices once each. So their maximum degree sum is k(k-1).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Graphic Sequence

    Uploaded by

    marshallcheung
    18 views1 page
    1. If a degree sequence is graphic, then the sum of all degrees must be even. 2. The sum of the degrees of the first k vertices must be less than or equal to k(k-1) plus the sum of the minimum of k and the remaining degrees. 3. This is because the first k vertices can only be adjacent to each other k times each, and adjacent to the remaining vertices once each. So their maximum degree sum is k(k-1).

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. If a degree sequence is graphic, then the sum of all degrees must be even. 2. The sum of the degrees of the first k vertices must be less than or equal to k(k-1) plus the sum of the minimum of k and the remaining degrees. 3. This is because the first k vertices can only be adjacent to each other k times each, and adjacent to the remaining vertices once each. So their maximum degree sum is k(k-1).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    18 views1 page

    Graphic Sequence

    Uploaded by

    marshallcheung
    1. If a degree sequence is graphic, then the sum of all degrees must be even. 2. The sum of the degrees of the first k vertices must be less than or equal to k(k-1) plus the sum of the minimum of k and the remaining degrees. 3. This is because the first k vertices can only be adjacent to each other k times each, and adjacent to the remaining vertices once each. So their maximum degree sum is k(k-1).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 1

    1.

    1.

    If a degree sequence d := ( d(v1 ),....,

    d(vn ))

    = (

    d1 ,...
    i=k+1

    dn )

    is graphic, then

    n
    i=1
    proof:

    dn

    is even, and

    k
    i=1

    di k(k 1) +

    min{k, di }

    Let G denote a simple graph with the graphic sequence d. Since the sequence d is graphic, of course any graph,
    i=1 dn is even. Since for |E| is the number of edges a graph G k n has. Now, we also have that i=1 di k(k 1) + i=k+1 min{k, di }, k n where 1 k n. Consider i=1 di i=k+1 di ; we have that this sum

    i=1 dn

    2|E|

    where

    is less than or equal to number of degrees k vertices in G have amongst themselves. That is, the k vertices involved in the sum adjacent to the other ( n - k ) vertices no more than

    k n i=1 di can be i=k+1 di times.

    However, this estimate can be tightened by the following argument: since G is simple, and there are only k vertices involved with the degree sum

    k
    to

    i=1

    di , the remaining ( n - k ) vertices can only contribute k degrees each k the sum i=1 di (since each vertex can be adjacent at most one time, di < k for k + 1 i n, then of course, the corresponding vertex be kdi can nadjacent to the k vertices at most di < k times. So, di - i=k+1 min{k, di } is less than or equal to number of i=1
    has the degree sum

    and there are k vertices for which each ( n - k ) vertices can be adjacent with). If we have with with degree

    k i=1 di = k(k 1). Thus, for any simple k n graph G, where 1 k n, di - i=k+1 min{k, di } k(k 1) and we i=1 n k have i=k+1 min{k, di }. i=1 di k(k 1)+ |V | = k

    degrees k vertices in G have amongst themselves. A complete simple graph

    You might also like