Article · Wikipedia archive · Last revised Jul 5, 2026

Lollipop graph

In the mathematical discipline of graph theory, the (m,n)-lollipop graph is a special type of graph consisting of a complete graph (clique) on m vertices and a path graph on n vertices, connected with a bridge.

Last revised
Jul 5, 2026
Read time
≈ 1 min
Length
190 w
Citations
4
Source
Wikipedia ↗
Lollipop graph
A (8,4)-lollipop graph
Vertices m + n {\displaystyle m+n}
Edges ( m 2 ) + n {\displaystyle {\tbinom {m}{2}}+n}
Girth { ∞ m ≤ 2 3 otherwise {\displaystyle \left\{{\begin{array}{ll}\infty &m\leq 2\\3&{\text{otherwise}}\end{array}}\right.}
Propertiesconnected
Notation L m , n {\displaystyle L_{m,n}}
Table of graphs and parameters

In the mathematical discipline of graph theory, the (m,n)-lollipop graph is a special type of graph consisting of a complete graph (clique) on m vertices and a path graph on n vertices, connected with a bridge.1

The special case of the (2n/3,n/3)-lollipop graphs are known to be graphs which achieve the maximum possible hitting time,2 cover time3 and commute time.4

See also

See also

References

References

  1. Weisstein, Eric. "Lollipop Graph". Wolfram Mathworld. Wolfram MathWorld. Retrieved 19 August 2015.
  2. Brightwell, Graham; Winkler, Peter (September 1990). "Maximum hitting time for random walks on graphs". Random Structures & Algorithms. 1 (3): 263–276. doi:10.1002/rsa.3240010303.
  3. Feige, Uriel (August 1995). "A tight upper bound on the cover time for random walks on graphs". Random Structures & Algorithms. 6: 51–54. CiteSeerX 10.1.1.38.1188. doi:10.1002/rsa.3240060106.
  4. Jonasson, Johan (March 2000). "Lollipop graphs are extremal for commute times". Random Structures and Algorithms. 16 (2): 131–142. doi:10.1002/(SICI)1098-2418(200003)16:2<131::AID-RSA1>3.0.CO;2-3.