Tikkaat (graafiteoria)
| Earl "Ladder" | |
|---|---|
| Huiput | 2n |
| kylkiluut | n+2(n-1) |
| Kromaattinen numero | 2 |
| Kromaattinen indeksi |
3 kun n > 2 2 kun n = 2 1 kun n = 1 |
| Ominaisuudet |
Hamiltonin yksikköetäisyysgraafi tasomainen kaksiosainen |
| Nimitys | L n |
| Mediatiedostot Wikimedia Commonsissa | |
Graafiteoriassa tikapuut L n on tasomainen suuntaamaton graafi , jossa on 2n kärkeä ja n+2(n-1) reunaa [1] .
Tikkaat voidaan saada kahden polun suorana tulona , joista toisella on vain yksi reuna - L n = P n × P 1 [2] [3] . Jos lisäämme vielä kaksi leikkaavaa reunaa, jotka yhdistävät asteisen kaksi tikapuun neljä kärkeä, saadaan kuutiograafi - Möbius-tikkaat .
Tikkaat L n ovat rakenteeltaan isomorfisia hilan G 2, n kanssa ja näyttävät tikkailta, joissa on n puolta. Graafi on Hamiltonin ympärysmitta 4 (jos n>1 ) ja kromaattinen indeksi 3 (jos n>2 ).
Tikkaiden kromaattinen luku on 2 ja sen kromaattinen polynomi on .
Kehätikkaat kaavio
Rengas tikapuugraafi CL n on syklin, jonka pituus on n≥3 , ja reunan suora tulo [4] . Symbolisessa muodossa CL n = C n × P 1 . Graafilla on 2n kärkeä ja 3n reunaa. Kuten tikkaat, graafi on yhdistetty , tasomainen ja Hamiltonin , mutta graafi on kaksiosainen , jos ja vain jos n on parillinen.
Galleria
-
Portaiden kromaattinen numero on 2.
Muistiinpanot
- ↑ Weisstein, Eric W. Ladder Graph Wolfram MathWorld -verkkosivustolla .
- ↑ Hosoya, Harary, 1993 , s. 211-218.
- ↑ Noy, Ribó, 2004 , s. 350-363.
- ↑ Chen, Gross, Mansour, 2013 , s. 32–57.
Kirjallisuus
- H. Hosoya, F. Harary. Kolmen aitakuvaajan yhteensopivuusominaisuuksista // J. Math. Chem.. - 1993. - Numero. 12 . - S. 211-218 .
- M. Noy, A. Ribo. Rekursiivisesti rakennettavat graafiset perheet // Adv. Appl. Matematiikka. - 2004. - Numero. 32 . - S. 350-363 .
- Yichao Chen, Jonathan L. Gross, Toufik Mansour. Pyöreän tikkaiden upotusjakaumat // Journal of Graph Theory. - 2013. - T. 74 , no. 1 . - S. 32-57 . - doi : 10.1002/jgt.21690 .