K-fa

A k -fa egy irányítatlan gráf , amelyet egy teljes gráfból alakítanak ki ( k  + 1) csúcsokkal, csúcsok egymás utáni összeadásával úgy, hogy minden hozzáadott v csúcsnak pontosan k szomszédja van U , így k  + 1 csúcs ( v + U csúcsok ) klikket alkotnak [1] [2] .

Leírások

k -Fák pontosan a maximális gráfok adott faszélességgel , vagyis olyan gráfok, amelyekhez nem adható él a gráf faszélességének növelése nélkül [2] . Ezek is pontosan akkordgráfok , amelyeknek mindegyik maximális klikkje azonos méretű , és mindegyik minimális klikkelválasztója is azonos méretű k [1] .

Grafikonok összekapcsolt osztályai

1-A fák ugyanazok, mint a gyökerezetlen fák . A 2-fák maximális párhuzamos-szekvenciális gráfok [3] , és tartalmaznak maximális külső síkbeli gráfokat is . A sík 3-fákat Apollonius-hálózatoknak is nevezik [4] .

A legfeljebb k faszélességű gráfok pontosan k -fák részgráfjai , ezért ezeket részleges k -fáknak nevezzük [2] .

A k -dimenziós blokkpoliéderek éleiből és csúcsaiból alkotott gráfok , vagyis az egyszerűségek lapjainak egymás utáni ragasztásával szimplexből kiinduló poliéderek , k -fák, ha [5] . Ez a ragasztási folyamat a k -fák felépítését utánozza azáltal, hogy csúcsokat ad egy klikkhez [6] . A k -fa akkor és csak akkor blokkpoliéder gráf, ha nincs három ( k  + 1) csúcsú klikknek k közös csúcsa [7] .

Jegyzetek

1. ↑ 12. Patil , 1986 , p. 57–64.
2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , p. 390.
3. ↑ Hwang, Richards, Winter, 1992 .
4. ↑ Távolságok véletlenszerű apollóni hálózati struktúrákban Archiválva 2011. július 21-én a Wayback Machine -nél , Olivier Bodini, Alexis Darrasse, Michèle Soria beszéddiái a 2008-as FPSAC-on elhangzott előadásból, elérve: 2011-03-06
5. ↑ Koch és Perles, 1976 , p. 420.
6. ↑ Lent, De Loera, Richter-Gebert .
7. ↑ Kleinschmidt, 1976 , p. 663–667.

Irodalom

• Patil HP A k -trees szerkezetéről // Journal of Combinatorics, Information and System Sciences. - 1986. - T. 11 , sz. 2-4 . – 57–64 .
• Frank Hwang, Dana Richards, Pawel Winter. A Steiner-fa probléma. - Elsevier, 1992. - V. 53. - P. 177. - (Annals of Discrete Mathematics (North-Holland Mathematics Studies)). - ISBN 978-0-444-89098-6 .
• Jaroslav Nešetřil, Patrice Ossona de Mendez. A ritka gráfok szerkezeti tulajdonságai // Hidak építése: matematika és számítástechnika között / Martin Grötschel, Katona Gyula OH. - Springer-Verlag, 2008. - V. 19. - P. 390. - (Bolyai Társaság Matematikai Tanulmányai). — ISBN 978-3-540-85218-6 .
• Etan Koch, Micha A. Perles. A fák és a k -fák hatékonyságának lefedése // Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1976). - Utilitas Math., Winnipeg, Man., 1976. - P. 391-420. Congressus Numerantium, sz. A XVII.
• Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. Konvex 3-politópok kis háromszögleteinek megtalálásának bonyolultsága.
• Kleinschmidt Péter. Eine graphentheoretische Kennzeichnung der Stapelpolytope // Archiv der Mathematik. - 1976. - December ( 27. évf. , 1. szám ). – S. 663–667 . - doi : 10.1007/BF01224736 .