Sousselierův graf - Sousselier graph
| Sousselierův graf | |
|---|---|
 | |
| Vrcholy | 16 |
| Hrany | 27 |
| Poloměr | 2 |
| Průměr | 3 |
| Obvod | 5 |
| Automorfismy | 2 |
| Chromatické číslo | 3 |
| Chromatický index | 5 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Tabulka grafů a parametrů | |
The Sousselierův graf je v teorie grafů, a hypohamiltoniánský graf s 16 vrcholy a 27 hranami. Má to tloušťka knihy 3 a číslo fronty 2.[1]
Dějiny
Hypohamiltonovské grafy byly nejprve studovány Sousselierem v Problèmes plaisants et délectables (1963).[2]
V roce 1967 Lindgren vytvořil nekonečnou sekvenci hypohamiltonovských grafů. Všechny grafy této sekvence mají 6k+10 vrcholů, pro každé celé číslo k.[3]Stejnou sekvenci hypohamiltoniánských grafů vytvořil nezávisle Sousselier.[4] V roce 1973 Chvátal ve vědecké práci vysvětluje, jak lze k některým hypohamiltonovským grafům přidat hrany, aby se vytvořily nové ve stejném pořadí, a jmenuje Bondyho[5]jako původní autor metody. Pro ilustraci ukazuje, že ke druhému grafu Lindgrenovy posloupnosti (kterou pojmenuje Sousselierova posloupnost) lze přidat dva okraje, aby bylo možné vytvořit nový hypohamiltonovský graf na 16 vrcholech. Tento graf se jmenuje Sousselierův graf.
Reference
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Sousselier, R. (1963), Problém č. 29: Le cercle des irascibles, 7, Rev. Franç. Rech. Opérationnelle, str. 405–406
- ^ Lindgren, W. F. (1967), „Nekonečná třída hypohamiltonovských grafů“, Americký matematický měsíčník, 74: 1087–1089, doi:10.2307/2313617, PAN0224501
- ^ Herz, J. C .; Duby, J. J .; Vigué, F. (1967). "Recherche systématique des graphes hypohamiltoniens". Teorie grafů. Dunod. str. 153–159.
- ^ V. Chvátal (1973), „Žabky v hypo-hamiltonovských grafech“, Kanadský matematický bulletin, 16: 33–41, doi:10.4153 / cmb-1973-008-9