Panconnectivity

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.

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 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 is at most two) is panconnected.
• 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 is at most three) is panconnected.
• If every vertex in an -vertex graph has degree at least , then the graph is panconnected.
• If an -vertex graph has at least edges, then the graph is panconnected.

Related concepts

Vertex-pancyclic graphs: A graph of order is vertex-pancyclic if every vertex lies on cycles of every possible length from the graph's girth up to . While vertex-pancyclic graphs need not be panconnected, they share the property of having rich cycle structures.

Hamilton-connected graphs: These are graphs where every pair of vertices is connected by a Hamiltonian path. All panconnected graphs are Hamilton-connected, but the converse is not true. For example, the graphs (line graphs of certain inclusion graphs) are Hamilton-connected for but not panconnected.

References