Line graph

Last updated

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

Contents

The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this. [1] 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, [1] as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph. [2]

HasslerWhitney  ( 1932 ) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph. [3] 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 definition

Given a graph G, its line graph L(G) is a graph such that

That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints. [2]

Example

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).

Properties

Translated properties of the underlying graph

Properties of a graph G that depend only on adjacency between edges may be translated into equivalent properties in L(G) that depend on adjacency between vertices. For instance, a matching in G is a set of edges no two of which are adjacent, and corresponds to a set of vertices in L(G) no two of which are adjacent, that is, an independent set. [4]

Thus,

Whitney isomorphism theorem

The diamond graph (left) and its more-symmetric line graph (right), an exception to the strong Whitney theorem 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 K3 and the claw K1,3, which have isomorphic line graphs but are not themselves isomorphic. [3]

As well as K3 and K1,3, 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 K1,1,2 (two triangles sharing an edge) has four graph automorphisms but its line graph K1,2,2 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. [11]

Analogues of the Whitney isomorphism theorem have been proven for the line graphs of multigraphs, but are more complicated in this case. [12]

Strongly regular and perfect line graphs

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. 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 Kn is also known as the triangular graph, the Johnson graph J(n, 2), or the complement of the Kneser graph KGn,2. Triangular graphs are characterized by their spectra, except for n = 8. [13] They may also be characterized (again with the exception of K8) as the strongly regular graphs with parameters srg(n(n – 1)/2, 2(n – 2), n – 2, 4). [14] The three strongly regular graphs with the same parameters and spectrum as L(K8) are the Chang graphs, which may be obtained by graph switching from L(K8).

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. [15] 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 L(K4,4), 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. [16]

More generally, a graph G is said to be a line perfect graph if L(G) 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. [17] Equivalently, a graph is line perfect if and only if each of its biconnected components is either bipartite or of the form K4 (the tetrahedron) or K1,1,n (a book of one or more triangles all sharing a common edge). [18] Every line perfect graph is itself perfect. [19]

All line graphs are claw-free graphs, graphs without an induced subgraph in the form of a three-leaf tree. [20] As with claw-free graphs more generally, every connected line graph L(G) with an even number of edges has a perfect matching; [21] equivalently, this means that if the underlying graph G 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. [22] 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. [23]

All eigenvalues of the adjacency matrix A of a line graph are at least −2. The reason for this is that A can be written as , where J is the signless incidence matrix of the pre-line graph and I is the identity. In particular, A + 2I is the Gramian matrix of a system of vectors: all graphs with this property have been called generalized line graphs. [24]

Characterization and recognition

Clique partition

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

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

The existence of such a partition into cliques can be used to characterize the line graphs: A graph L is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in L (allowing some of the cliques to be single vertices) that partition the edges of L, such that each vertex of L belongs to exactly two of the cliques. [20] 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 L are both in the same two cliques. Given such a family of cliques, the underlying graph G for which L is the line graph can be recovered by making one vertex in G for each clique, and an edge in G for each vertex in L with its endpoints being the two cliques containing the vertex in L. By the strong version of Whitney's isomorphism theorem, if the underlying graph G 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:

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 subgraphs

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. 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 Beineke (1970) (and reported earlier without proof by Beineke (1968)). 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 K1,3), 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. [25]

Algorithms

Roussopoulos (1973) and Lehot (1974) described linear time algorithms for recognizing line graphs and reconstructing their original graphs. Sysło (1982) generalized these methods to directed graphs. Degiorgi & Simon (1995) 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 Roussopoulos (1973) and Lehot (1974) 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 Degiorgi & Simon (1995) 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 S whose size is proportional to the number of neighbors of v. 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 operator

van Rooij & Wilf (1965) consider the sequence of graphs

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

If G is not connected, this classification applies separately to each component of G.

For connected graphs that are not paths, all sufficiently high numbers of iteration of the line graph operation produce graphs that are Hamiltonian. [27]

Generalizations

Medial graphs and convex polyhedra

When a planar graph G has maximum vertex degree three, its line graph is planar, and every planar embedding of G can be extended to an embedding of L(G). However, there exist planar graphs with higher degree whose line graphs are nonplanar. These include, for example, the 5-star K1,5, 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. [28]

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. [29]

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. [30] This operation is known variously as the second truncation, [31] degenerate truncation, [32] or rectification. [33]

Total graphs

The total graph T(G) of a graph G has as its vertices the elements (vertices or edges) of G, 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 G and then taking the square of the subdivided graph. [34]

Multigraphs

The concept of the line graph of G may naturally be extended to the case where G 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. [35]

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 K1,n 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. [12]

Line digraphs

Construction of the de Bruijn graphs as iterated line digraphs 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. [36] If G is a directed graph, its directed line graph or line digraph has one vertex for each edge of G. Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v = w. That is, each edge in the line digraph of G represents a length-two directed path in G. The de Bruijn graphs may be formed by repeating this process of forming directed line graphs, starting from a complete directed graph. [37]

Weighted line graphs

In a line graph L(G), each vertex of degree k in the original graph G creates k(k − 1)/2 edges in the line graph. For many types of analysis this means high-degree nodes in G are over-represented in the line graph L(G). For instance, consider a random walk on the vertices of the original graph G. This will pass along some edge e with some frequency f. On the other hand, this edge e is mapped to a unique vertex, say v, in the line graph L(G). If we now perform the same type of random walk on the vertices of the line graph, the frequency with which v is visited can be completely different from f. If our edge e in G was connected to nodes of degree O(k), it will be traversed O(k2) more frequently in the line graph L(G). Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph G 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. [38] For instance if edges d and e in the graph G are incident at a vertex v with degree k, then in the line graph L(G) the edge connecting the two vertices d and e can be given weight 1/(k − 1). In this way every edge in G (provided neither end is connected to a vertex of degree 1) will have strength 2 in the line graph L(G) corresponding to the two ends that the edge has in G. It is straightforward to extend this definition of a weighted line graph to cases where the original graph G was directed or even weighted. [39] The principle in all cases is to ensure the line graph L(G) reflects the dynamics as well as the topology of the original graph G.

Line graphs of hypergraphs

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 graph

The disjointness graph of G, denoted D(G), is constructed in the following way: for each edge in G, make a vertex in D(G); for every two edges in G that do not have a vertex in common, make an edge between their corresponding vertices in D(G). [40] In other words, D(G) is the complement graph of L(G). A clique in D(G) corresponds to an independent set in L(G), and vice versa.

Notes

  1. 1 2 Hemminger & Beineke (1978), p. 273.
  2. 1 2 3 Harary (1972), p. 71.
  3. 1 2 Whitney (1932); Krausz (1943); Harary (1972), Theorem 8.3, p. 72. Harary gives a simplified proof of this theorem by Jung (1966).
  4. 1 2 Paschos, Vangelis Th. (2010), Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives, John Wiley & Sons, p. 394, ISBN   9780470393673, Clearly, there is a one-to-one correspondence between the matchings of a graph and the independent sets of its line graph.
  5. The need to consider isolated vertices when considering the connectivity of line graphs is pointed out by Cvetković, Rowlinson & Simić (2004), p. 32.
  6. Harary (1972), Theorem 8.1, p. 72.
  7. Diestel, Reinhard (2006), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, p. 112, ISBN   9783540261834 . Also in free online edition, Chapter 5 ("Colouring"), p. 118.
  8. Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts, vol. 54, Cambridge: Cambridge University Press, p. 44, ISBN   0-521-82151-7, MR   1971819 . Lauri and Scapellato credit this result to Mark Watkins.
  9. Harary (1972), Theorem 8.8, p. 80.
  10. Ramezanpour, Karimipour & Mashaghi (2003).
  11. Jung (1966); Degiorgi & Simon (1995).
  12. 1 2 Zverovich (1997)
  13. van Dam, Edwin R.; Haemers, Willem H. (2003), "Which graphs are determined by their spectrum?", Linear Algebra and Its Applications, 373: 241–272, doi: 10.1016/S0024-3795(03)00483-X , MR   2022290, S2CID   32070167 . See in particular Proposition 8, p. 262.
  14. Harary (1972), Theorem 8.6, p. 79. Harary credits this result to independent papers by L. C. Chang (1959) and A. J. Hoffman (1960).
  15. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics , 164 (1): 51–229, arXiv: math/0212070 , doi:10.4007/annals.2006.164.51, S2CID   119151552 . See also Roussel, F.; Rusu, I.; Thuillier, H. (2009), "The strong perfect graph conjecture: 40 years of attempts, and its resolution", Discrete Mathematics , 309 (20): 6092–6113, doi: 10.1016/j.disc.2009.05.024 , MR   2552645, S2CID   16049392 .
  16. Harary (1972), 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.
  17. Trotter (1977); de Werra (1978).
  18. Maffray (1992).
  19. Trotter (1977).
  20. 1 2 Harary (1972), 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.
  21. Sumner, David P. (1974), "Graphs with 1-factors", Proceedings of the American Mathematical Society, 42 (1), American Mathematical Society: 8–12, doi:10.2307/2039666, JSTOR   2039666, MR   0323648 . Las Vergnas, M. (1975), "A note on matchings in graphs", Cahiers du Centre d'Études de Recherche Opérationnelle, 17 (2–3–4): 257–260, MR   0412042 .
  22. Harary (1972), Theorem 8.5, p. 78. Harary credits the result to Gary Chartrand.
  23. Erdős, Paul; Saks, Michael; Sós, Vera T. (1986), "Maximum induced trees in graphs", Journal of Combinatorial Theory, Series B, 41 (1): 61–79, doi: 10.1016/0095-8956(86)90028-6 .
  24. Cvetković, Rowlinson & Simić (2004).
  25. Metelsky & Tyshkevich (1997)
  26. This result is also Theorem 8.2 of Harary (1972).
  27. Harary (1972), Theorem 8.11, p. 81. Harary credits this result to Gary Chartrand.
  28. Sedláček (1964); Greenwell & Hemminger (1972).
  29. Archdeacon, Dan (1992), "The medial graph and voltage-current duality", Discrete Mathematics , 104 (2): 111–141, doi: 10.1016/0012-365X(92)90328-D , MR   1172842 .
  30. McKee, T. A. (1989), "Graph-theoretic model of geographic duality", Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), Ann. New York Acad. Sci., vol. 555, New York: New York Acad. Sci., pp. 310–315, Bibcode:1989NYASA.555..310M, doi:10.1111/j.1749-6632.1989.tb22465.x, MR   1018637, S2CID   86300941 .
  31. Pugh, Anthony (1976), Polyhedra: A Visual Approach, University of California Press, ISBN   9780520030565 .
  32. Loeb, Arthur Lee (1991), Space Structures—their Harmony and Counterpoint (5th ed.), Birkhäuser, ISBN   9783764335885 .
  33. Weisstein, Eric W. "Rectification". MathWorld .
  34. Harary (1972), p. 82.
  35. Ryjáček & Vrána (2011).
  36. Harary & Norman (1960).
  37. Zhang & Lin (1987).
  38. Evans & Lambiotte (2009).
  39. Evans & Lambiotte (2010).
  40. Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN   1439-6912. S2CID   207006642.

Related Research Articles

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Graph isomorphism</span> Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Perfect graph theorem</span> An undirected graph is perfect if and only if its complement graph is also perfect

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Complement graph</span> Graph with same nodes but opposite connections as another

In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

<span class="mw-page-title-main">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph is denoted by , and is the maximum of 's vertices' degrees. The minimum degree of a graph is denoted by , and is the minimum of 's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

<span class="mw-page-title-main">Graph property</span> Property of graphs that depends only on abstract structure

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Rook's graph</span> Graph of chess rook moves

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

References