Barátság grafikon

Barátsággráf (vagy dán mill graph , vagy n -bladed fan ) F n egy síkbeli irányítatlan gráf 2n+1 csúcsgal és 3n éllel [ 1] .

Az F n barátsággráf a C 3 ciklus n példányának egy közös csúcsba történő összekapcsolásával építhető fel [2] .

A konstrukció alapján az F n barátsággráf izomorf a Wd(3, n ) szélmalommal . A grafikon egységnyi távolsággráf , kerülete 3, átmérője 2 és sugara 1. Az F 2 gráf izomorf egy pillangóval .

Barátság gráf tétel

Erdős, Rényi és Vera Sos [3] [4] barátsággráf-tétele kimondja, hogy azok a véges gráfok, amelyeknek a tulajdonsága, hogy bármely két csúcsnak pontosan egy közös szomszédja van, pontosan barátsági gráfok. Informálisan, ha egy embercsoportnak az a tulajdonsága, hogy bármely emberpárnak pontosan egy közös barátja van, akkor egy személynek kell lennie, aki a csoport többi tagjának barátja. A végtelen gráfok esetében azonban sok különböző, azonos számosságú gráf lehet, amelyek rendelkeznek ezzel a tulajdonsággal [5] .

A barátsággráf-tétel kombinatorikus bizonyítását Mertzios és Unger adta [6] . Egy másik bizonyítékot Craig Huneke [7] adott .

Jelölés és színezés

A barátsággráf kromatikus száma 3 és kromatikus indexe 2n . Ennek kromatikus polinomja a C 3 cikluskromatikus polinomból nyerhető, és egyenlő .

Az F n barátsági gráfnak akkor és csak akkor van tökéletes élcímkézése , ha n páratlan. Akkor és csak akkor van kecses címkézése , ha n ≡ 0 (mod 4), vagy n ≡ 1 (mod 4) [8] [9] .

Bármely barátsági grafikon faktorkritikus .

Extrém gráfelmélet

Az extremális gráfelmélet szerint minden (a csúcsok számához képest) kellően nagy élszámú gráfnak részgráfként egy k lapátos legyezőt kell tartalmaznia. Pontosabban ez igaz egy n csúcsú gráfra, ha az élek száma igen

ahol f ( k ) egyenlő k 2  -  k -vel , ha k páratlan, és f ( k ) egyenlő k 2  - 3 k /2-vel, ha k páros. Ezek a korlátok általánosítják a Turan-tételt egy háromszög nélküli gráf éleinek számára vonatkozóan, és ők a legjobb korlátok erre a problémára, mivel bármilyen kisebb számú élre vannak olyan gráfok, amelyek nem tartalmaznak k lapátot [10] .

Jegyzetek

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

Irodalom

• JA Gallian. Dynamic Survey DS6: Graph Labeling  // Electronic J. Combinatorics. - 2007. - január. Az eredetiből archiválva : 2012. január 31.
• 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. Az antennák kombinatorikai problémájáról a rádiócsillagászatban, in Kombinatorika // Colloq. Math. szoc. Bolyai János, / Hajnal A., VT Sos, szerk.. - North-Holland, Amsterdam, 1978. - T. 18, 2 vols..
• Paul Erdős , Alfred Rényi , Vera T. Sos. A gráfelméleti problémáról  // Studia Sci. Math. Magyar.. - 1966. - T. 1 . – S. 215–235 .
• Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. Vannak bíboros barátság grafikonjai  // Canadian Mathematical Bulletin. - 1976. - T. 19 , sz. 4 . – S. 431–433 . - doi : 10.4153/cmb-1976-064-1 .
• George Mertzios, Walter Unger. A barátság probléma grafikonokon  // Relations, Orders and Graphs: Interaction with Computer Science. – 2008.
• Craig Huneke. A barátság tétele // The American Mathematical Monthly. - 2002. - január ( 109. évf. , 2. szám ). – S. 192–194 . - doi : 10.2307/2695332 . — .
• Paul Erdős , Z. Furedi, RJ Gould, DS Gunderson. Extrém gráfok metsző háromszögekhez  // Journal of Combinatorial Theory. - 1995. - T. 64 , sz. 1 . — S. 89–100 . - doi : 10.1006/jctb.1995.1026 .