롤리팝 그래프
Lollipop graph| 롤리팝 그래프 | |
|---|---|
 A(8,4)-롤리팝 그래프 | |
| 정점 | |
| 가장자리 | |
| 둘레 | |
| 특성. | 연결된 |
| 표기법 | |
| 그래프 및 모수 표 | |
그래프 이론의 수학적 분야에서는 (m,n)-롤리팝 그래프는 m 정점에 대한 완전한 그래프(클릭)와 n 정점에 대한 경로 그래프로 구성된 특별한 형태의 그래프로, 브리지와 연결되어 있다.[1]
(2n/3,n/3)-롤리팝 그래프의 특별한 경우는 가능한 최대 적중 시간,[2] 커버 시간[3] 및 통근 시간을 달성하는 그래프로 알려져 있다.[4]
대안 개념
롤리팝 그래프는 특히 스펙트럼 그래프 이론에서 구별 정점으로 펜던트 정점을 가진 경로와 사이클의 결합으로 이해할 수 있다.이 경우, 이 등급의 그래프는 인접 스펙트럼과 라플라시안 스펙트럼에 의해 결정된다고 알려져 있다.[5]
참고 항목
참조
- ^ Weisstein, Eric. "Lollipop Graph". Wolfram Mathworld. Wolfram MathWorld. Retrieved 19 August 2015.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Boulet, Romain; Jouve, Bertrand (2008). "The lollipop graph is determined by its spectrum". The Electronic Journal of Combinatorics. 15. arXiv:0802.1035. doi:10.37236/798.
.svg){kind=small}
