Let $G= (V,E)$ be a simple graph. The line graph $L(G)$ is the graph its vertices correspond to $G$'s edges and two vertices are connected with an edge in $L(G)$ if the respective edges share a vertice in $G$.
Vertices: Obviously $|V(L(G))| = |E(G)|$ by definition.
Edges: An edge appears in $L(G)$ for each two edges that share a vertice in $G$, thus
$$
|E(L(G))| = \sum_{v_i \in V(G)} {\text{deg}(v_i) \choose 2}
$$
However, I'm having trouble producing a closed form of $L(G)$'s degree sequence.
My first thought was to take an edge $e = (u,v) \in E(G)$ with $e \in V(L(G))$ and find its degree in $L(G)$ as
$$
\text{deg}_{L(G)}(e) = \text{deg}_G(u) + \text{deg}_G(v) – 2
$$
but I can't figure out how to express $L(G)$'s degree sequence if $G$'s degree sequence $d_1 \geq d_2 \geq \dots \geq d_n$ is given.
Any form of help would be greatly appreciated.
Best Answer
I don’t think it’s possible to deduce the degree sequence of $L(G)$ given JUST the degree sequence of $G$. For example, consider the following graphs:
$G_1$ is a path of length 4, its degree sequence is 2,2,2,1,1. Then $L(G_1)$ is a path of length 3, its degree sequence is 2,2,1,1.
$G_2$ is the disjoint union of a triangle an an edge, it’s degree sequence is 2,2,2,1,1. Then $L(G_2)$ is the disjoint union of a triangle and a isolated vertex, its degree sequence is 2,2,2,0.
Then $G_1$ and $G_2$ have the same degree sequence but $L(G_1)$ and $L(G_2)$ do not.