Graf simplex

Un graf G și graful său simplex corespondent κ(G). Nodul albastru din κ(G) corespunde clicii 0-nodurilor din G (o mulțime vidă), iar nodul violet corespunde clicii de 3-noduri.

În teoria grafurilor graful simplex κ(G) al unui graf neorientat G este el însuși un graf, cu câte un nod pentru fiecare clică din G. Două noduri ale lui κ(G) sunt legate printr-o muchie ori de câte ori cele două clici corespunzătoare diferă prin prezența sau absența unui singur nod.

Mulțimea vidă este inclusă ca una dintre clicile din G folosite pentru a forma graful clicii, la fel ca fiecare mulțime a nodurilor cu un vârf sau cu două vârfuri adiacente. Prin urmare, graful simplex conține în el o subdiviziune a lui G însuși. Graful simplex al unui graf complet este un graf hipercubic. Graful simplex al grafului complementar al unui drum este un cub Fibonacci.

Grafurile simplex au fost introduse de Bandelt și van de Vel în 1989,[1] care au observat că un graf simplex nu are cuburi dacă și numai dacă graful suport este liber de triunghiuri^⁠(d) și a arătat că numărul cromatic al grafului suport este egal cu numărul minim n, astfel încât graful simplex poate fi încorporat izometric într-un produs cartezian al n arbori. Ca o consecință a existenței grafurilor libere de triunghiuri cu număr cromatic mare, ei au arătat că există algebre mediane topologice bidimensionale care nu pot fi încorporate în produsele a mai multor arbori reali. Imrich, Klavžar și Mulder utilizează grafuri simplex ca parte a demonstrației că testarea dacă un graf este liber de triunghiuri sau dacă este un graf median este la fel de rapidă.

Note

1. Imrich, Klavžar și Mulder atribuie introducerea grafurilor simplex într-o lucrare ulterioară, tot de Bandelt și van de Vel, dar aceasta pare a fi o greșeală.

Bibliografie

• en Bandelt, H.-J.; Chepoi, V. (2008), „Metric graph theory and geometry: a survey”, În Goodman, Jacob E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math., 453, Providence, RI: AMS, pp. 49–86 
• en Bandelt, H.-J.; van de Vel, M. (1989), „Embedding topological median algebras in products of dendrons”, Proceedings of the London Mathematical Society, s3-58 (3): 439–453, doi:10.1112/plms/s3-58.3.439, arhivat din original la 15 aprilie 2013 
• en Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), „On the use of ordered sets in problems of comparison and consensus of classifications”, Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188 
• en Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), „Median graphs and triangle-free graphs”, SIAM Journal on Discrete Mathematics, 12 (1): 111–118, CiteSeerX 10.1.1.28.5906 , doi:10.1137/S0895480197323494, MR 1666073 
• en Propp, James (1997), „Generating random elements of finite distributive lattices”, Electronic Journal of Combinatorics, 4 (2): R15, arXiv:math.CO/9801066