3
$\begingroup$

This is an extension of the problem at this thread: Graphs, line graph and complement of graph.

Just to reiterate definitions:

The line graph $L(G)$ of a graph $G$ is defined in the following way: the vertices of $L(G)$ are the edges of $G$, $V(L(G))=E(G)$, and two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ share a vertex.

Question:

Suppose $G$ has $n$ vertices, labeled $v_1,v_2,\ldots,v_n$ and the degree of vertex $v_i$ is $r_i$. Let $m$ denote the size of $G$, so $r_1+r_2+\ldots+r_n=2m$. Find formulas for the order and size of $L(G)$ in terms of $n,m,$ and $r_i$.

So far:

  1. Clearly, the order is $m$.
  2. Suppose that the edge $e=(v_i,v_j)$ exists in $G$. Then, the $\deg(e)=r_i+r_j - 2$ in $L(G)$, because at the $v_i$ end, $e$ shares $v_i$ with $r_i - 1$ other edges, and at the $v_j$ end, $e$ shares $v_j$ with $r_j - 1$ other edges.
  3. I tried to use the above to sum over all the edges in $G$, but this depends on knowing which edges exist in the graph $G$, which we are not given. We only know the degree sequence, not the edges.
  4. Another approach I tried was to find this expression for a regular graph with degree $k$, and this can be found using the above: $$m(2k - 2) = 2|E(L(G))| \implies |E(L(G))| = m(k - 1).$$ I then tried this for a complete graph (so $k = m - 1$), and then removing edges one at a time until it becomes $G$, but this also requires knowledge of the edges.

Any help would be greatly appreciated. One piece of information that I seem to be not using is the variable $n$, the order of $G$, but I am not sure where it would be appropriate to use.

$\endgroup$
2
  • 3
    $\begingroup$ Assuming your graphs don't have multiple edges, each vertex of degree $r$ in $G$ contributes $r(r-1)/2$ edges to the line graph. $\endgroup$ May 23, 2013 at 19:37
  • 2
    $\begingroup$ Wow, that is neat! Instead of enumerating by the edges of $G$ as I did, you enumerate by the vertices of $G$ and their effect on the size of $L(G)$. And yours is true because for each vertex $v$ with $\deg(v)=r$ in $G$, all pairs of edges share the $v$, so consequently, this adds $\binom{n}{2}$ edges in $L(G)$. Beautiful and simple, thank you. Do you want to make that an answer so I can accept it? $\endgroup$ May 23, 2013 at 21:59

1 Answer 1

2
$\begingroup$

The way I found it easiest to think about is that every vertex in G of degree r corresponds to r vertices that are connected among each other in L(G), so every vertex corresponds to a complete graph of order r. Then it corresponds to r(r-1)/2 edges (the number of edges in a complete graph). Then you just sum over $\frac{r^2-r}{2}$ to get the size of L(G) (from Wolfram Mathworld): $$\ \frac{1}{2}\sum_{i=1}^n (r_i)^2 - m $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.