Results 1 to 5 of 5

Math Help - Graphic Sequence

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Graphic Sequence

    How do I show whether or not this a graphic sequence:

    5,5,4,3,2,2,2,1

    Thanks...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    From Wolfram Mathworld :

    Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with n>=3 and d_1>=1 is graphical iff the sequence {d_2-1,d_3-1,...,d_(d_1+1)-1,d_(d_1+2),...,d_p} is graphical.

    Graphic Sequence -- from Wolfram MathWorld

    The sequence in the successive steps would look like:

    5 5 4 3 2 2 2 1

    4 3 2 1 1 2 1

    4 3 2 2 1 1 1

    2 1 1 0 1 1

    2 1 1 1 1 0

    0 0 1 1 0

    The last sequence is clearly graphic. So the first one will be graphic too.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    I still have a question about how you went from the original to the second line:

    5 5 4 3 2 2 2 1

    4 3 2 1 1 2 1

    So you deleted the front 5 and subtracted 1 from 5,4,3,2,2. Why are the last two of the second sequence still 2,1? Shouldn't we subtract 1 from those also?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    No, what we are doing is equivalent to removing a vertex and and deleting its incident edges. A vertex is adjacent exactly to the number of vertices as its degree. So a vertex with degree 5 would be adjacent to exactly 5 vertices. Now, if you remove the edges between this vertex and its neighbours, each of the 5 neighbours would lose 1 from their degrees.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2010
    Posts
    57
    What if we have d1 as greater or equal to number vertices in the graph. How long we have to subtract 1 ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graphic-solution
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: July 2nd 2009, 06:58 AM
  2. graphic
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: June 29th 2009, 04:23 AM
  3. graphic
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 13th 2008, 11:12 AM
  4. matlab 3D-4D graphic plot
    Posted in the Math Software Forum
    Replies: 6
    Last Post: October 25th 2008, 03:53 AM
  5. Solving Graphic Equations
    Posted in the Algebra Forum
    Replies: 4
    Last Post: May 28th 2008, 11:04 PM

Search Tags


/mathhelpforum @mathhelpforum