\documentstyle[11pt,fullpage]{article} \catcode`\"=13 \def"#1{\v #1}
\setlength{\topmargin}{-1.5cm}            % \topskip=15truept
\setlength{\oddsidemargin}{-0.5cm}        % \hoffset=15truept
\setlength{\evensidemargin}{-0.5cm}
\setlength{\textheight}{24cm}          % \vsize=217truemm
\setlength{\textwidth}{17cm}           % \hsize=148truemm
\hfuzz=10pt
\def\G{\Gamma}
\def\mmod{{\rm mod\ }}
\def\Z{{\rm Z\!\! Z}}

\begin{document} \pagestyle{empty}

\centerline {{\bf Te"caj iz algebrai"cne kombianatorike, 
10. doma"ca naloga}
                  (do petka 4. maja, 2007)}

\vspace{.1in}
\hrule%--------------------------------------------------------------

% \centerline
% {\small\bf Odgovori in re"sitve naj bodo jasne, pregledne in 
           % utemeljene z ra"cunom ali besedo!}
% 20+20+20+20+20+20=120 
\hrule%--------------------------------------------------------------

\vspace{.25in}
\begin{enumerate}
\item Naj bo $\G$ graf s premerom $d$ in 
      o"zino $2d+1$ (tj. dol"zina najkraj"sega cikla). 
      Poka"zi, da je $\G$ regularen graf.

\item Lihi graf  $O(m)$ ima za vozli"s"ca ($m-1$)-elementne 
      podmno"zice iz mno"zice z (2$m-1$)-elementni, dve pa sta sosednji, 
      "ce sta disjunktni.  ("Ce je $\G=J(2m-1,m-1)$, potem je 
      $O(m)$ razdaljni graf $\G_{m-1}$ grafa $\G$.)
      Poka"zi, da so lihi grafi razdaljno-regularni.

\item Dolo"ci o"zino in dol"zino najkraj"sega lihega cikla v 
      lihem grafu $O(m)$, za $m >2$.

\item Poka"zi, da je vsak dvodelen razdaljno-regularen graf premera 3
      inciden"cni graf simetri"cnega 2-designa.

\item Naj bo $\G$ dvodelen razdaljno-regularen graf premera 3, o"zine 6 
      z najmanj"so stopnjo vsaj 3. Poka"zi, da je $\G$ inciden"cen graf 
      projektivne ravnine (projektivna ravnina je simetri"cen design 
      v katerem se vsak par to"ck nahaja v natanko dolo"cenem bloku).

\item "Ce je $\G$ razdaljno-regularen graf, potem poka"zi, da velja
      $$
      A_i A_1 = A_{i-1} b_{i-1} + A_i a_i + A_{i+1} c_{i+1}.
      $$

\item Naj bo $\G$ razdaljno-regularen graf premera $d$. 
      "Ce je parameter $a_1$ od ni"c razli"cen, 
      potem poka"zi, da je parameter $a_i$
      od ni"c razli"cen za vsak $i<d$.

\item Naj bo $\G$ razdaljno-regularen graf premera $d$. 
      "Ce je $p_{st}^h > 0$, poka"zi, da velja
      $$
      p_{ij}^h \le \sum_r \min \{p_{ir}^s,p_{jr}^t\}.
      $$
      %
      \begin{description}
      \item{(a)} Postavi $i=h+1$, $t=h-1$ in $s=j=1$, 
                 ter od tod izpelji, 
                 da je zaporedje $\{b_i\}$ ne nara"s"cujo"ce.
      
      \item{(b)} Postavi $i=h-1$, $t=h+1$ in $s=j=1$, 
                 da poka"ze"s, da je zaporedje $\{c_i\}$ ne padajo"ce.
      
      \item{(c)} Kon"cno vzemi $i=h-1$, $j=1$, $s=h+t$, da poka"ze"s, 
                 da je $c_i\le b_j$, "ce je $i+j \le d$.
\end{description}

\item Naj bo $T$ graf katerega vozli"s"ca so 15 povezav in 15 parjenj
      grafa $K_6$, pri "cemer je povezava sosednja s parjenjem,
      ki jo vsebuje. Ta graf je poznan pod imenom Tuttova 8-kletka. 
      Poka"zi, da ima premer 4 in o"zino 8. Nadalje poka"zi, da je 
      razdaljno-regularen in vsebuje kopijo subdivizijskega grafa 
      Petersenovega grafa.


\item Naj bo $S$ mno"zica sedmih vozli"s"c v lihem grafu 
      $O$(4), ki so paroma na razdalji 3. Poka"zi, da je 
      graf $\G$, ki ga dobimo tako, da izbri"semo vsa vozli"s"ca 
      iz mno"zice, razdaljno-regularen graf premera $d$. 
      Ta graf je poznan pod imenom Coxeterjev graf.
\end{enumerate}
\end{document}
