Fact-checked by Grok 2 weeks ago

Path graph

In graph theory, a path graph P_n (for n \geq 1) is a simple, connected graph with n vertices and n-1 edges, where the vertices can be ordered as v_1, v_2, \dots, v_n such that the edges connect consecutive vertices \{v_i, v_{i+1}\} for i = 1, 2, \dots, n-1, resulting in two endpoints of degree 1 and all intermediate vertices of degree 2.^[1] This structure forms a tree that is both acyclic and minimally connected, making it one of the simplest non-trivial graphs and a foundational example in the field.^[1] Path graphs exhibit several key structural properties that highlight their role in graph enumeration and analysis. They are bipartite, as they contain no odd-length cycles, and their chromatic number is 2, with the chromatic polynomial given by z(z-1)^{n-1}.^[1] Additionally, P_n is graceful, admitting a labeling where vertices are assigned distinct integers from 0 to n-1 such that the absolute differences on edges produce distinct values from 1 to n-1.^[1] The line graph of P_n is isomorphic to P_{n-1}, and special cases include P_1 as the trivial single-vertex graph (isomorphic to K_1) and P_2 as a single edge (isomorphic to K_{2}).^[1] These graphs also have explicit independence, matching, and reliability polynomials, such as the reliability polynomial (1-p)^{n-1}, which quantifies the probability that the graph remains connected under random edge failures.^[1] As a canonical subgraph, path graphs are integral to algorithms and models in computer science and operations research, including shortest-path computations in simple networks and linear scheduling problems where tasks form sequential dependencies.^[2] They appear in transportation modeling as basic routes and in bioinformatics for representing linear DNA sequences.^[3] Their simplicity facilitates proofs of broader theorems, such as those on Hamiltonian paths in larger graphs and tree decompositions where path graphs serve as base cases due to their treewidth of 1.^[4]^[5]

Fundamentals

Definition

In graph theory, the path graph P_n (for n \geq 1) is defined as an undirected simple graph consisting of a vertex set V = \{1, 2, \dots, n\} and an edge set E = \{(i, i+1) \mid 1 \leq i \leq n-1\}, which connects the vertices in a linear sequence without branches, loops, or multiple edges. This structure forms a connected chain where each consecutive pair of vertices is adjacent, resulting in a graph that is both acyclic and minimally connected for its number of vertices. For n \geq 2, the path graph P_n is a tree, characterized by exactly two vertices of degree 1 (the endpoints, vertices 1 and n) and the remaining n-2 vertices of degree 2. In the special case n=1, P_1 consists of a single isolated vertex with no edges. This configuration underscores its role as the simplest nontrivial tree in graph theory.^[6] The concept of the path graph emerged in the foundational literature of graph theory during the 1930s, notably in the work of Dénes König, who established it as a basic linear structure in his seminal treatise on finite and infinite graphs.^[7]

Notation and Examples

In graph theory, the path graph on n vertices is standardly denoted by P_n, where n refers to the number of vertices rather than edges.^[1]^[8] While this is the most common convention, some authors, such as Reinhard Diestel, use P_n to denote a path of length n (that is, with n edges and n+1 vertices).^[6] To illustrate, consider small instances of path graphs. The graph P_1 consists of a single isolated vertex with no edges, representing the trivial path.^[1] P_2 features two vertices connected by a single edge, forming the simplest nontrivial path and isomorphic to the complete bipartite graph K_{1,1}.^[1] For P_3, three vertices are arranged linearly—labeled v_1, v_2, v_3—with edges \{v_1 v_2, v_2 v_3\}, yielding degrees of 1, 2, and 1, respectively; this is isomorphic to K_{1,2}.^[1]^[8] Extending to P_4, four vertices connect sequentially with edges between consecutive pairs, resulting in endpoint degrees of 1 and internal degrees of 2 (specifically, 1-2-2-1), which can be visualized as a straight line of vertices and edges.^[1] In general, P_n contains exactly n-1 edges and is the unique graph (up to isomorphism) satisfying the degree sequence of two vertices of degree 1 and n-2 vertices of degree 2 for n \geq 2.^[1]^[8] These examples highlight the linear, acyclic structure that defines path graphs, providing intuition for their role as fundamental building blocks in more complex networks.

Structural Properties

Connectivity and Trees

The path graph P_n on n vertices is connected, meaning there exists at least one path between every pair of distinct vertices, and in fact, there is exactly one such path, which follows the linear ordering of the vertices.^[9] This unique path property underscores the graph's minimal connectivity, as any deviation would introduce alternative routes. The diameter of P_n, defined as the length of the longest shortest path between any two vertices, is n-1, achieved between the two endpoint vertices.^[10] As a tree, P_n is an acyclic connected graph with precisely n-1 edges, satisfying the fundamental characterization of trees in graph theory.^[11] The absence of cycles follows directly from the unique path between any vertices: if a cycle existed, multiple paths would connect some pair, contradicting this property.^[9] Consequently, P_n serves as its own spanning tree, requiring no additional edges or subgraphs to connect all vertices without redundancy. All edges in P_n are bridges, such that removing any single edge disconnects the graph into two components.^[12] Regarding articulation points, or cut vertices, the two endpoints (degree 1) are not articulation points, as their removal leaves the remaining graph connected; however, every internal vertex (of degree 2) is an articulation point, since its removal separates the graph into exactly two components.

Bipartiteness and Cycles

Path graphs P_n are bipartite for every positive integer n \geq 1. The vertex set can be partitioned into two independent sets based on the parity of the vertex indices: one set consisting of vertices with odd indices (e.g., v_1, v_3, \dots) and the other with even indices (e.g., v_2, v_4, \dots). All edges connect a vertex from the odd set to one in the even set, ensuring no edges within either set.^[1]^[13] This bipartition enables 2-coloring of the graph, where vertices in the odd set receive one color and those in the even set receive the other, with colors alternating along the path. The absence of odd cycles in P_n guarantees this property, as bipartite graphs are precisely those without odd-length cycles. As a tree, the path graph contains no cycles at all, meaning there are no simple closed paths of length 3 or greater. All closed walks are of even length due to bipartiteness.^[1]^[14] The sizes of the two partitions depend on the parity of n. For even n, both sets have equal size n/2. For odd n, the sets are unequal, with sizes (n+1)/2 and (n-1)/2, the larger set containing the endpoints. This imbalance for odd-length paths highlights the linear structure, where the two ends fall into the same partition.^[1]

Algebraic and Spectral Properties

Adjacency Matrix and Eigenvalues

The adjacency matrix A of the path graph P_n on n vertices, labeled sequentially from 1 to n, is the n \times n symmetric tridiagonal matrix with zeros along the main diagonal and ones along the subdiagonal and superdiagonal, so A_{i,i+1} = A_{i+1,i} = 1 for i = 1, \dots, n-1, and all other entries zero.^[15] The eigenvalues of A are given by \lambda_k = 2 \cos \left( \frac{\pi k}{n+1} \right) for integers k = 1, 2, \dots, n, all distinct and lying in the interval (-2, 2).^[15] The corresponding eigenvectors v_k have components v_{j,k} = \sin \left( \frac{\pi j k}{n+1} \right) for j = 1, \dots, n, forming an orthogonal basis that diagonalizes A.^[16] The largest eigenvalue is \lambda_1 = 2 \cos \left( \frac{\pi}{n+1} \right), which approaches 2 as n \to \infty and equals the spectral radius of A; this limit aligns with the maximum degree of 2 in P_n, providing insight into the graph's expansion properties via the Perron-Frobenius theorem for nonnegative matrices.^[15] These spectral properties arise from solving the characteristic equation \det(A - \lambda I) = 0, which yields a recurrence relation for the principal minors of the tridiagonal matrix, solvable using trigonometric identities or connections to Chebyshev polynomials of the second kind.^[16]

Chromatic and Independence Numbers

The chromatic number of the path graph P_n is \chi(P_n) = 2 for n \geq 2, reflecting its bipartite structure that allows a proper vertex coloring with two colors by alternating along the path, while \chi(P_1) = 1 for the single-vertex graph.^[11] The chromatic polynomial of P_n is given by x(x-1)^{n-1}, which counts the number of proper colorings with x colors and confirms the chromatic number as the smallest x for which this polynomial is positive.^[1] The independence number \alpha(P_n) is \lceil n/2 \rceil, the size of the largest independent set of non-adjacent vertices, achieved by selecting every other vertex starting from one endpoint (for example, vertices 1, 3, 5, ... in a path labeled sequentially from 1 to n).^[11] This maximum is tight, as adding any additional vertex would introduce an adjacency within the set. The clique number \omega(P_n) = 2 for n \geq 2, since the largest complete subgraph is any single edge in the path, and no triangles or larger cliques exist due to the linear structure without branches or cycles.^[11] The domination number \gamma(P_n) = \lceil n/3 \rceil, the cardinality of the smallest dominating set where every vertex is either in the set or adjacent to one in it, obtained by positioning dominators at intervals of three vertices (e.g., vertices 2, 5, 8, ... adjusted for the path length).^[17]

Applications

In Network Modeling

Path graphs are frequently employed to model linear processes in network systems, where vertices represent sequential stages and edges denote transitions between them. In supply chain management, complex networks can be decomposed into path graphs to represent linear flows of goods from suppliers to consumers, facilitating efficient data storage and querying for RFID-tracked items. For instance, a split-path schema transforms intricate supply chain structures into path graphs that are further divided into tree-like components for optimized processing and analysis. Similarly, in manufacturing, conveyor systems are modeled using path graphs to simulate sequential material transport, enabling reconfiguration strategies that search for optimal paths during automation adjustments. In algorithmic applications, the shortest path problem in a path graph P_n (with n vertices) is trivial, as the unique path between any two vertices is the direct subpath connecting them along the chain, requiring no complex computation beyond direct traversal. Path graphs serve as foundational examples in dynamic programming approaches to path-finding, where the linear structure allows recursive computation of optimal subpaths, often extended to solve problems like the weighted independent set on paths or longest paths in acyclic graphs. As benchmarks for tree traversal algorithms, path graphs test efficiency in operations like depth-first search (DFS), which completes in O(n) time due to the absence of branches, providing a baseline for evaluating scalability in multi-agent path-finding scenarios. In computer science, path graphs model linear data structures such as singly linked lists, where nodes form a chain without cycles, aiding in analyses of memory allocation and traversal efficiency. They also represent file paths in hierarchical file systems as sequences of directories, supporting operations like permission propagation along the path. Furthermore, path graphs play a role in approximating the traveling salesman problem (TSP) for near-linear instances, where the optimal tour approximates a Hamiltonian path; approximation algorithms for the s-t path TSP achieve factors like 3/2 by leveraging linear programming relaxations on path-like graphs, improving solutions for logistics with sequential constraints.

As Dynkin Diagrams in Lie Theory

In the classification of semisimple Lie algebras over the complex numbers, the path graph plays a central role as the Dynkin diagram of type A_n, which consists of n nodes arranged in a linear chain connected by single edges, corresponding precisely to the path graph P_n with n vertices.^[18] This diagram encodes the structure of the simple roots for the root system of rank n, where the nodes represent the simple roots and the single edges indicate an angle of 120 degrees between adjacent roots, characteristic of simply-laced diagrams with no multiple bonds.^[19] The A_n Dynkin diagram is associated with the special linear Lie algebra \mathfrak{sl}(n+1, \mathbb{C}), which has dimension (n+1)^2 - 1 and realizes the root system through its Cartan subalgebra and root spaces.^[18] The Weyl group of this root system is the symmetric group S_{n+1}, acting as the group of permutations on n+1 elements, which permutes the roots while preserving the positive root system.^[20] This connection highlights the path graph's utility in capturing the combinatorial symmetries underlying the representations of \mathfrak{sl}(n+1, \mathbb{C}), such as those appearing in quantum mechanics and particle physics. Dynkin diagrams, including the A_n series, were formalized in the 1940s by Eugene Dynkin in his work on classifying semisimple Lie algebras, building on earlier ideas from Harold Coxeter's diagrams for reflection groups in the 1930s.^[21] Dynkin's approach, detailed in his 1947 paper "The structure of semisimple Lie algebras," used these graphs to simplify the determination of Cartan matrices and root systems, establishing the finite simply-laced cases like A_n as fundamental in the ADE classification.^[21]

Generalizations

Directed and Oriented Paths

A directed path graph on n vertices, denoted \overrightarrow{P_n}, is a directed graph (digraph) with vertex set \{v_1, v_2, \dots, v_n\} and arcs oriented consecutively from v_i to v_{i+1} for i = 1, 2, \dots, n-1.^[22] This structure has a unique source vertex v_1 with in-degree 0 and out-degree 1, a unique sink vertex v_n with in-degree 1 and out-degree 0, and all internal vertices v_i (for $2 \leq i \leq n-1) with both in-degree and out-degree equal to 1.^[22]^[11] As a basic building block in digraph theory, the directed path graph is acyclic, forming a directed acyclic graph (DAG) with no directed cycles, which aligns with its topological ordering from v_1 to v_n.^[11] The longest directed path within \overrightarrow{P_n} spans the entire graph, with length n-1 (measured in arcs), and the graph itself constitutes a Hamiltonian path that visits every vertex exactly once.^[22]^[11] Oriented paths generalize this by considering any orientation of the underlying undirected path graph P_n, where each edge receives a direction without creating bidirectional arcs.^[23] Unlike the uniform forward orientation of the directed path, oriented paths may include reversals, leading to varied in- and out-degree distributions at endpoints and internals, while preserving the tree-like acyclicity of the undirected base.^[23] These structures find applications in modeling sequential, one-way processes, such as assembly line scheduling where tasks form a linear precedence chain represented by directed paths to optimize flow without cycles.^[24] Similarly, they capture temporal dependencies in time series data, treating observations as vertices with directed arcs indicating causal or sequential influences.^[25]

Infinite and Circular Variants

The infinite path graph generalizes the finite path P_n by extending it indefinitely. A one-sided infinite path, also known as a ray, is a countable infinite graph with vertices labeled v_0, v_1, v_2, \dots and edges connecting consecutive vertices \{v_i v_{i+1} \mid i \geq 0\}.^[26] This structure has one endpoint at v_0 (degree 1) and all other vertices of degree 2, making it a tree with infinite extent in one direction.^[27] A bi-infinite path, or double ray, extends in both directions with vertices \{\dots, v_{-1}, v_0, v_1, \dots\} indexed by the integers \mathbb{Z} and edges \{v_i v_{i+1} \mid i \in \mathbb{Z}\}; it has no endpoints, all vertices degree 2, and is the unique connected 2-regular infinite graph up to isomorphism.^[26] These infinite paths find applications in modeling linear arrangements, such as in tiling theory where the existence of a tiling of the real line \mathbb{R} corresponds to an infinite path in a compatibility graph of tile types.^[28] In aperiodic structures, infinite paths serve as building blocks for analyzing non-periodic sequences and hierarchical substitutions, providing a framework for infinite extensions without cycles.^[28] The circular variant of the path graph is the cycle graph C_n for n \geq 3, formed by adding an edge between the endpoints of the finite path P_n.^[13] This closes the structure into a single cycle, resulting in a connected 2-regular graph with n vertices and n edges, where every vertex has degree 2.^[26] Unlike the path graph, C_n contains a cycle and thus is not a tree; its girth, the length of the shortest cycle, is exactly n.^[26] As a connected graph with all even degrees, C_n admits an Eulerian circuit—a closed trail traversing each edge exactly once.^[29]

References

[1]
Path Graph -- from Wolfram MathWorld
A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line.
[2]
[PDF] A Study on Path Related Problems in Graphs - IOSR Journal
They are widely used in various applications, including computer science, network optimization, social network analysis, and transportation systems. Path ...<|control11|><|separator|>
[3]
Applications of Graph Theory - GeeksforGeeks
Aug 26, 2025 · Graph theory is essential in modeling transportation networks, including road networks, railway systems, and flight routes. It enables efficient ...
[4]
None
### Summary of Path Graph Content
[5]
[PDF] The Basics
Section 1.1 offers a brief but self-contained summary of the most basic definitions in graph theory, those centred round the notion of a ... Our formal definition ...Missing: Pn | Show results with:Pn
[6]
Theory of Finite and Infinite Graphs
Konig, D. (Denes), 1884-1944. [Theorie der endlichen und unendlichen Graphen. English]. Theory of finite and infinite graphs 1 Denes Konig ; translated by.
[7]
[PDF] Discrete Mathematics, Spring 2009 Graph theory notation
Mar 5, 2009 · Paths and cycles: a graph on n vertices is called a path (of length n − 1) if the vertices can be labeled as v1,...,vn in such a way that E = { ...Missing: P_n | Show results with:P_n
[8]
Graph Theory in Practice: Part II | American Scientist
A connected graph must have at least n-1 edges, and its largest possible diameter is n-1. At the opposite extreme, a complete graph, with n2/2 edges, has a ...
[9]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.Missing: P_n | Show results with:P_n
[10]
[PDF] Chapter 6: Graph Theory
Properties of Trees: 1. If a graph is a tree, there is one and only one path joining any two vertices. Conversely, if there is ...
[11]
Graph Theory - 2-Vertex-Connected Graphs - Tutorials Point
No Cut Vertices: A 2-vertex-connected graph has no articulation points. ... Removing a non-leaf vertex disconnects the tree. Grid Graph, Depends, Depends ...<|separator|>
[12]
[PDF] Math 3322: Graph Theory - Chapters 1–4 - Faculty Web Pages
Feb 17, 2021 · Graphs that just happen to be bipartite because of their structure. Example: a path graph is bipartite because all edges join an even ...
[13]
17.6 Cycles and Trees - Computer Science
Diagram of a path graph. We might consider some simple examples to gain some ... We say that G is a tree when it is connected and has no cycles. Wait a ...
[14]
[PDF] Spectra of graphs - CWI
The eigenvalues are θk = 2cos(kπ/(n + 1)) for k = 1,...,n. The ... of two paths Pm, with largest eigenvalue λ = 2 cos π/(m + 1). If n = 2m is ...
[15]
Eigenvalues of Graphs - American Mathematical Society
In this chapter we demonstrate how certain linear algebraic properties of the adjacency matrix of a graph can be used to obtain information about structural ...Missing: sine | Show results with:sine
[16]
Independent Domination Subdivision in Graphs
Mar 13, 2021 · ... domination number. We show that for every connected graph G on at ... P_n) = \left\{ \begin{array}{lc} 1 &{} \text{ if } n \equiv 0 ...<|control11|><|separator|>
[17]
Dynkin Diagram -- from Wolfram MathWorld
Every semisimple Lie algebra g is classified by its Dynkin diagram. A Dynkin diagram is a graph with a few different kinds of possible edges.Missing: path | Show results with:path
[18]
[PDF] root systems and dynkin diagrams - Cornell Mathematics
It is the root system of the Lie algebra An = sln+1(C). The symmetry of a root system defined by “reflect through the hyperplane perpendicular to α” is given by ...Missing: S | Show results with:S
[19]
[PDF] Reference sheet for classical roots systems - UC Berkeley math
Sep 21, 2023 · Mnemonic: “sln is the first semisimple Lie algebra you ever learn about, so its Dynkin diagram comes first in the alphabet.” • Weyl group: Sn.Missing: S | Show results with:S
[20]
Evgenii B Dynkin (1924 - 2014) - Biography - MacTutor
Dynkin's most famous contribution to the theory of Lie algebras was his use of the "Coxeter-Dynkin diagrams" to describe and classify the Cartan matrices of ...
[21]
[PDF] 5 Directed Graphs
Directed Path a graph whose vertex set may be numbered {v1,...,vn} and edges may be numbered {e1,...,en−1} so that ei = (vi,vi+1) for every 1 ≤ i ≤ n − 1.
[22]
[PDF] Oriented trees and paths in digraphs - arXiv
May 24, 2024 · Every (k + 1)-chromatic oriented graph contains each oriented path with k edges. There is some support for this conjecture, apart from it ...
[23]
Graph-Based Modeling in Shop Scheduling Problems: Review and ...
The feasible solution is the directed path which visits every node, completing every operation [160]. 6. Overview of the Full Dataset. According to the ...
[24]
[PDF] Graph Neural Networks and Time Series as Directed Graphs ... - arXiv
Oct 4, 2023 · In this paper, we see time series themselves as directed graphs, so that their topology encodes time dependencies and we start to explore the ...Missing: path | Show results with:path
[25]
[PDF] Infinite Graphs
The study of infinite graphs is an attractive, but often neglected, part of graph theory. This chapter aims to give an introduction that starts gent-.
[26]
[PDF] Section 1.6. Infinite Graphs
Sep 17, 2022 · A one-way infinite path is an infinite countable simple graph whose vertices can be arranged in an infinite linear sequence, say v1,v2,..., ...
[27]
[PDF] 1. Aperiodic Order – Introduction A tiling (or tesselation) of Rd is a ...
A tiling of R exists if and only if there is an infinite path in this graph, which is equivalent to existence of a cycle. Definition 1.1. A tiling Τ of Rd ...
[28]
Euler Paths and Circuits - Discrete Mathematics
An Euler circuit is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an ...