Andrásfai graf - Andrásfai graph
Andrásfai graf | |
---|---|
![]() | |
Pojmenoval podle | Béla Andrásfai |
Vrcholy | |
Hrany | |
Průměr | 2 |
Zápis | A(n) |
Tabulka grafů a parametrů |

Dva výkresy grafu And (4)
v teorie grafů, an Andrásfai graf je bez trojúhelníků oběhový graf pojmenoval podle Béla Andrásfai.
Vlastnosti
Andrásfaiův graf A (n) pro jakékoli přirozené číslo je cirkulační graf na vrcholy, ve kterých je vrchol je spojen hranou s vrcholy pro každého to odpovídá 1 mod 3. Například Wagnerův graf je Andrásfaiův graf, graf And (3).
Rodina grafů je bez trojúhelníků a And (n) má číslo nezávislosti z . Z toho vzorec výsledky, kde je Ramseyovo číslo. Rovnost platí pro pouze.
Reference
- Godsil, Chris; Royle, Gordon F. (2013) [2001]. „§6.10–6.12: Andrásfaiovy grafy - Andrásfaiovy barevné grafy, charakteristika“. Algebraická teorie grafů. Postgraduální texty z matematiky. 207. Springer. str. 118–123. ISBN 978-1-4613-0163-9.
- Andrásfai, Béla (1971). Ismerkedés a gráfelmélettel (v maďarštině). Budapešť: Tankönyvkiadó. str. 132–5. OCLC 908973331.
- Weisstein, Eric W. "Andrásfai Graph". MathWorld.
Související zboží
![]() | Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |