In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+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).
path, graph, this, article, about, family, graphs, paths, parts, arbitrary, graphs, path, graph, theory, confused, with, line, graph, mathematical, field, graph, theory, path, graph, linear, graph, graph, whose, vertices, listed, order, such, that, edges, wher. This article is about a family of graphs For paths as parts of arbitrary graphs see Path graph theory Not to be confused with line graph In the mathematical field of graph theory a path graph or linear graph is a graph whose vertices can be listed in the order v1 v2 vn such that the edges are vi vi 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 Path graphA path graph on 6 verticesVerticesnEdgesn 1Radius n 2 Diametern 1Automorphisms2Chromatic number2Chromatic index2Spectrum 2 cos k p n 1 displaystyle 2 cos left frac k pi n 1 right k 1 n displaystyle k 1 cdots n PropertiesUnit distanceBipartite graphTreeNotationPn 1 Table of graphs and parameters 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 Contents 1 As Dynkin diagrams 2 See also 3 References 4 External linksAs Dynkin diagrams editIn 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 See also editPath graph theory Caterpillar tree Complete graph Null graph Path decomposition Cycle graph theory References edit While it is most common to use Pn for a path of n vertices some authors e g Diestel use Pn for a path of n edges and n 1 vertices 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 External links editWeisstein Eric W Path Graph MathWorld Retrieved from https en wikipedia org w index php title Path graph amp oldid 1188885033, wikipedia, wiki, book, books, library,
