Lesson plan
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.