1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Find the largest value of k for which the answer to this graph question is yes.

Discussion in 'Mathematics' started by Ali Khan, Oct 8, 2018.

  1. Ali Khan

    Ali Khan Guest

    Consider the following question: For a given positive integer $k$, does there exist a connected graph $G$ whose complement $\overline G$ is also connected and contains four distinct vertices $u,v,x,y$ for which $d_G(u,v)=k=d_{\overline G}(x,y)$?

    $(a)$ Show that the answer to this question is yes if $k=1$ ou $k=2$.

    $(b)$ Find the largest value of $k$ for which the answer to this question is yes.

    The book answers the alternative $(a)$: Consider the $5$-cycle $(u,v,x,w,y,u)$ for $k=1$ and the $5$-cycle $(u,x,y,v,z,u)$ for $k=2$. For the alternative $(b)$, the book gives the following hint, which I did not understand: Note that $k\geq3$. Consider $P_4=(u,x,y,v)$

    A graph that is a path of order $n$ is denoted by $P_n$

    Login To add answer/comment
     

Share This Page