Tečaj iz algebraične kombinatorike, 10. domača naloga

1. Naj bo G graf s premerom d in ožino 2d+1 (tj. dolžina najkrajšega cikla). Pokaži, da je G regularen graf.

2. Lihi graf O(m) ima za vozlišča (m-1)-elementne podmnožice iz množice z (2m-1)-elementni, dve pa sta sosednji, če sta disjunktni. (Če je G=J(2m-1,m-1) potem je O(m) razdaljni graf G_m-1 grafa G.) Pokaži, da so lihi grafi razdaljno-regularni.

3. Določi ožino in dolžino najkrajšega lihega cikla v lihem grafu O(m), za m >2.

4. Pokaži, da je vsak dvodelen razdaljno-regularen graf premera 3 incidenčni graf simetričnega 2-designa.

5. Naj bo G dvodelen razdaljno-regularen graf premera 3, ožine 6 z najmanjšo stopnjo vsaj 3. Pokaži, da je G incidenčen graf projektivne ravnine (projektivna ravnina je simetričen design v katerem se vsak par točk nahaja v natanko določenem bloku).

6. Če je G razdaljno-regularen graf, potem pokaži, da velja
A_i A₁ = A_i-1 b_i-1 + A_i a_i + A_i+1 c_i+1.

7. Naj bo G razdaljno-regularen graf premera d. Če je parameter a₁ od nič različen, potem pokaži, da je parameter a_i od nič različen za vsak i < d.

8. Naj bo G razdaljno-regularen graf premera d. Če je p_st^h > 0, pokaži, da velja
p_ij^h =< sum_r min {p_ir^s, p_jr^t}.

• Postavi i=h+1, t=h-1 in s=j=1, ter od tod izpelji, da je zaporedje {b_i} ne naraščujoče.
• Postavi i=h-1, t=h+1 in s=j=1, da pokažeš, da je zaporedje {c_i} ne padajoče.
• Končno vzemi i=h-1, j=1, s=h+t, da pokažeš, da je c_i =< b_j, če je i+j =< d.

9. Naj bo T graf katerega vozlišča so 15 povezav in 15 parjenj grafa K₆, pri čemer je povezava sosednja s parjenjem, ki jo vsebuje. Ta graf je poznan pod imenom Tuttova 8-kletka. Pokaži, da ima premer 4 in ožino 8. Nadalje pokaži, da je razdaljno-regularen in vsebuje kopijo subdivizijskega grafa Petersenovega grafa.

10. Naj bo S množica sedmih vozlišč v lihem grafu O(4), ki so paroma na razdalji 3. Pokaži, da je graf G, ki ga dobimo tako, da izbrišemo vsa vozlišča iz množice, razdaljno-regularen graf premera d. Ta graf je poznan pod imenom Coxeterjev graf.