Graph Path

A path in a graph  is a subgraph of  that is a path graph (West 2000, p. 20). The length of a path is the number of edges it contains.

In most contexts, a path must contain at least one edge, though in some applications (e.g., defining the path covering number), "degenerate" paths of length 0 consisting of a single vertex are allowed (Boesch et al. 1974).

An -path is a path whose endpoints (vertices of degree 1) are the vertices with distinct indices  and . (The symbols  and  are also commonly used.) A single -path may be found in the Wolfram Language using FindPath[g, s, t], while FindPath[g, s, t, kspec, n] finds at most  paths of length kspec (where kspec may be Infinity and  may be All).

For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph , a Hamiltonian path is a path that includes all vertices of  (and whose endpoints are not adjacent).

The number of (undirected) -walks from vertex  to vertex  in a graph with adjacency matrix  is given by the  element of  (Festinger 1949). In order to compute the number  of graph paths, all closed -walks that are not paths must be subtracted.

The first few matrices of -paths  can be given in closed form by

			(1)
			(2)
			(3)

(Luce and Perry 1949, Katz 1950, Ross and Harary 1952, Perepechko and Voropaev), where  is the matrix formed from the diagonal elements of  and  denotes matrix element-wise multiplication.

Furthermore, the number of -cycles is related to  by

(4)

where  denotes the trace.

Giscard et al. (2016) gave the formula for the path matrix giving the number of -paths from  to  as

(5)

where the sum is over connected induced subgraphs  of  containing both  and ,  denotes the number of neighbors of  in  (namely vertices  of  which are not in  and such that there exists at least one edge from  to a vertex of ),  denotes the matrix trace, and  is the th element of the th matrix power of the adjacency matrix of  restricted to the connected induced subgraph , namely

(6)

with .

REFERENCES

Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.

Giscard, P.-L. and Rochet, P. "Enumerating Simple Paths from Connected Induced Subgraphs." 1 Jun 2016. https://arxiv.org/abs/1606.00289.

Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. https://arxiv.org/pdf/1612.05531.pdf.

Festinger, L. "The Analysis of Sociograms Using Matrix Algebra." Human Relations 2, 153-158, 1949.

Katz, L. "An Application of Matrix Algebra to the Study of Human Relations Within Organizations." Institute of Statistics, University of North Carolina, Mimeograph Series, 1950.

Luce, R. D. and Perry, A. D. "A Method of Matrix Analysis of Group Structure." Psychometrika 14, 95-116, 1949.

Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Roberts, B. and Kroese, D. P. "Estimating the number of  Paths in a Graph." J. Graph Algorithms Appl. 11, 195-214, 2007.

Ross, I. C. and Harary, F. "On the Determination of Redundancies in Sociometric Chains." Psychometrika 17, 195-208, 1952.

Valiant, L. G. "The Complexity of Enumeration and Reliability Problems." SIAM J. Computing 8, 410-421, 1979.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 20, 2000.