ロリポップグラフ

グラフ理論の数学分野では、( m , n )-ロリポップグラフは、m個の頂点を持つ完全グラフ（クリーク）とn個の頂点を持つパスグラフがブリッジで接続された特殊なタイプのグラフである。^[¹^]

(2 n /3, n /3)-ロリポップグラフの特殊なケースは、可能な限り最大のヒット時間^{[ 2 ]} 、カバー時間^{[ 3 ]}、および通勤時間^[⁴^]を達成するグラフとして知られています。

参考文献

↑ Weisstein, Eric. "Lollipop Graph" . Wolfram Mathworld . Wolfram MathWorld . 2015年8月19日取得.
↑ Brightwell, Graham ; Winkler, Peter (1990 年 9 月) 「グラフ上のランダムウォークの最大到達時間」Random Structures & Algorithms . 1 (3): 263– 276. doi : 10.1002/rsa.3240010303 .
↑ Feige, Uriel (1995 年 8 月) 「グラフ上のランダムウォークのカバー時間の厳密な上限」Random Structures & Algorithms . 6 : 51– 54. CiteSeerX 10.1.1.38.1188 . doi : 10.1002/rsa.3240060106 .
↑ Jonasson, Johan (2000年3月). "ロリポップグラフは通勤時間に関して極値である". 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 .