Incubator escapee wiki

Line graph

Article Discussion
Revision as of 18:02, 9 May 2025 by imported>MrSwedishMeatballs (→‎Strongly regular and perfect line graphs)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:Short description Template:About Template:Distinguish

In the mathematical discipline of graph theory, the line graph of an undirected graph Template:Mvar is another graph Template:Math that represents the adjacencies between edges of Template:Mvar. Template:Math is constructed in the following way: for each edge in Template:Mvar, make a vertex in Template:Math; for every two edges in Template:Mvar that have a vertex in common, make an edge between their corresponding vertices in Template:Math.

The name line graph comes from a paper by Template:Harvtxt although both Template:Harvtxt and Template:Harvtxt used the construction before this.Template:Sfnp Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom,Template:Sfnp as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph.<ref name="h72-71">Template:Harvtxt, p. 71.</ref>

Template:Harvs proved that with one exceptional case the structure of a connected graph Template:Mvar can be recovered completely from its line graph.<ref name="whitney"/> Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same translation can also be done in the other direction. Line graphs are claw-free, and the line graphs of bipartite graphs are perfect. Line graphs are characterized by nine forbidden subgraphs and can be recognized in linear time.

Various extensions of the concept of a line graph have been studied, including line graphs of line graphs, line graphs of multigraphs, line graphs of hypergraphs, and line graphs of weighted graphs.

Formal definitionEdit

Given a graph Template:Mvar, its line graph Template:Math is a graph such that

That is, it is the intersection graph of the edges of Template:Mvar, representing each edge by the set of its two endpoints.<ref name="h72-71"/>

ExampleEdit

The following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices). Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. For instance, the green vertex on the right labeled 1,3 corresponds to the edge on the left between the blue vertices 1 and 3. Green vertex 1,3 is adjacent to three other green vertices: 1,4 and 1,2 (corresponding to edges sharing the endpoint 1 in the blue graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the blue graph).

  • Line graph construction 1.svg

    Graph G

  • Line graph construction 2.svg

    Vertices in L(G) constructed from edges in G

  • Line graph construction 3.svg

    Added edges in L(G)

  • Line graph construction 4.svg

    The line graph L(G)

PropertiesEdit

Translated properties of the underlying graphEdit

Properties of a graph Template:Mvar that depend only on adjacency between edges may be translated into equivalent properties in Template:Math that depend on adjacency between vertices. For instance, a matching in Template:Mvar is a set of edges no two of which are adjacent, and corresponds to a set of vertices in Template:Math no two of which are adjacent, that is, an independent set.<ref name="paschos">Template:Citation</ref>

Thus,

Whitney isomorphism theoremEdit

File:Diamond line graph.svg
The diamond graph (left) and its more-symmetric line graph (right), an exception to the strong Whitney theorem

If the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph Template:Math and the claw Template:Math, which have isomorphic line graphs but are not themselves isomorphic.<ref name="whitney">Template:Harvtxt; Template:Harvtxt; Template:Harvtxt, Theorem 8.3, p. 72. Harary gives a simplified proof of this theorem by Template:Harvtxt.</ref>

As well as Template:Math and Template:Math, there are some other exceptional small graphs with the property that their line graph has a higher degree of symmetry than the graph itself. For instance, the diamond graph Template:Math (two triangles sharing an edge) has four graph automorphisms but its line graph Template:Math has eight. In the illustration of the diamond graph shown, rotating the graph by 90 degrees is not a symmetry of the graph, but is a symmetry of its line graph. However, all such exceptional cases have at most four vertices. A strengthened version of the Whitney isomorphism theorem states that, for connected graphs with more than four vertices, there is a one-to-one correspondence between isomorphisms of the graphs and isomorphisms of their line graphs.<ref>Template:Harvtxt; Template:Harvtxt.</ref>

Analogues of the Whitney isomorphism theorem have been proven for the line graphs of multigraphs, but are more complicated in this case.<ref name="z97"/>

Strongly regular and perfect line graphsEdit

File:Line perfect graph.svg
A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.

The line graph of the complete graph Template:Mvar is also known as the triangular graph, the Johnson graph Template:Math, or the complement of the Kneser graph Template:Math. Triangular graphs are characterized by their spectra, except for Template:Math.<ref>Template:Citation. See in particular Proposition 8, p. 262.</ref> They may also be characterized (again with the exception of Template:Math) as the strongly regular graphs with parameters Template:Math.<ref>Template:Harvtxt, Theorem 8.6, p. 79. Harary credits this result to independent papers by L. C. Chang (1959) and A. J. Hoffman (1960).</ref> The three strongly regular graphs with the same parameters and spectrum as Template:Math are the Chang graphs, which may be obtained by graph switching from Template:Math.

The line graph of a bipartite graph is perfect (see Kőnig's theorem), but need not be bipartite as the example of the claw graph shows. The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the strong perfect graph theorem.<ref>Template:Citation. See also Template:Citation.</ref> A special case of these graphs are the rook's graphs, line graphs of complete bipartite graphs. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non-adjacent points. The one exceptional case is Template:Math, which shares its parameters with the Shrikhande graph. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular.<ref>Template:Harvtxt, Theorem 8.7, p. 79. Harary credits this characterization of line graphs of complete bipartite graphs to Moon and Hoffman. The case of equal numbers of vertices on both sides had previously been proven by Shrikhande.</ref> It has been shown that, except for Template:Math , Template:Math , and Template:Math , all connected strongly regular graphs can be made non-strongly regular within two line graph transformations.<ref> Template:Cite arxiv </ref> The extension to disconnected graphs would require that the graph is not a disjoint union of Template:Math.

More generally, a graph Template:Mvar is said to be a line perfect graph if Template:Math is a perfect graph. The line perfect graphs are exactly the graphs that do not contain a simple cycle of odd length greater than three.<ref>Template:Harvtxt; Template:Harvtxt.</ref> Equivalently, a graph is line perfect if and only if each of its biconnected components is either bipartite or of the form Template:Math (the tetrahedron) or Template:Math (a book of one or more triangles all sharing a common edge).Template:Sfnp Every line perfect graph is itself perfect.Template:Sfnp

Other related graph familiesEdit

All line graphs are claw-free graphs, graphs without an induced subgraph in the form of a three-leaf tree.<ref name="h72-8.4"/> As with claw-free graphs more generally, every connected line graph Template:Math with an even number of edges has a perfect matching;<ref>Template:Citation. Template:Citation.</ref> equivalently, this means that if the underlying graph Template:Mvar has an even number of edges, its edges can be partitioned into two-edge paths.

The line graphs of trees are exactly the claw-free block graphs.<ref>Template:Harvtxt, Theorem 8.5, p. 78. Harary credits the result to Gary Chartrand.</ref> These graphs have been used to solve a problem in extremal graph theory, of constructing a graph with a given number of edges and vertices whose largest tree induced as a subgraph is as small as possible.<ref>Template:Citation.</ref>

All eigenvalues of the adjacency matrix Template:Mvar of a line graph are at least −2. The reason for this is that Template:Mvar can be written as <math>A = J^\mathsf{T}J - 2I</math>, where Template:Mvar is the signless incidence matrix of the pre-line graph and Template:Mvar is the identity. In particular, Template:Math is the Gramian matrix of a system of vectors: all graphs with this property have been called generalized line graphs.Template:Sfnp

Characterization and recognitionEdit

Clique partitionEdit

File:Line graph clique partition.svg
Partition of a line graph into cliques

For an arbitrary graph Template:Mvar, and an arbitrary vertex Template:Mvar in Template:Mvar, the set of edges incident to Template:Mvar corresponds to a clique in the line graph Template:Math. The cliques formed in this way partition the edges of Template:Math. Each vertex of Template:Math belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in Template:Mvar).

The existence of such a partition into cliques can be used to characterize the line graphs: A graph Template:Mvar is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in Template:Mvar (allowing some of the cliques to be single vertices) that partition the edges of Template:Mvar, such that each vertex of Template:Mvar belongs to exactly two of the cliques.<ref name="h72-8.4">Template:Harvtxt, Theorem 8.4, p. 74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being claw-free and odd diamond-free, and the nine forbidden graphs of Beineke.</ref> It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of Template:Mvar are both in the same two cliques. Given such a family of cliques, the underlying graph Template:Mvar for which Template:Mvar is the line graph can be recovered by making one vertex in Template:Mvar for each clique, and an edge in Template:Mvar for each vertex in Template:Mvar with its endpoints being the two cliques containing the vertex in Template:Mvar. By the strong version of Whitney's isomorphism theorem, if the underlying graph Template:Mvar has more than four vertices, there can be only one partition of this type.

For example, this characterization can be used to show that the following graph is not a line graph:

File:LineGraphExampleA.svg

In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. Therefore, any partition of the graph's edges into cliques would have to have at least one clique for each of these three edges, and these three cliques would all intersect in that central vertex, violating the requirement that each vertex appear in exactly two cliques. Thus, the graph shown is not a line graph.

Forbidden subgraphsEdit

File:Forbidden line subgraphs.svg
The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.

Another characterization of line graphs was proven in Template:Harvtxt (and reported earlier without proof by Template:Harvtxt). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an induced subgraph. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a complete bipartite graph Template:Math), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.<ref name="mt97">Template:Harvtxt</ref>

AlgorithmsEdit

Template:Harvtxt and Template:Harvtxt described linear time algorithms for recognizing line graphs and reconstructing their original graphs. Template:Harvtxt generalized these methods to directed graphs. Template:Harvtxt described an efficient data structure for maintaining a dynamic graph, subject to vertex insertions and deletions, and maintaining a representation of the input as a line graph (when it exists) in time proportional to the number of changed edges at each step.

The algorithms of Template:Harvtxt and Template:Harvtxt are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of Template:Harvtxt uses only Whitney's isomorphism theorem. It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:

Each step either takes constant time, or involves finding a vertex cover of constant size within a graph Template:Mvar whose size is proportional to the number of neighbors of Template:Mvar. Thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the handshaking lemma) is proportional to the number of input edges.

Iterating the line graph operatorEdit

Template:Harvtxt consider the sequence of graphs

<math>G, L(G), L(L(G)), L(L(L(G))), \dots.\ </math>

They show that, when Template:Mvar is a finite connected graph, only four behaviors are possible for this sequence:

If Template:Mvar is not connected, this classification applies separately to each component of Template:Mvar.

For connected graphs that are not paths, all sufficiently high numbers of iteration of the line graph operation produce graphs that are Hamiltonian.<ref>Template:Harvtxt, Theorem 8.11, p. 81. Harary credits this result to Gary Chartrand.</ref>

GeneralizationsEdit

Medial graphs and convex polyhedraEdit

Template:Main article When a planar graph Template:Mvar has maximum vertex degree three, its line graph is planar, and every planar embedding of Template:Mvar can be extended to an embedding of Template:Math. However, there exist planar graphs with higher degree whose line graphs are nonplanar. These include, for example, the 5-star Template:Math, the gem graph formed by adding two non-crossing diagonals within a regular pentagon, and all convex polyhedra with a vertex of degree four or more.<ref>Template:Harvtxt; Template:Harvtxt.</ref>

An alternative construction, the medial graph, coincides with the line graph for planar graphs with maximum degree three, but is always planar. It has the same vertices as the line graph, but potentially fewer edges: two vertices of the medial graph are adjacent if and only if the corresponding two edges are consecutive on some face of the planar embedding. The medial graph of the dual graph of a plane graph is the same as the medial graph of the original plane graph.<ref>Template:Citation.</ref>

For regular polyhedra or simple polyhedra, the medial graph operation can be represented geometrically by the operation of cutting off each vertex of the polyhedron by a plane through the midpoints of all its incident edges.<ref>Template:Citation.</ref> This operation is known variously as the second truncation,<ref>Template:Citation.</ref> degenerate truncation,<ref>Template:Citation.</ref> or rectification.<ref>Template:Mathworld</ref>

Total graphsEdit

The total graph Template:Math of a graph Template:Mvar has as its vertices the elements (vertices or edges) of Template:Mvar, and has an edge between two elements whenever they are either incident or adjacent. The total graph may also be obtained by subdividing each edge of Template:Mvar and then taking the square of the subdivided graph.<ref>Template:Harvtxt, p. 82.</ref>

MultigraphsEdit

The concept of the line graph of Template:Mvar may naturally be extended to the case where Template:Mvar is a multigraph. In this case, the characterizations of these graphs can be simplified: the characterization in terms of clique partitions no longer needs to prevent two vertices from belonging to the same to cliques, and the characterization by forbidden graphs has seven forbidden graphs instead of nine.Template:Sfnp

However, for multigraphs, there are larger numbers of pairs of non-isomorphic graphs that have the same line graphs. For instance a complete bipartite graph Template:Math has the same line graph as the dipole graph and Shannon multigraph with the same number of edges. Nevertheless, analogues to Whitney's isomorphism theorem can still be derived in this case.<ref name="z97">Template:Harvtxt</ref>

Line digraphsTemplate:AnchorEdit

File:DeBruijn-as-line-digraph.svg
Construction of the de Bruijn graphs as iterated line digraphs

It is also possible to generalize line graphs to directed graphs.Template:Sfnp If Template:Mvar is a directed graph, its directed line graph or line digraph has one vertex for each edge of Template:Mvar. Two vertices representing directed edges from Template:Mvar to Template:Mvar and from Template:Mvar to Template:Mvar in Template:Mvar are connected by an edge from Template:Mvar to Template:Mvar in the line digraph when Template:Math. That is, each edge in the line digraph of Template:Mvar represents a length-two directed path in Template:Mvar. The de Bruijn graphs may be formed by repeating this process of forming directed line graphs, starting from a complete directed graph.Template:Sfnp

Weighted line graphsEdit

In a line graph Template:Math, each vertex of degree Template:Mvar in the original graph Template:Mvar creates Template:Math edges in the line graph. For many types of analysis this means high-degree nodes in Template:Mvar are over-represented in the line graph Template:Math. For instance, consider a random walk on the vertices of the original graph Template:Mvar. This will pass along some edge Template:Mvar with some frequency Template:Mvar. On the other hand, this edge Template:Mvar is mapped to a unique vertex, say Template:Mvar, in the line graph Template:Math. If we now perform the same type of random walk on the vertices of the line graph, the frequency with which Template:Mvar is visited can be completely different from f. If our edge Template:Mvar in Template:Mvar was connected to nodes of degree Template:Math, it will be traversed Template:Math more frequently in the line graph Template:Math. Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph Template:Mvar faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship. One solution is to construct a weighted line graph, that is, a line graph with weighted edges. There are several natural ways to do this.Template:Sfnp For instance if edges Template:Mvar and Template:Mvar in the graph Template:Mvar are incident at a vertex Template:Mvar with degree Template:Mvar, then in the line graph Template:Math the edge connecting the two vertices Template:Mvar and Template:Mvar can be given weight Template:Math. In this way every edge in Template:Mvar (provided neither end is connected to a vertex of degree 1) will have strength 2 in the line graph Template:Math corresponding to the two ends that the edge has in Template:Mvar. It is straightforward to extend this definition of a weighted line graph to cases where the original graph Template:Mvar was directed or even weighted.Template:Sfnp The principle in all cases is to ensure the line graph Template:Math reflects the dynamics as well as the topology of the original graph Template:Mvar.

Line graphs of hypergraphsEdit

Template:Main article The edges of a hypergraph may form an arbitrary family of sets, so the line graph of a hypergraph is the same as the intersection graph of the sets from the family.

Disjointness graphEdit

The disjointness graph of Template:Mvar, denoted Template:Math, is constructed in the following way: for each edge in Template:Mvar, make a vertex in Template:Math; for every two edges in Template:Mvar that do not have a vertex in common, make an edge between their corresponding vertices in Template:Math.<ref>Template:Cite journal</ref> In other words, Template:Math is the complement graph of Template:Math. A clique in Template:Math corresponds to an independent set in Template:Math, and vice versa.

NotesEdit

Template:Reflist

ReferencesEdit

Template:Refbegin

Template:Refend

External linksEdit

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Line_graph&oldid=403410"