Ystävyyskaavio

Ystävyysgraafi (tai tanskalainen mill graph , tai n -lapainen tuuletin ) F n on tasomainen suuntaamaton graafi , jossa on 2n+1 kärkeä ja 3n reunaa [1] .

Ystävyysgraafi F n voidaan rakentaa yhdistämällä n kopiota syklistä C 3 yhteen yhteiseen kärkeen [2] .

Ystävyysgraafi F n on rakenteeltaan isomorfinen tuulimyllylle Wd(3, n ). Kaavio on yksikköetäisyyskäyrä ja sen ympärysmitta 3, halkaisija 2 ja säde 1. Kuvaaja F 2 on isomorfinen perhosen kanssa .

Ystävyysgraafi lause

Erdősin, Rényin ja Vera Sosin [3] [4] ystävyysgraafiteoreema sanoo, että äärelliset graafit, joiden ominaisuus on, että millä tahansa kahdella kärjellä on täsmälleen yksi yhteinen naapuri, ovat täsmälleen ystävyysgraafia. Epävirallisesti, jos ihmisryhmällä on ominaisuus, että millä tahansa ihmisparilla on täsmälleen yksi yhteinen ystävä, silloin on oltava yksi henkilö, joka on ryhmän muiden jäsenten ystävä. Äärettömille graafisille voi kuitenkin olla useita saman kardinaalisuuden omaavia kuvaajia, joilla on tämä ominaisuus [5] .

Mertzios ja Unger [6] antoivat kombinatorisen todisteen ystävyysgraafilauseesta . Toisen todisteen antoi Craig Huneke [7] .

Merkinnät ja väritys

Ystävyysgraafin kromaattinen luku on 3 ja kromaattinen indeksi 2n . Sen kromaattinen polynomi voidaan saada syklin kromaattisesta polynomista C 3 ja se on yhtä suuri kuin .

Ystävyysgraafissa F n on täydellinen reunamerkintä silloin ja vain, jos n on pariton. Siinä on siro merkintä silloin ja vain jos n ≡ 0 (mod 4) tai n ≡ 1 (mod 4) [8] [9] .

Mikä tahansa ystävyyskaavio on tekijäkriittinen .

Extremal graph theory

Ekstremaalisen graafiteorian mukaan minkä tahansa graafin, jossa on riittävän suuri määrä reunoja (suhteessa pisteiden määrään), tulee sisältää k -lapaviuhka aligraafina. Tarkemmin sanottuna tämä pätee graafille, jossa on n kärkeä, jos reunojen lukumäärä on

missä f ( k ) on k 2  −  k , jos k on pariton ja f ( k ) on k 2  − 3 k /2, jos k on parillinen. Nämä rajat yleistävät Turanin lauseen kolmiovapaan graafin reunojen lukumäärästä , ja ne ovat parhaat rajat tälle ongelmalle, koska pienemmälle määrälle reunoja on graafit, jotka eivät sisällä k -lapaa [10] .

Muistiinpanot

1. ↑ Weisstein, Eric W. Dutch Windmill Graph  Wolfram MathWorld -verkkosivustolla .
2. ↑ Gallian, 2007 , s. 1-58.
3. ↑ Erdős, Rényi, Sos, 1966 .
4. ↑ Erdős, Rényi, Sós, 1966 , s. 215–235.
5. ↑ Chvátal, Kotzig, Rosenberg, Davies, 1976 , s. 431–433.
6. ↑ Mertzios, Unger, 2008 .
7. ↑ Huneke, 2002 , s. 192-194.
8. ↑ Bermond, Brouwer, Germa, 1978 , s. 35-38.
9. ↑ Bermond, Kotzig, Turgeon, 1978 , s. 135-149.
10. ↑ Erdős, Furedi, Gould, Gunderson, 1995 , s. 89-100.

Kirjallisuus

• JA Gallian. Dynamic Survey DS6: Graph Labeling  // Electronic J. Combinatorics. - 2007. - tammikuuta. Arkistoitu alkuperäisestä 31. tammikuuta 2012.
• J.C. Bermond, A.E. Brouwer, A. Germa. Systèmes de triplets et différences associées // Problèmes Combinatoires et Théorie des Graphes. - Paris, 1978. - Vol. 260, Editions du Centre Nationale de la Recherche Scientifique. - (Colloq. Intern. du CNRS).
• JC Bermond, A. Kotzig, J. Turgeon. Antennien kombinatorisesta ongelmasta radioastronomiassa, julkaisussa Kombinatoriikka // Colloq. Matematiikka. soc. János Bolyai, / A. Hajnal, VT Sos, toim. - North-Holland, Amsterdam, 1978. - T. 18, 2 osaa.
• Paul Erdős , Alfred Rényi , Vera T. Sos. Graafiteorian ongelmasta  // Studia Sci. Matematiikka. Unkari.. - 1966. - T. 1 . — S. 215–235 .
• Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. On olemassa kardinaalin ystävyyskaavioita  // Canadian Mathematical Bulletin. - 1976. - T. 19 , no. 4 . — S. 431–433 . - doi : 10.4153/cmb-1976-064-1 .
• George Mertzios, Walter Unger. Ystävyysongelma kaavioissa  // Suhteet, tilaukset ja kaaviot: vuorovaikutus tietojenkäsittelytieteen kanssa. – 2008.
• Craig Huneke. Ystävyyslause // The American Mathematical Monthly. - 2002. - tammikuu ( osa 109 , numero 2 ) . — S. 192–194 . - doi : 10.2307/2695332 . — .
• Paul Erdős , Z. Furedi, RJ Gould, DS Gunderson. Äärimmäiset kaaviot leikkaaville kolmiolle  // Journal of Combinatorial Theory. - 1995. - T. 64 , no. 1 . — S. 89–100 . - doi : 10.1006/jctb.1995.1026 .