{{Short description|Graph with all path lengths between each two vertices}} thumb|300px|Each possible pair of vertices <math>s</math> and <math>t</math> have paths of length 1 through <math>n-1</math>, where <math>n</math> is the number of vertices. Thus, the graph shown is panconnected. 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.<ref name="aw75">{{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}}.</ref>
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 {{mvar|G}} is at most two) is panconnected.<ref name="aw75"/> *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 {{mvar|G}} is at most three) is panconnected.<ref name="aw75"/> *If every vertex in an {{mvar|n}}-vertex graph has degree at least {{math|''n''/2 + 1}}, then the graph is panconnected.<ref name="w77">{{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 }}.</ref> *If an {{mvar|n}}-vertex graph has at least {{math|(''n'' − 1)(''n'' − 2)/2 + 3}} edges, then the graph is panconnected.<ref name="w77"/>
==Related concepts==
'''Vertex-pancyclic graphs''': A graph of order {{mvar|n}} is vertex-pancyclic if every vertex lies on cycles of every possible length from the graph's girth up to {{mvar|n}}. While vertex-pancyclic graphs need not be panconnected, they share the property of having rich cycle structures.<ref name="km22">{{citation | last1 = Kouhi | first1 = Sara | last2 = Mirafzal | first2 = S. Morteza | doi = 10.1007/s12044-022-00703-5 | journal = Proceedings of the Indian Academy of Sciences. Mathematical Sciences | pages = 58 | title = L(n) graphs are vertex-pancyclic and Hamilton-connected | volume = 132 | year = 2022 | issue = 4 }}</ref>
'''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 {{math|''L''(''n'')}} graphs (line graphs of certain inclusion graphs) are Hamilton-connected for {{math|''n'' ≥ 4}} but not panconnected.<ref name="km22"/>
==References== {{reflist}}
Category:Graph families