Žebřík graf - Ladder graph
| Žebřík graf | |
|---|---|
 Žebříkový graf L8. | |
| Vrcholy | 2n |
| Hrany | 3n-2 |
| Chromatické číslo | 2 |
| Chromatický index | 3 pro n> 2 2 pro n = 2 1 pro n = 1 |
| Vlastnosti | Jednotková vzdálenost Hamiltonian Rovinný Bipartitní |
| Zápis | Ln |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, žebříkový graf Ln je rovinný neorientovaný graf s 2n vrcholy a 3n-2 hrany.[1]
Žebříkový graf lze získat jako kartézský součin ze dvou grafy cesty, z nichž jeden má pouze jednu hranu: Ln,1 = Pn × P2.[2][3]
Vlastnosti
Podle konstrukce je žebříkový graf Ln je isomorfní s mřížkový graf G2,n a vypadá jako žebřík s n příčky. to je Hamiltonian s obvodem 4 (pokud n> 1) a chromatický index 3 (pokud n> 2).
The chromatické číslo žebříčkového grafu je 2 a jeho chromatický polynom je .
The chromatické číslo žebříčkového grafu je 2.
Žebřík příčkový graf
Někdy se pro výraz "žebříkový graf" používá výraz n × P2 žebříkový příčkový graf, což je unie grafů n kopie grafu cesty P2.
Kruhový žebříkový graf
The kruhový žebříkový graf CLn je konstruovatelný spojením čtyř 2-stupňových vrcholů v a rovný způsobem, nebo kartézským součinem cyklu délky n≥3 a hrana.[4]V symbolech, CLn = Cn × P2. Má to 2n uzly a 3n hrany. Stejně jako žebříkový graf je připojeno, rovinný a Hamiltonian, ale je bipartitní kdyby a jen kdyby n je sudý.
Kruhový žebříkový graf jsou polyedrické grafy hranolů, takže se běžněji nazývají hranolové grafy.
Kruhové žebříkové grafy:
 CL3 |  CL4 |  CL5 |  CL6 |  CL7 |  CL8 |
Möbiový žebřík
Spojení čtyř 2-stupňových vrcholů křížem vytváří kubický graf zavolal Möbiový žebřík.
Reference
- ^ Weisstein, Eric W. "Žebříkový graf". MathWorld.
- ^ Hosoya, H. a Harary, F. „O shodných vlastnostech tří plotových grafů.“ J. Math. Chem. 12, 211-218, 1993.
- ^ Noy, M. a Ribó, A. „Rekurzivně konstruovatelné rodiny grafů.“ Adv. Appl. Matematika. 32, 350-363, 2004.
- ^ Chen, Yichao; Gross, Jonathan L .; Mansour, Toufik (září 2013). Msgstr "Celkové rozdělení distribuce kruhových žebříků". Journal of Graph Theory. 74 (1): 32–57. CiteSeerX 10.1.1.297.2183. doi:10,1002 / jgt.21690.