Kniha (teorie grafů) - Book (graph theory)
v teorie grafů, a knižní graf (často psáno ) může být některý z několika druhů grafů tvořených několika cykly sdílejícími hranu.
Variace
Jeden druh, který lze nazvat a čtyřstranná kniha, skládá se z p čtyřúhelníky sdílení společného okraje (známého jako „páteř“ nebo „základ“ knihy). To znamená, že je kartézský součin a hvězda a jeden okraj.[1][2] Sedmistránkový knižní graf tohoto typu poskytuje příklad grafu bez č harmonické označování.[2]
Druhý typ, který lze nazvat a trojúhelníková kniha, je kompletní trojstranný graf K.1,1,p. Jedná se o graf skládající se z trojúhelníky sdílení společné výhody.[3] Kniha tohoto typu je a dělený graf. Tento graf byl také nazýván a .[4] Trojúhelníkové knihy tvoří jeden z klíčových stavebních kamenů řádkové perfektní grafy.[5]
Termín „knižní graf“ byl použit pro jiná použití. Barioli[6] používal to k označení grafu složeného z řady libovolných podgrafů, které mají společné dva vrcholy. (Barioli nenapsal pro jeho knižní graf.)
Ve větších grafech
Daný graf , jeden může psát pro největší knihu (uvažovaného druhu) obsaženou v .
Věty o knihách
Označte Ramseyovo číslo dvou trojúhelníkových knih od Toto je nejmenší číslo tak, že pro každého -vertexový graf, buď samotný graf obsahuje jako podgraf nebo jeho doplňkový graf obsahuje jako podgraf.
- Li , pak .[7]
- Existuje konstanta takhle kdykoli .
- Li , a je velký, Ramseyovo číslo je dána .
- Nechat být konstantní, a . Pak každý graf zapnutý vrcholy a hrany obsahují (trojúhelníkový) .[8]
Reference
- ^ Weisstein, Eric W. "Book Graph". MathWorld.
- ^ A b Gallian, Joseph A. (1998). „Dynamický průzkum značení grafů“. Electronic Journal of Combinatorics. 5: Dynamický průzkum 6. PAN 1668059.
- ^ Lingsheng Shi; Zhipeng Song (2007). "Horní hranice spektrálního poloměru bez knih a / nebo K.2, l-bezplatné grafy ". Lineární algebra a její aplikace. 420: 526–9. doi:10.1016 / j.laa.2006.08.007.
- ^ Erdős, Paul (1963). "O struktuře lineárních grafů". Israel Journal of Mathematics. 1: 156–160. doi:10.1007 / BF02759702.
- ^ Maffray, Frédéric (1992). "Jádra v dokonalých spojnicových grafech". Journal of Combinatorial Theory. Řada B. 55 (1): 1–8. doi:10.1016 / 0095-8956 (92) 90028-V. PAN 1159851..
- ^ Barioli, Francesco (1998). „Úplně pozitivní matice s knižním grafem“. Lineární algebra a její aplikace. 277: 11–31. doi:10.1016 / S0024-3795 (97) 10070-2.
- ^ Rousseau, C. C.; Sheehan, J. (1978). "Na číslech Ramseyho pro knihy". Journal of Graph Theory. 2 (1): 77–87. doi:10.1002 / jgt.3190020110. PAN 0486186.
- ^ Erdős, P. (1962). „K teorému Rademacher-Turán“. Illinois Journal of Mathematics. 6: 122–7. doi:10.1215 / ijm / 1255631811.