Results 1 to 1 of 1

Math Help - graph: average of average degree of neighbours, is at least the average degree

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Belgium
    Posts
    1

    graph: average of average degree of neighbours, is at least the average degree

    Hello,

    thanks for letting me become a member of this forum.
    I would like to ask my very first question here

    Let G be a simple graph, with loops, multiple edges and without weighted edges.

    For every vertex v_i, let d_i denote its degree (number of neighbours), and let w_i denote the average of the degrees of neighbours of v_i

    Now one should prove that the average D of the d_i is at most the average W of the w_i, with equality if and only if the graph is regular (all d_i are equal).

    At first, I thought that this was simply related to the friendship paradox, where one considers

    \frac{\sum d_i}{n}\leq X=\frac{ \sum d_i^2}{\sum  d_i},
    which follows essentially from Cauchy-Schwarz.

    However, I noticed that the above is not quite the same.
    For instance, if you take a star graph on 4 vertices, then the average degree D is 1.5, while the number W is 2.5.
    The number  X from the above is 2, though.

    I found a discussion here, where a graph on four vertices is considered, here D= 2, W=2.4167 but X=2.25
    Why your friends have more friends than you: the friendship paradox - Mind Your Decisions


    Whenever I tried to prove that D \leq  W, I started struggling with a \frac{1}{d_i} somewhere that I can't get rid off.

    I'm probably missing something rather trivial, but for now I can't see it.
    Any ideas?

    Many thanks!
    Last edited by evilbu; January 21st 2013 at 02:05 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 'as an average'
    Posted in the New Users Forum
    Replies: 6
    Last Post: June 8th 2012, 05:59 AM
  2. Replies: 5
    Last Post: May 26th 2011, 06:11 AM
  3. Replies: 2
    Last Post: March 13th 2010, 05:49 AM
  4. average
    Posted in the Statistics Forum
    Replies: 3
    Last Post: March 20th 2009, 05:20 AM
  5. how to average SDs
    Posted in the Statistics Forum
    Replies: 3
    Last Post: April 15th 2008, 12:01 PM

Search Tags


/mathhelpforum @mathhelpforum