Fact-checked by Grok 2 weeks ago

Line graph

In graph theory, the line graph L(G) of an undirected simple graph G is defined as the graph whose vertex set consists of the edges of G, with two vertices in L(G) adjacent if and only if the corresponding edges in G are incident, meaning they share a common vertex.^[1] This construction transforms the edge structure of G into the vertex structure of L(G), providing a way to study edge-related properties through vertex analysis.^[2] The concept of line graphs originated in the early 20th century, with initial investigations by Hassler Whitney in 1932, who explored isomorphisms between graphs via their line graphs.^[3] The term "line graph" was formally introduced by Frank Harary and Robert Z. Norman in 1960, building on earlier work, though the idea had been studied under different names prior to that.^[3] Whitney's seminal result, known as Whitney's isomorphism theorem, states that if two connected graphs have isomorphic line graphs, then the original graphs are isomorphic, with the notable exception of the triangle K_3 and the star K_{1,3}, which share the same line graph (a triangle).^[1] Line graphs exhibit several characterizing properties that distinguish them within graph theory. A nonempty graph is a line graph if and only if its edge set can be partitioned into cliques such that every vertex lies in at most two of these cliques, a result known as Krausz's theorem.^[1] If G is k-regular, then L(G) is (2k-2)-regular, reflecting the incidence structure.^[1] Additionally, line graphs are claw-free, meaning they contain no induced subgraph isomorphic to K_{1,3}, and the line graphs of bipartite graphs are perfect graphs.^[4] For recognition, a graph with minimum degree at least 5 is a line graph if it avoids certain forbidden induced subgraphs, such as the Metelsky graphs.^[5] Line graphs find applications across various areas of graph theory, particularly in translating edge problems to vertex problems. For instance, finding a maximum matching in G is equivalent to finding a maximum independent set in L(G), and edge coloring in G corresponds to vertex coloring in L(G).^[4] They also aid in studying edge connectivity, as the vertex connectivity of L(G) relates to the edge connectivity of G.^[6] These properties make line graphs a fundamental tool in algebraic graph theory, network analysis, and combinatorial optimization.^[7]

Fundamentals

Definition

In graph theory, the line graph L(G) of a simple undirected graph G is constructed such that its vertex set is in one-to-one correspondence with the edge set of G, and two vertices in L(G) are connected by an edge if and only if the corresponding edges in G are incident, meaning they share a common endpoint.^[8] This mapping transforms the incidences between edges in the original graph into adjacencies in the line graph, providing a representation where the structure of edge connections is preserved topologically.^[9] More precisely, the adjacency condition in L(G) holds between two vertices if their preimages— the edges in G—share exactly one endpoint, assuming G has no multiple edges between the same pair of vertices.^[8] For an edge e = \{u, v\} in G, the degree of the corresponding vertex in L(G) is given by \deg_{L(G)}(e) = \deg_G(u) + \deg_G(v) - 2, reflecting the number of other edges incident to u or v excluding e itself.^[8] The original graph G is referred to as the root graph or preimage graph of L(G), emphasizing the derivational relationship between the two structures.^[9]

Example

To illustrate the construction of a line graph, consider the complete graph K_3, a triangle with vertices labeled 1, 2, and 3, and edges e_1 = \{1,2\}, e_2 = \{2,3\}, and e_3 = \{3,1\}.^[10] The line graph L(K_3) has three vertices v_1, v_2, and v_3, each corresponding to one of these edges. Vertices in L(K_3) are adjacent if the edges they represent share a common vertex in K_3: thus, v_1 connects to v_2 (sharing vertex 2), v_1 to v_3 (sharing vertex 1), and v_2 to v_3 (sharing vertex 3). This adjacency rule yields L(K_3) as another triangle with all pairs connected.^[8]^[10] Visually, K_3 appears as an equilateral triangle enclosing its three edges. To overlay L(K_3), place each vertex v_i at the midpoint of edge e_i; the induced edges then form a smaller triangle linking these midpoints, with each connection tracing the path around the shared endpoints of the original edges. In K_3, every vertex has degree 2, so for any edge e = \{u,v\}, it is adjacent to \deg(u) - 1 + \deg(v) - 1 = 2 other edges. Each vertex in L(K_3) thus has degree 2, consistent with the complete graph structure.^[8] This example shows L(K_3) \cong K_3.^[10]

Properties

Inherited Properties from the Original Graph

The connectivity of the line graph L(G) mirrors that of the original graph G in a direct manner. Specifically, assuming G has no isolated vertices, L(G) is connected if and only if G is connected. If G is disconnected, then L(G) is disconnected, with each connected component of L(G) corresponding to the edges in a connected component of G that contains at least one edge.^[11] Bipartiteness in line graphs is also inherited under precise conditions from the structure of G. L(G) is bipartite if and only if G is a disjoint union of even cycles and paths. This ensures that no odd cycles arise in L(G), as even cycles in G map to even cycles in L(G), while paths produce bipartite subgraphs without introducing odd-length structures.^[9] The number of edges in L(G) can be expressed in terms of the degrees in G, providing a quantitative link between the two graphs:

|E(L(G))| = \frac{1}{2} \sum_{v \in V(G)} \binom{\deg(v)}{2}.

This formula arises because each vertex v in G contributes \binom{\deg(v)}{2} edges in L(G) among the edges incident to v, with the factor of 1/2 accounting for double-counting across vertices.^[9] A defining inherited property is claw-freeness: every line graph L(G) is claw-free, meaning it contains no induced subgraph isomorphic to K_{1,3}. This holds because any three vertices in L(G) corresponding to edges incident to a common vertex in G must form a triangle (if pairwise adjacent) or be connected in a way that avoids the claw structure; non-adjacent edges in G cannot all share a single common neighbor without inducing additional edges.^[12] Paths and cycles in G translate directly to similar structures in L(G), preserving much of the original topology. A path in G corresponds to a path in L(G), as consecutive edges in the path become adjacent vertices in L(G). Similarly, every cycle of length at least 4 in G induces a cycle of the same length in L(G), since the edges around the cycle are sequentially adjacent in L(G).^[11]

Whitney Isomorphism Theorem

The Whitney isomorphism theorem asserts that if G and H are connected graphs that are neither isomorphic to K_3 nor to K_{1,3}, and their line graphs satisfy L(G) \cong L(H), then G \cong H. This result establishes that, under these conditions, the line graph operation is injective on the isomorphism classes of connected graphs, providing a near-reversibility to the mapping from graphs to their line graphs. The theorem was established by Hassler Whitney in 1932 as part of his work on graph congruences and connectivity. The exceptions arise specifically for the triangle K_3 and the claw K_{1,3}, both of which have line graphs isomorphic to K_3: in K_3, the three edges form a complete graph in the line graph due to pairwise vertex sharing; similarly, in K_{1,3}, the three pendant edges all share the central vertex, inducing the same K_3 structure. For connected graphs with more than four vertices, there are no such exceptions, ensuring uniqueness. A high-level outline of the proof proceeds by leveraging the structural encoding in the line graph. Given an isomorphism \phi: L(G) \to L(H), the degrees in L(G) reveal the degrees in G, since the degree of a vertex in L(G) corresponding to edge uv \in E(G) is \deg_G(u) + \deg_G(v) - 2. The adjacency relations in L(G) allow reconstruction of the endpoint incidences: maximal cliques in L(G) correspond to the edge stars at vertices of G (or triangles if present), enabling identification of the bundles of edges incident to each vertex. An isomorphism \phi then lifts to a bijection between edges of G and H that preserves these incidences, yielding vertex isomorphisms for G and H except in the small exceptional cases, which are verified directly. As a corollary, almost all line graphs—specifically, those of connected graphs excluding the exceptions—have a unique root graph up to isomorphism, underscoring the theorem's role in uniquely determining original graphs from their line representations.

Line Graphs of Special Graph Classes

Line graphs derived from special classes of graphs often inherit or exhibit notable structural properties. For instance, when the original graph is strongly regular, its line graph may also be strongly regular under certain conditions. The line graph of the complete graph K_m (for m \geq 4), known as the triangular graph T(m), is strongly regular with parameters \left( \binom{m}{2}, 2(m-2), m-2, 4 \right). Similarly, the line graph of the complete bipartite graph K_{m,m} (for m \geq 2), also known as the lattice graph L_2(m) or Shrikhande graph in some contexts, is strongly regular with parameters (m^2, 2(m-1), m-2, 2). Regarding perfect graphs, the line graph L(G) is perfect whenever G is bipartite. This follows from the structure of line graphs of bipartite graphs, which contain no induced odd cycles or their complements (odd antiholes), aligning with the strong perfect graph theorem. For example, if G is a complete bipartite graph K_{a,b}, then L(G) is a perfect graph whose chromatic number equals its clique number for every induced subgraph. However, if G is not bipartite, L(G) need not be perfect; a counterexample is the cycle graph C_5, whose line graph is isomorphic to C_5 itself, which has clique number 2 but chromatic number 3. The eigenvalues of the adjacency matrix of a line graph L(G) are intimately related to those of the original graph G through the incidence matrix B of G, where the adjacency matrix satisfies A_{L(G)} = B^T B - 2I (with I the identity matrix of order |E(G)|). For a k-regular graph G with adjacency eigenvalues \theta_1 = k (multiplicity 1) and \theta_2, \dots, \theta_n (where n = |V(G)|), the eigenvalues of L(G) are $2k - 2 (multiplicity 1) and k + \theta_i - 2 for i = 2 to n, along with -2 (with multiplicity |E(G)| - |V(G)|). Line graphs also exhibit Hamiltonian properties tied to Eulerian structures in the original graph. Specifically, L(G) is Hamiltonian (i.e., contains a Hamiltonian cycle) if G is Eulerian, meaning G is connected and every vertex has even degree; in this case, an Eulerian circuit in G traverses every edge exactly once and induces a Hamiltonian cycle in L(G). More broadly, L(G) contains a Hamiltonian path if G has an Eulerian path (i.e., G is connected with exactly zero or two vertices of odd degree).

Connections to Other Graph Families

Line graphs form a subclass of claw-free graphs, as no vertex in a line graph corresponds to an edge incident to three pairwise non-adjacent edges in the original graph. Specifically, if three edges incident to a common edge are pairwise non-adjacent, they would form an induced claw K_{1,3}, which is impossible in the structure of line graphs. However, the converse does not hold; there exist claw-free graphs that are not line graphs, such as certain quasi-line graphs or more complex structures identified in structural theorems for claw-free graphs. Thus, line graphs constitute a proper subclass of the claw-free family.^[13]^[14] Line graphs overlap with claw-free perfect graphs by including all complete graphs K_n (for n \geq 1) as special cases, since the line graph of the star graph K_{1,n} is isomorphic to K_n, and complete graphs are both claw-free and perfect. Additionally, line graphs include all cycle graphs C_n (for n \geq 3), as the line graph of C_n is isomorphic to C_n itself; odd cycles of length at least 5 are claw-free but not perfect, illustrating that line graphs contain both perfect and non-perfect members of the claw-free family. This overlap highlights line graphs as a bridge between perfect and non-perfect claw-free structures.^[15]^[9] Finally, line graphs are a specific type of intersection graph: L(G) is the intersection graph of the edges of G, where each vertex of L(G) represents an edge of G, and two vertices in L(G) are adjacent if and only if the corresponding edges in G share a common vertex (i.e., their endpoint sets intersect). This representation underscores the geometric and set-theoretic connections of line graphs to the incidence structure of the original graph.^[9]

Characterization and Recognition

Clique Partition Characterization

A graph H is a line graph if and only if its edge set can be partitioned into cliques such that every vertex of H lies in at most two of these cliques.^[1] This characterization, known as Krausz's theorem, provides a constructive way to verify membership in the class of line graphs by examining edge-disjoint cliques that cover all edges while respecting the degree-two intersection condition at vertices.^[16] In this partition, each clique in H = L(G) corresponds to either the set of edges incident to a single vertex in the original graph G (forming a star subgraph K_{1,d} where d = \deg(v)), or the three edges of a triangle in G. The size of a star-induced clique equals the degree of the corresponding vertex in G, reflecting the incidence structure where vertices of L(G) (edges of G) are adjacent if they share an endpoint. For instance, in the line graph of the complete graph K_3, which is itself K_3, the entire edge set forms a single clique of size 3, corresponding to the triangle in K_3.^[1] The root graph's incidence relation underpins these cliques, as adjacency in L(G) arises precisely from shared endpoints in G. This partition property implies that verifying the existence of such a clique cover can serve as a basis for line graph recognition, though efficient algorithms typically combine it with other structural checks.^[16]

Forbidden Induced Subgraphs

Beineke's theorem provides a forbidden induced subgraph characterization of line graphs. A graph is the line graph of some graph if and only if it contains none of nine specific induced subgraphs as minimal forbidden configurations.^[17] This characterization, established in 1970, is minimal in the sense that removing any one of the nine subgraphs from the list would allow some non-line graphs to be incorrectly classified as line graphs.^[17] The nine forbidden induced subgraphs, often referred to collectively as the Beineke graphs, each have between 4 and 6 vertices and represent structural impossibilities in the adjacency of edges within any underlying graph. For instance, the chair (also known as the fork) is a 5-vertex graph consisting of a path of length 3 (four vertices) with an additional edge connecting the second vertex to a pendant vertex, forming a configuration resembling a chair; its induced presence implies an incompatible branching of edge adjacencies not possible under the root graph's vertex constraints. The long claw extends the claw by lengthening one arm to a path of length 3, creating a 6-vertex tree where one path from the center is longer, which forbids it due to the inability to assign consistent incident edges without multiple incidences at a single vertex.^[17] The remaining six forbidden subgraphs include variants such as the umbrella (a triangle with two pendant edges attached to different vertices), certain chorded odd cycles like a 5-cycle with a chord, and other attached structures like a complete graph minus an edge (e.g., K_5 - e) or forked triangles. Each of these corresponds to a local configuration—such as an odd number of edges between partitions or incompatible multiple adjacencies—that cannot be realized as the incidence graph of edges in a simple graph, as proven through exhaustive case analysis of potential root graphs.^[17]^[18] This approach complements alternative characterizations, such as those based on clique partitions.

Recognition Algorithms

The recognition of line graphs has been advanced through several efficient algorithms that leverage structural characterizations to determine whether a given graph is the line graph of some root graph and, if so, to reconstruct it. One of the seminal approaches is the algorithm developed by Roussopoulos in 1973, which operates in O(\max{n, m}) time, where n is the number of vertices and m the number of edges. This method uses a partition of the edges of the input graph into cliques, corresponding to the stars and triangles in the root graph, to reconstruct the root via a rooting process that identifies odd triangles and builds the adjacency structure accordingly.^[19] Independently, Lehot proposed a similar linear-time algorithm in 1974, achieving O(n + m) complexity by employing an edge-coloring strategy on the input graph to simulate the matching of edges in the root graph, followed by verification and reconstruction steps that ensure the coloring aligns with the line graph properties. Both Roussopoulos's and Lehot's algorithms not only recognize line graphs but also output the root graph, making them practical for applications requiring inversion. These methods rely on the clique partition characterization rather than exhaustive searches, ensuring efficiency for sparse and dense graphs alike.^[20] An alternative recognition strategy involves checking for the absence of Beineke's nine forbidden induced subgraphs, which characterize non-line graphs. While induced subgraph isomorphism is NP-complete in general, the fixed small size (at most six vertices) of these specific subgraphs allows for polynomial-time verification, with naive enumeration yielding O(n^6) complexity, though optimized implementations reduce this to O(n^3) or better using adjacency matrix multiplications or bounded-degree heuristics. This approach is theoretically foundational but less efficient in practice than the linear-time reconstruction methods for large graphs.^[16] Recent advancements have refined these techniques for even greater efficiency and applicability. For instance, the ILIGRA (Inverse Line Graph Recognition Algorithm) by Liu, Trajanovski, and Van Mieghem in 2015 provides a linear-time solution, O(n + m), by iteratively building the root graph through degree-based vertex selection and clique identification, with early termination if inconsistencies arise during construction. Additionally, dynamic algorithms like that of Degiorgi and Simon (1996) extend recognition to handle local graph modifications in O(1 + d) time per update, where d is the size of the modified adjacency list, enabling real-time applications in evolving networks. Up to 2025, no fundamentally new linear-time paradigms have emerged beyond these refinements, though degeneracy-based preprocessing has been integrated into hybrid tools for faster empirical performance on sparse graphs.^[21]^[22]

Iterated Line Graphs

Construction Process

The iterated line graph L^k(G) of a graph G is constructed by recursively applying the line graph operator L, where L^1(G) = L(G) and L^k(G) = L(L^{k-1}(G)) for k \geq 2.^[23] This process begins with the standard line graph, in which vertices represent the edges of G and adjacency exists between vertices if the corresponding edges in G share a common vertex, and extends it through successive transformations.^[23] In the second iteration, L^2(G), the vertices correspond to the edges of L(G), which themselves represent pairs of incident edges from the original graph G; thus, each vertex in L^2(G) encodes a path of length 2 in G.^[24] The edges of L(G), and hence the vertices of L^2(G), number \sum_{v \in V(G)} \binom{\deg_G(v)}{2}, reflecting quadratic growth relative to the degrees in G for graphs with higher connectivity.^[23] Subsequent iterations amplify this effect, with the number of vertices in L^k(G) determined by the edge count of L^{k-1}(G), leading to rapid expansion in graphs where minimum degree is at least 3. For a finite connected graph G, the sequence G, L(G), L^2(G), \dots exhibits one of four behaviors under iteration: the number of vertices steadily increases indefinitely; the sequence remains constant (as with cycle graphs); it stabilizes after one step (as with the star K_{1,3}); or it decreases to the empty graph (as with paths or disjoint edges).^[25] In small cases, such as those with all degrees at most 2, the process terminates or stabilizes quickly, while others grow without bound.^[25] As an example, iteration on a path graph P_n (with n \geq 3) produces L(P_n) \cong P_{n-1}, continuing to shorten the path until reaching the empty graph after n-1 steps, thereby stabilizing thereafter.^[25]

Properties and Uniqueness

The k-iterated line graph L^k(G) of a connected graph G remains connected for all k ≥ 1, as the line graph operator preserves connectivity for graphs without isolated edges.^[26] Furthermore, if G is a connected regular graph of degree at least 3, the vertex-connectivity of L^k(G) equals its degree for sufficiently large k (specifically k ≥ 5), achieving the maximum possible connectivity.^[26] For a connected graph G that is not a path, cycle, or claw (termed prolific), the diameter of L^k(G) satisfies diam(L^{k+1}(G)) = diam(L^k(G)) + 1 for all sufficiently large k, implying a linear growth in diameter with the iteration depth.^[27] This behavior establishes an upper bound on the diameter of L^k(G) that is at most 2k - 1 under standard assumptions on the initial diameter of L(G) ≤ 2 for connected graphs excluding paths.^[27] Unlike the single iteration case, where Whitney's isomorphism theorem guarantees that most graphs are uniquely reconstructible from their line graph (except for K_3 and K_{1,3}), higher iterations do not preserve uniqueness of the root graph.^[28] Multiple non-isomorphic graphs can yield isomorphic k-iterated line graphs for k > 1, as the mapping from G to L^k(G) loses structural information through successive applications of the line graph operator, with known counterexamples for second-iterated line graphs.^[29] This failure of generalization limits root reconstruction to specialized cases or additional constraints. The spectral properties of iterated line graphs for regular graphs exhibit distinctive patterns in their eigenvalues. For an r-regular graph G with r ≥ 3, all negative eigenvalues of L^k(G) are equal to -2 for every k ≥ 1.^[30] The adjacency matrix of L(G) relates to the incidence matrix B of G via A(L(G)) = B B^T - 2I, and eigenvalues of iterated versions arise from powers of this operator, with the largest eigenvalue (spectral radius) of L(G) being 2(r - 1) and subsequent iterations amplifying positive eigenvalues while stabilizing the negative spectrum at -2.^[30] As k increases, L^k(G) for a connected graph G with |E(G)| = m exhibits asymptotic behavior toward a highly dense structure on an exponentially growing number of vertices, where the minimum degree and connectivity approach the theoretical maximum relative to the order, resembling properties of complete graphs in terms of expansion and linkage but on |E(L^{k-1}(G))| vertices.^[26] For large k, the graph becomes maximally connected, with diameter growing linearly while the vertex count expands, leading to effective completeness in local neighborhoods.^[27]

Generalizations

Multigraph and Digraph Variants

In the context of multigraphs, which permit multiple edges between the same pair of vertices, the line graph L(G) is constructed with vertices corresponding to the edges of G, and two such vertices are adjacent in L(G) if the corresponding edges in G share a common incident vertex. If G contains parallel edges, L(G) may itself be a multigraph, with the multiplicity of edges in L(G) reflecting the number of shared incidences between the original edges.^[31] This extension preserves the incidence structure while accommodating parallels, distinguishing it from the simple graph case where at most one edge exists between any pair.^[31] Loops in a multigraph G, which are edges connecting a vertex to itself, are handled in the line graph construction such that a loop at vertex v becomes a vertex in L(G) adjacent to all vertices corresponding to other edges incident to v, since they share v.^[15] Some formulations may exclude loops or adjust degrees, but the standard definition integrates them via incidence. For directed graphs, or digraphs, the analogous structure is the line digraph L(D), where vertices correspond to the arcs of D. There is a directed edge in L(D) from the vertex representing arc (u, v) to the vertex representing arc (x, y) precisely when v = x, capturing head-to-tail incidence.^[32] This definition extends the undirected incidence relation to respect directionality, focusing on sequential connectivity along arcs. Line digraphs inherit key connectivity properties from their root digraphs. Specifically, L(D) is strongly connected if and only if D is strongly connected, assuming D has at least two vertices, thereby preserving the ability to traverse all vertices via directed paths.^[32] Regarding degrees, the out-degree in L(D) of the vertex for arc (u, v) equals the out-degree of v in D, while its in-degree equals the in-degree of u in D; this relation ensures that local arc behaviors translate to global degree patterns in the line digraph.^[32]

Total and Weighted Line Graphs

The total graph T(G) of a graph G is defined as the graph with vertex set V(G) \cup E(G), where two vertices in T(G) are adjacent if and only if they correspond to elements of G that are either adjacent vertices, incident vertex-edge pairs, or adjacent edges (sharing a common endpoint). This construction was introduced by Behzad in 1970 as part of a characterization study of such graphs. The edges of T(G) thus consist of three disjoint types: the original edges of G (connecting vertices in V(G)), the edges of the line graph L(G) (connecting vertices in E(G)), and the bipartite incidence edges between V(G) and E(G) (connecting a vertex to each of its incident edges).^[33] This structure positions T(G) as a natural extension that incorporates both vertex and edge information from G, facilitating analyses that bridge vertex and edge properties, such as total colorings or traversability studies. For instance, the degree of a vertex v in T(G) is \deg_G(v) + \deg_G(v) = 2\deg_G(v), while the degree of an edge-vertex e = uv in T(G) is \deg_G(u) + \deg_G(v).^[34] Total graphs of regular graphs exhibit strong regularity properties, often leading to strongly regular graphs when G is complete.^[35] Weighted line graphs extend the line graph construction to weighted graphs G, where each edge e \in E(G) has an associated attribute such as length or capacity, denoted w(e). In the weighted line graph WL(G), the vertices correspond to E(G) as in the standard line graph, with adjacency preserved based on shared endpoints in G; however, the edges of WL(G) are assigned weights derived from the attributes of the corresponding original edges, for example, via a formula that normalizes the product of weights adjusted by endpoint strengths to account for degree heterogeneity.^[36] This weighting preserves incidence relations while encoding edge-specific metrics, enabling applications like community detection in weighted networks.^[36] In network flow contexts, such weighted line graphs model edge capacities or costs, transforming edge-flow problems into vertex-based analyses on WL(G), where flow constraints on original edges become properties of vertices or weighted adjacencies.^[37] For multigraphs with parallel edges, weighted line graphs handle parallels by assigning distinct vertices in WL(G) to each parallel edge, with weights reflecting their individual attributes.^[36]

Hypergraph and Disjointness Extensions

In hypergraph theory, the line graph of a hypergraph H = (V, E) is defined as the graph L(H) whose vertex set corresponds to the hyperedges in E, with two vertices adjacent if and only if the corresponding hyperedges have a non-empty intersection.^[38] This construction generalizes the classical line graph of a graph, where hyperedges replace edges and intersection replaces shared vertices.^[39] Seminal work by Berge refers to L(H) interchangeably as the line graph or representative graph of H, emphasizing its role in capturing hyperedge overlaps.^[40] Two primary variants of line graphs for hypergraphs exist: intersection line graphs and incidence line graphs. The intersection line graph, as defined above, focuses on pairwise overlaps among hyperedges and is the direct analog of the graph line graph. In contrast, the incidence line graph is bipartite, with one part consisting of the vertices of H and the other part consisting of the hyperedges of H, where an edge connects a vertex to a hyperedge if the vertex belongs to that hyperedge; this structure encodes membership relations without emphasizing intersections.^[41] For k-uniform hypergraphs (where all hyperedges have exactly k vertices), the intersection line graph can be further specialized; for instance, if H is linear (any two hyperedges intersect in at most one vertex), the resulting graph belongs to the class I_1(k).^[38] The disjointness graph provides an abstract dual variant to the intersection line graph. For a family of sets such as the hyperedges of H, the disjointness graph has the sets as vertices, with an edge between two vertices if the corresponding sets are disjoint.^[42] This construction inverts the adjacency condition of the intersection line graph, making it useful for studying complementary overlap properties in set systems.^[43] Hypergraph line graphs extend key properties of classical line graphs to higher uniformity. Notably, the line graphs of 2-uniform hypergraphs (ordinary graphs) are claw-free, meaning they contain no induced K_{1,3} subgraph.^[38] For k \geq 3, the intersection graphs of linear k-uniform hypergraphs generalize this by avoiding infinite families of forbidden induced subgraphs, such as chains of diamond graphs, though they are not necessarily claw-free without additional constraints like minimum degree conditions (e.g., finite forbidden subgraph characterizations exist for minimum degree at least $2k^2 - 3k + 1).^[38] These properties highlight how hypergraph line graphs capture structural generalizations of claw-freeness, with recognition problems being NP-complete for k \geq 3.^[44]

Medial Graphs and Polyhedral Applications

In the context of plane graphs, the medial graph of a plane graph G is constructed by placing a vertex at the midpoint of each edge of G, with edges in the medial graph connecting these midpoints whenever the corresponding edges of G are consecutive along the boundary of a face in the embedding of G.^[45] This construction yields a 4-regular plane graph, as each original edge borders two faces and has two consecutive neighbors on each face boundary.^[45] Medial graphs bear a close relationship to line graphs, particularly for 3-regular (cubic) plane graphs. For a cubic plane graph G, the medial graph coincides exactly with the line graph L(G), because the embedding ensures that edges incident at each vertex are consecutive along the faces, making the adjacency conditions equivalent. More generally, medial graphs of 3-connected planar graphs are 4-regular line graphs, inheriting planarity and connectivity from the original embedding.^[45] In polyhedral applications, line graphs of the 1-skeletons of convex polyhedra play a key role in embedding theory. The 1-skeleton of a 3-dimensional convex polyhedron is a 3-connected planar graph by Steinitz's theorem, which states that a graph is realizable as the 1-skeleton of a convex 3-polytope if and only if it is planar and 3-connected.^[46] For a cubic 3-polytope \Gamma, its line graph L(\Gamma) (equivalently, the medial graph M(\Gamma)) is a 4-regular 3-connected planar graph, hence also realizable as the 1-skeleton of another convex 3-polytope by Steinitz's theorem.^[45] This correspondence allows line graphs to map polyhedral structures to new embeddable graphs on surfaces, facilitating studies in geometric graph theory and polyhedral realizations.^[46] A representative example is the cube, whose 1-skeleton is a cubic 3-polytope with 8 vertices and 12 edges. The medial graph of this skeleton coincides with its line graph, forming a 4-regular graph with 12 vertices that is the 1-skeleton of the cuboctahedron, another convex 3-polytope. This illustrates how medial and line graph constructions preserve polyhedral embeddability.^[45]

References

[1]
[PDF] Section 1.7. Line Graphs
Oct 9, 2022 · The line graph of a graph X is the graph L(X) with the edges of X as its vertices, and where two edges of X are adjacent in L(X) if and only if ...
[2]
[PDF] Line Graphs Math 381 — Spring 2011 Since edges are so ... - People
The name comes from the fact that ”line” is another name for ”edge”; the line graph is the graph of relations between edges.
[3]
[PDF] A Note On Line Graphs - Smarandache Notions
The line graph L(G) of a graph G is defined to have as its vertices the edges of G, with two being adjacent if the corresponding edges share a vertex in G. Line ...
[4]
[PDF] Line Graphs and Circulants
The line graph of a simple graph G, denoted L(G), is the graph with vertex set E(G), where vertices x and y are adjacent in L(G) iff edges x and y share a ...
[5]
[PDF] On the Planarity of Generalized Line Graphs
Large parts of graph theory could be formulated in terms of line graphs. For instance matching theory deals with independent vertex sets in the line graph, edge ...
[6]
[PDF] Edge Importance in a Network Via Line Graphs and the Matrix ...
Defining a single line graph for a directed graph is difficult, as there are some non- canonical choices. We therefore introduce four line graphs that capture ...
[7]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.
[8]
Line Graph -- from Wolfram MathWorld
A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the above six Metelsky graphs as an induced subgraph (Metelsky and ...
[9]
[PDF] A Study On Distinct Domination Parameters On Line Graph of ...
2) For complete graph K1, no line graph exist. 3) Line graph of K2 is a null graph. 4) Line graph of K3 graph is a K3 graph. (ie) L(K3)= K3. 5) For all n>3 ...
[10]
[PDF] Line Graphs Math 381 Version of March 18, 2013 Since edges are ...
This graph is the line graph, L(G). Formal definition: L(G) is the graph ... Then L(G) is connected if and only if. G is connected. Exercise LG.6. Prove ...
[11]
[PDF] Hamiltonian Claw-free Graphs and Line Graphs
A claw-free graph G = a graph that does not have an induced K1,3. Theorem: (Beineke and Robertson) Every line graph is also a claw-free graph.
[12]
[PDF] The structure of claw-free graphs - Math (Princeton)
A graph is claw-free if no vertex has three pairwise nonadjacent neighbors. Every connected claw-free graph can be obtained from basic types by expansion.
[13]
Claw-Free Graph -- from Wolfram MathWorld
The line graph of any graph is claw-free, as is the complement of any triangle-free graph. Classes of graphs that are claw-free include. 1. antiprism graphs,.
[14]
Some notes on the threshold graphs - ScienceDirect.com
Sep 28, 2010 · Threshold graphs ... The next example (constructed ad hoc) shows that other graphs (like line graphs of NSGs) do not have such a nice property.
[15]
Line graphs - Graph Theory - SageMath Documentation
The line graph of a directed graph G is a directed graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f ...
[16]
Full article: New results and open problems in line graphs
(Krausz [20]) The edges of G can be partitioned into complete subgraphs in such a way that no vertex belongs to more than two of the subgraphs.
[17]
https://doi.org/10.1016/S0021-9800(70)80019-9
[18]
[PDF] Line Graphs and Forbidden Induced Subgraphs
Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8olte s gave another characterization, ...
[19]
A max {m,n} algorithm for determining the graph H from its line graph G
In fact, root graph reconstruction has attracted the attention of researchers throughout the years (Lehot, 1974; Naor & Novick, 1990; Roussopoulos, 1973).Missing: recognition | Show results with:recognition
[20]
An Optimal Algorithm to Detect a Line Graph and Output Its Root ...
An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph. Author: Philippe G. H. Lehot ... Published: 01 October 1974 Publication History. 128 ...Missing: recognition | Show results with:recognition
[21]
ILIGRA: An Efficient Inverse Line Graph Algorithm
Apr 25, 2014 · During the root graph construction, ILIGRA checks whether the given graph H is a line graph and ILIGRA stops once it finds H is not a line graph ...
[22]
A dynamic algorithm for line graph recognition - SpringerLink
Roussopoulos. A max{m, n} Algorithm for Detecting the Graph H from its Line Graph G. Information Processing Letters2(1973), 108–112. Google Scholar. K. Simon ...
[23]
[PDF] Index of Parameters of Iterated Line Graphs - arXiv
Jan 13, 2022 · This idea of unboundedness is motivated by a well-known old result of van Rooij and Wilf that says that the number of vertices is unbounded if ...
[24]
[PDF] iterated line graphs
Iterated line graphs of G, Li(G), are defined as follows: Li (G) = ³G if i = 0; L(Li-º (G)) if i > 0.Missing: construction | Show results with:construction
[25]
[PDF] Iterated line graphs on bi-regular graphs and trees
Suppose that e = uv is an edge in G. Then degL(G) e = degG u +degG v −2. Furthermore, a vertex in G of degree d contributes ¡ d. 2. ¢ (with the convention that.
[26]
Connectivity of iterated line graphs - ScienceDirect.com
In this paper we present lower bounds for the connectivity of the i-iterated line graph Li(G) of a graph G. We prove that if G is a connected regular graph ...
[27]
(PDF) Distances in iterated line graphs - ResearchGate
Aug 5, 2025 · For a connected graph G that is not a cycle, a path or a claw, let its k-iterated line graph have the diameter diamk and the radius rk.
[28]
[2105.08610] Whitney's Theorem for Line Graphs of Multi ... - arXiv
May 18, 2021 · Whitney's Theorem states that every graph, different from K_3 or K_{1,3}, is uniquely determined by its line graph. A 1-line graph of a multi- ...
[29]
Characterizations of second iterated line graphs - Wiley Online Library
The main results of this paper are two characterizations of second iterated line graphs, i.e., two sets of necessary and sufficient conditions for the ...
[30]
Spectra and energies of iterated line graphs of regular graphs
If is a regular graph of degree , r ≥ 3 , then all negative eigenvalues of its iterated line graphs are equal to minus 2.
[31]
[PDF] arXiv:2105.08610v1 [math.CO] 18 May 2021
May 18, 2021 · Abstract. Whitney's Theorem states that every graph, different from K3 or K1,3, is uniquely determined by its line graph. A 1-line graph of ...
[32]
Line Graph of Multigraph - Math Stack Exchange
Apr 4, 2016 · So the line graph of a d-regular multigraph is regular if it is loopless and every pair of vertices is linked by either 0 or k (for some k<d) ...Clarification on the definition of multigraph - Math Stack ExchangeAmbigous line graph definition - Mathematics Stack ExchangeMore results from math.stackexchange.com
[33]
[PDF] A Survey of Line Digraphs and Generalizations
Mar 11, 2021 · The line graph transformation is one of the most widely investigated operations in graph theory. Frank Harary was the first to generalize this ...
[34]
[PDF] On the Decomposition of Total Graphs - camo
Obtaining a graph from any given graph is a popular area of research in Graph Theory. Concept of Total Graph falls under this category.
[35]
(PDF) TOTAL GRAPH OF REGULAR GRAPHS - ResearchGate
The total graph ( ) [1, 2,5,8,11,12,14] of is the graph whose vertex set is ( ) ∪ ( ) with two vertices of ( ) being adjacent if and only if the corresponding ...
[36]
[PDF] Few Results on Total Graph of Complete Graph - iarjset
The total graph T(Kn) of a complete graph Kn is formed by summing the vertices and edges of Kn, and is proven to be a strongly regular graph.
[37]
[PDF] Line Graphs of Weighted Networks for Overlapping Communities
Jun 9, 2010 · There ex- ist many other ways to project the incidence graph B(G) onto a weighted line graph4 but this definition is the one which preserves ...
[38]
Heterogeneous network flow and Petri nets characterize multilayer ...
Mar 3, 2022 · The HFN network flow, however, does due to the following property (Definition 8): the line-graph equivalent of a heterogeneous multilayer flow ...<|control11|><|separator|>
[39]
[PDF] Intersection Graphs of Graphs and Hypergraphs: A Survey - arXiv
Aug 14, 2019 · Theorem 2.2. [25] A graph G is a line graph of a graph if the edges of G can be partitioned into complete subgraphs (cliques) in ...
[40]
Line graphs of hypergraphs I - ScienceDirect.com
We define the k-line graph of a hypergraph H as the graph whose vertices are the edges of H, two vertices being joined if the edges they represent intersect ...
[41]
Hypernetwork science via high-order hypergraph walks
Jun 10, 2020 · A hypergraph in which all hyperedges have size k is called k-uniform, and a 2-uniform hypergraph is simply a graph. Definitions of hypergraphs ...<|control11|><|separator|>
[42]
A Gentle Introduction to Hypergraph Mathematics - HyperNetX
This is called the line graph, and it is an important structure which records all of the incident hyperedges. Line graphs are also used extensively in graph ...
[43]
[PDF] Disjointness graphs of short polygonal chains - arXiv
Dec 11, 2021 · Abstract. The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they ...
[44]
[PDF] Disjointness Graphs - Nathan Lindzey
Abstract. The disjointness graph of a collection of objects is defined such that two objects are ad- jacent if they are "disjoint".
[45]
Edge intersection graphs of linear 3-uniform hypergraphs
A partition of a graph into cliques satisfying the assumptions of Theorem 1 for a class P is called a Krausz-type P -decomposition. The first example of such ...
[46]
[2404.07819] Generation of $3$-connected, planar line graphs - arXiv
Apr 11, 2024 · We classify and construct all line graphs that are 3-polytopes (planar and 3-connected). Apart from a few special cases, they are all obtained starting from ...
[47]
Graphs of polyhedra; polyhedra as graphs - ScienceDirect.com
Feb 6, 2007 · However, Steinitz's theorem can also be fruitfully applied to obtain results on convex polyhedra using graph-theoretic techniques.