Path graph | |
---|---|

A path graph on 6 vertices | |

Vertices | n |

Edges | n − 1 |

Radius | ⌊n / 2⌋ |

Diameter | n − 1 |

Automorphisms | 2 |

Chromatic number | 2 |

Chromatic index | 2 |

Spectrum | {2 cos(k π / (n + 1)); k = 1, ..., n} |

Properties | Unit distance Bipartite graph Tree |

Notation | |

Table of graphs and parameters |

In the mathematical field of graph theory, a **path graph** or **linear graph** is a graph whose vertices can be listed in the order *v*_{1}, *v*_{2}, …, *v*_{n} such that the edges are {*v*_{i}, *v*_{i+1}} where *i* = 1, 2, …, *n* − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2.

Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph. A path is a particularly simple example of a tree, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A disjoint union of paths is called a linear forest.

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or Diestel (2005).

In algebra, path graphs appear as the Dynkin diagrams of type A. As such, they classify the root system of type A and the Weyl group of type A, which is the symmetric group.

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; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

In graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph. A **forest** is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In graph theory, a **tree decomposition** is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

In graph theory, a **cycle** in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A **directed cycle** in a directed graph is a non-empty directed trail in which the only repeated vertices are the first and last vertices.

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 such that 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.

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In the mathematical field of graph theory, a **spanning tree***T* of an undirected graph *G* is a subgraph that is a tree which includes all of the vertices of *G*, with a minimum possible number of edges. 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*.

In the mathematical field of graph theory, a **complete bipartite graph** or **biclique** is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In the mathematical field of graph theory, a **vertex-transitive graph** is a graph *G* in which, given any two vertices *v*_{1} and *v*_{2} of *G*, there is some automorphism

In graph theory, a **path** in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A **directed path** in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

In 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. It is not, however, the set complement of the graph; only the edges are complemented.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.

In the mathematical discipline of graph theory the **Tutte theorem**, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.

In graph theory, the **treewidth** of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: the size of the largest vertex set in a tree decomposition of the graph, the size of the largest clique in a chordal completion of the graph, the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

In the mathematical area of graph theory, **Kőnig's theorem**, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In the mathematical discipline of graph theory the **Tutte–Berge formula** is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte's theorem on perfect matchings, and is named after W. T. Tutte and Claude Berge.

In mathematics, and more specifically in graph theory, a **directed graph** is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In graph theory, a branch of mathematics, the **Herschel graph** is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel.

In graph theory, a branch of mathematics, **Fleischner's theorem** gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if *G* is a 2-vertex-connected graph, then the square of *G* is Hamiltonian. it is named after Herbert Fleischner, who published its proof in 1974.

In graph theory, a branch of mathematics, the *k*th power*G*^{k} of an undirected graph *G* is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in *G* is at most *k*. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: *G*^{2} is called the **square** of *G*, *G*^{3} is called the **cube** of *G*, etc.

- Bondy, J. A.; Murty, U. S. R. (1976).
*Graph Theory with Applications*. North Holland. pp. 12–21. ISBN 0-444-19451-7. - Diestel, Reinhard (2005).
*Graph Theory*(3rd ed.). Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.