Panconnectivity

In graph theory, a panconnected graph is an undirected graph in which, for every two vertices $s$ and $t$ , there exist paths from $s$ to $t$ of every possible length from the distance $d (s, t)$ up to $n - 1$ , where $n$ 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 $uv$ 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 $G$ has a Hamiltonian cycle, then the square of $G$ (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 $G$ is any connected graph, then the cube of $G$ (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 $n$ -vertex graph has degree at least $n /2 + 1$ , then the graph is panconnected.^[2]
If an $n$ -vertex graph has at least $(n - 1)(n - 2)/2 + 3$ edges, then the graph is panconnected.^[2]

Related concepts

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

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 $L (n)$ graphs (line graphs of certain inclusion graphs) are Hamilton-connected for $n \geq 4$ but not panconnected.^[3]

References

^ ^a ^b ^c Alavi, Yousef; Williamson, James E. (1975), "Panconnected graphs", Studia Scientiarum Mathematicarum Hungarica, 10 (1–2): 19–22, MR 0450125.
^ ^a ^b Williamson, James E. (1977), "Panconnected graphs. II", Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society, 8 (2): 105–116, doi:10.1007/BF02018497, MR 0463037, S2CID 120309280.
^ ^a ^b Kouhi, Sara; Mirafzal, S. Morteza (2022), "L(n) graphs are vertex-pancyclic and Hamilton-connected", Proceedings of the Indian Academy of Sciences. Mathematical Sciences, 132 (4): 58, doi:10.1007/s12044-022-00703-5

[aw75-1] Alavi, Yousef; Williamson, James E. (1975), "Panconnected graphs", Studia Scientiarum Mathematicarum Hungarica, 10 (1–2): 19–22, MR 0450125.

[w77-2] Williamson, James E. (1977), "Panconnected graphs. II", Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society, 8 (2): 105–116, doi:10.1007/BF02018497, MR 0463037, S2CID 120309280.

[km22-3] Kouhi, Sara; Mirafzal, S. Morteza (2022), "L(n) graphs are vertex-pancyclic and Hamilton-connected", Proceedings of the Indian Academy of Sciences. Mathematical Sciences, 132 (4): 58, doi:10.1007/s12044-022-00703-5

[1]

[2]

[3]