Marko Petkovšek in Helena Zakrajšek: Seminar za diskretno matematiko 17.11.2009

Iz MaFiRaWiki

Preštevanje I-grafov.

I-graf I(n,j,k) je graf z 2n vozlišči a0,a1,..,an − 1,b0,b1,..,bn − 1 in 3n povezavami ai,bi,ai,ai + j,bi,bi + k za i = 0,1,..,n − 1, kjer seštevamo po modulu n. Znani posebni primeri I-grafov so Petersenov graf I(5,1,2), n-strane prizme I(n,1,1) ter posplošeni Petersenovi grafi I(n,1,k).

Na seminarju januarja letos je T. Pisanski postavil vprašanje eksplicitne formule za število paroma neizomorfnih I-grafov na 2n vozliščih. S pomočjo znane Cauchy-Frobeniusove leme in primerne grupe, ki deluje na množici Z_n \times Z_n, bomo izpeljali iskano formulo. Na podoben način je mogoče dobiti tudi formule za števila paroma neizomorfnih grafov v različnih podrazredih razreda vseh I-grafov, kot so posplošeni Petersenovi grafi ter povezane in/ali dvodelne različice omenjenih grafov.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja