Lollipop graph

Lollipop graph
A (8,4)-lollipop graph
Vertices	$m+n$
Edges	${\displaystyle {\tbinom {m}{2}}+n}$
Girth	${\displaystyle \left\{{\begin{array}{ll}\infty &m\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
Properties	connected
Notation	${\displaystyle L_{m,n}}$

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 as graphs which achieve the maximum possible hitting time,^[2] cover time^[3] and commute time.^[4]

See also

• Barbell graph
• Tadpole graph

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. 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.