Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[Graph theory] Formula for the size of a line graph

  1. Apr 5, 2010 #1
    1. The problem statement, all variables and given/known data
    Let G be a graph of order n and size m.
    V(G)={v1,v2,...,vn} and deg(vi)=ri.
    Find a formula for the size of the line graph L(G) in terms of n, m, and ri.

    2. Relevant equations
    The http://en.wikipedia.org/wiki/Line_graph" [Broken] L(G) is the graph such that every vertex in L(G) corresponds to an edge in G, and two vertices in L(G) are adjacent iff the corresponding edges in G share a vertex.

    3. The attempt at a solution
    I know that the degree of any w in V(L(G)), when w is equivalent to some edge (va,vb) in G, is (ra-1)+(rb-1), that is to say ra+rb-2.
    The size of L(G) would be (with it's vertices labeled from 1 to m).
    \frac{\sum_{i=1}^{m} r_{a_{i}}+r_{b_{i}}-2}{2}
    Where vai and vbi are the vertices of the edge in G corresponding to wi in L(G). This, however, seems to be the least elegant solution possible. Is there a better solution? Are there any errors in the one I wrote? (I really am not sure about it).
    Last edited by a moderator: May 4, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?