Algebraična kombinatorika - 18. maj. 2007

Povzetek predavanja: LASTNOST h-HOMEGENOST

• definicija h-homegenosti in osnovne lastnosti (9 parametrov in 5 relacij),
• 0-homogenost je ekvivalentna razdaljni-regularnosti,
• 1-homogenost:
  • primeri 1-homogenih grafov,
  • lokalno nepovezani 1-homogeni grafi ekvivalentni regularnim skoraj 2d-kotnikom,
  • 1-homogeni grafi so lokalno krepko regularni,
  • lokalen pristop in CAB lastnost,
  • algoritem za klasifikacijo, v primeru, da predpišemo lokalen graf,
  • klasifikacija 1-homogenih grafov, ki so lokalno Moorovi grafi,
  • klasifikacija Terwilligerjevih grafov s c₂.

  in prosojnice:

• ac13_hp

Vse postscript pdf datoteke si lahko ogladate z Adobe Reader, ki so na voljo za večino računalnikov in brskalnikov.

Dodatna gradiva:

• CAB.pdf

Domače naloge (neobvezne):

1. N.L. Biggs, A.G. Boshier in John Shawe-Taylor (slednji je opravil dodiplomski študij v Ljubljani) so leta 1986 klasificirali vse kubične razdaljno-regularne grafe. Le-ti so
   • K₄, tj. tetraeder, {3;1}, v=4,
   • K_3,3, tj. poln dvodelen graf, {3,2;1,3}, v=6,
     (imenujemo ga tudi graf Kuratovskega -- se spomnite naloge o treh sosedih in treh vodnjakih),
   • O₃, tj. Petersenov graf, {3,2;1,1}, v=10,
   • Q₃, kocka, {3,2,1;1,2,3}, v=8,
   • Heawoodov graf, {3,2,2; 1,1,3}, v=14,
   • Pappusov graf, {3,2,2,1;1,1,2,3}, v=18,
   • Coxeterjev graf, {3,2,2,1;1,1,1,2}, v=28,
   • Tutte-ova 8-kletka, {3,2,2,2;1,1,1,3}, v=30,
   • 1-skelet dodekaedra, {3,2,1,1,1; 1,1,1,2,3}, v=20,
   • Desarguesov graf, {3,2,2,1,1;1,1,2,2,3}, v=20,
   • Tutte-ova 12-kletka, {3,2,2,2,2,2;1,1,1,1,1,3}, v=126,
     (gre za GD(1,2), torej posplošeni 10-kotnik, pa mimogrede polovički pri tem grafu nista izomorfni, pa čeprav imata enake parametre) ,
   • Biggs-Smithov graf, {3,2,2,2,1,1,1;1,1,1,1,1,1,3}, v=102,
   • Fosterjev graf, {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}, v=90.
   Vemo, da so kubični grafi 1-homogeni. Nariši razdaljno particijo glede na vozlišči na razdalji 1 in določi vse parametre, ki ustrezajo tej ekvitabilni particiji. (za dodekaeder, Coxeterjev graf in Biggs-Smithov graf smo ustrezne slike pokazali že na predavanjih).

2. Nariši razdaljno particijo še kakšnega 1-homogenega grafa (ki ni kubičen) glede na sosednji vozlišči in določi vse parametre, ki ustrezajo tej ekvitabilni particiji (na predavanjih smo npr. predstavili ustrezno sliko Wellsovega grafa).

3. Dokaži vse štiri zveze, ki jih zadovoljujejo parametri ekvitabilne particije CAB_i (prosojnica 220) (namig: štetje na dva načina).

4. Preuči algoritem za klasifikacijo 1-homogenih grafov, če poznaš lokalen graf (glej prosojnici 221,222 in zgoraj navedeno dodatno gradivo).