J. A. Hernandez edited sectionClique_width_.tex  almost 8 years ago

Commit id: 488569ab8211bc8ec2ee33e7205e6c2546d101ed

deletions | additions      

       

\section{Clique width for paths}  For a graph $P_{2}$, and $P_{3}$ the \emph{cwd }is $2$.  \begin{example}  Now we show the result of compute the \emph{cwd} of a $P_{4}$. Let  $G=(\text{\{}v_{1},v_{2},v_{3},v_{4}\},\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4}\})$.  The resulting $k$-expression is:  \end{example}  $\rho_{c\rightarrow a}(\eta_{c,b}(\rho_{b\rightarrow a}(\eta_{b,c}(\eta_{a,b}(a\oplus b)\oplus c))\oplus b))$,  therefore the $cwd\leq3$.  \begin{prop}  The $cwd(P_{n})\leq3$.  \end{prop}  \begin{proof}  By induction on the structure.  If $P_{1}$ is a path with just one label, the $k$-expression is  $a$ and the $cwd(P_{1})$ is $1$, therefore the proposition holds.  Now we assume for a path $P_{n}$ there is a $k$-expression such  that the $cwd(P_{n})\leq3$. To show for $P_{n+1}$ there is a $k$-expression  such that the $cwd(P_{n+1})\leq3$. By construction we assume that  the label of the last vertex of $P_{n}$ is different from the others  i.e the label $b$, that means that $a$ is the label of the remaining  $n-1$ vertices.  The $3$-expression that constructs a path of length $n+1$ is the  following:  %$\rho_{c\rightarrow b}(\rho_{b\rightarrow a}(\eta_{b,c}((3-$expression$_{P_{n}})\oplus c)))$.  \end{proof} \section{A}