Lollipop graph

{{infobox graph

| name = Lollipop graph

| image = 160px

| image_caption = A (8,4)-lollipop graph

| vertices = $m+n$

| edges = $\backslash tbinom\; m2\; +\; n$

| girth =

| notation = $L\_\{m,n\}$

| properties = connected

}}

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.

{{cite web|last1=Weisstein|first1=Eric|title=Lollipop Graph|url=http://mathworld.wolfram.com/LollipopGraph.html|website=Wolfram Mathworld|publisher=Wolfram MathWorld|accessdate=19 August 2015}}

The special case of the (2n/3,n/3)-lollipop graphs are known to be graphs which achieve the maximum possible hitting time,{{cite journal|last1=Brightwell|first1=Graham|authorlink1=Graham Brightwell|last2=Winkler|first2=Peter|authorlink2=Peter Winkler|title=Maximum hitting time for random walks on graphs|journal=Random Structures & Algorithms|date=September 1990|volume=1|issue=3|pages=263–276|doi=10.1002/rsa.3240010303}} cover time{{cite journal|last1=Feige|first1=Uriel|authorlink1=Uriel Feige|title=A tight upper bound on the cover time for random walks on graphs|journal=Random Structures & Algorithms|date=August 1995|volume=6|pages=51–54|doi=10.1002/rsa.3240060106|citeseerx=10.1.1.38.1188}} and commute time.{{cite journal|last1=Jonasson|first1=Johan|title=Lollipop graphs are extremal for commute times|journal=Random Structures and Algorithms|date=March 2000|volume=16|issue=2|pages=131–142|doi=10.1002/(SICI)1098-2418(200003)16:2<131::AID-RSA1>3.0.CO;2-3}}