Panconnectivity
{{Short description|Graph with all path lengths between each two vertices}}
File:Panconnected graph animation.gif
In graph theory, a panconnected graph is an undirected graph in which, for every two vertices {{mvar|s}} and {{mvar|t}}, there exist paths from {{mvar|s}} to {{mvar|t}} of every possible length from the distance {{math|d(s,t)}} up to {{math|n − 1}}, where {{mvar|n}} is the number of vertices in the graph. The concept of panconnectivity was introduced in 1975 by Yousef Alavi and James E. Williamson.{{citation
| last1 = Alavi | first1 = Yousef
| last2 = Williamson | first2 = James E.
| issue = 1–2
| journal = Studia Scientiarum Mathematicarum Hungarica
| mr = 0450125
| pages = 19–22
| title = Panconnected graphs
| volume = 10
| year = 1975}}.
Panconnected graphs are necessarily pancyclic: if {{math|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 {{mvar|G}} has a Hamiltonian cycle, then the square of {{mvar|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.
- If {{mvar|G}} is any connected graph, then the cube of {{mvar|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.
- If every vertex in an {{mvar|n}}-vertex graph has degree at least {{math|n/2 + 1}}, then the graph is panconnected.{{citation
| last = Williamson | first = James E.
| doi = 10.1007/BF02018497
| issue = 2
| journal = Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society
| mr = 0463037
| pages = 105–116
| title = Panconnected graphs. II
| volume = 8
| year = 1977| s2cid = 120309280
}}.
References
{{reflist}}