Panconnectivity Explained

In graph theory, a panconnected graph is an undirected graph in which, for every two vertices and, there exist paths from to of every possible length from the distance up to, where is the number of vertices in the graph. The concept of panconnectivity was introduced in 1975 by Yousef Alavi and James E. Williamson.^[1]

Panconnected graphs are necessarily pancyclic: if is an edge, then it belongs to a cycle of every possible length, and therefore the graph contains a cycle of every possible length.Panconnected graphs and are also a generalization of Hamiltonian-connected graphs (graphs that have a Hamiltonian path connecting every pair of vertices).

Several classes of graphs are known to be panconnected:

• If has a Hamiltonian cycle, then the square of (the graph on the same vertex set that has an edge between every two vertices whose distance in G is at most two) is panconnected.^[1]
• If is any connected graph, then the cube of (the graph on the same vertex set that has an edge between every two vertices whose distance in G is at most three) is panconnected.^[1]
• If every vertex in an -vertex graph has degree at least, then the graph is panconnected.^[2]
• If an -vertex graph has at least edges, then the graph is panconnected.^[2]

Notes and References

1. .
2. .