Path graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about a family of graphs. For paths as parts of arbitrary graphs, see Path (graph theory).
To be distinguished from line graph.
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))1; k=1,...,n}
Properties Unit distance
Bipartite graph
Notation P_n

In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1. In particular, it has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2.


See also[edit]


External links[edit]