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.^[1]

Vertices${\displaystyle m+n}$

Edges${\displaystyle {\tbinom {m}{2}}+n}$

Girth${\displaystyle \left\{{\begin{array}{ll}\infty &m\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$

Propertiesconnected

Quick facts Vertices, Edges ...

Lollipop graph
A (8,4)-lollipop graph
Vertices	${\displaystyle 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}}$
Table of graphs and parameters

Close

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 time^[3] and commute time.^[4]