Line graph

The line graph of a graph has one vertex for each original edge, with two vertices adjacent exactly when their edges share an endpoint.

Incidence matrix: A matrix recording which vertices are incident to which edges in a graph. Multiplying incidence data reveals which pairs of original edges meet.
Graph (discrete mathematics): A mathematical structure of vertices connected by edges. The line graph is a transformation applied to an original graph.
Complete graph: A graph in which every pair of distinct vertices is adjacent. The line graph of a complete graph displays dense edge-incidence structure.
Subdivision graph: A graph formed by inserting a new vertex into each edge of an original graph. Subdivision inserts vertices along edges; a line graph instead represents edges as vertices.
Clique: A set of pairwise adjacent vertices in a graph. Edges incident at one original vertex become a clique in the line graph.
Adjacency: A relation indicating that two vertices or edges are directly connected or incident. Line-graph edges encode adjacency between original edges.
Path graph: A graph whose vertices form one simple path. Taking a line graph shortens a path by one edge-vertex step.
Total graph: A graph representing both original vertices and edges, with adjacency based on incidence or adjacency. Unlike a line graph, it retains original vertices as well as edges.
Degree (graph theory): The number of edges incident to a vertex in a graph. An original vertex of degree d induces a clique of d line-graph vertices.
Simple graph: A graph with no loops and at most one edge between any vertex pair. For simple inputs, the line graph is also simple.

Linked from 13 pages