Panconnectivity

Each possible pair of vertices and have paths of length 1 through , where 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 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]

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 ≥ 4 but not panconnected.[3]

References

  1. ^ a b c Alavi, Yousef; Williamson, James E. (1975), "Panconnected graphs", Studia Scientiarum Mathematicarum Hungarica, 10 (1–2): 19–22, MR 0450125.
  2. ^ 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.
  3. ^ 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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.