- #1
dbh2ppa
- 1
- 0
Homework Statement
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.
Homework Equations
The http://en.wikipedia.org/wiki/Line_graph" 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.
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).
[tex]
\frac{\sum_{i=1}^{m} r_{a_{i}}+r_{b_{i}}-2}{2}
[/tex]
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: