5
$\begingroup$

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between vertices $v_i,v_j$.

And the graph has the following property:

  • $(v_1,v_2)\in E$
  • For $i\geq 3$, $(v_i,v_1)\in E\Rightarrow (v_i,v_2)\notin E$,and $(v_i,v_2)\in E\Rightarrow (v_i,v_1)\notin E$
  • For $i\neq j,(v_i,v_j) \notin E \Rightarrow \exists v_{k_1},v_{k_2}(k_1\neq k_2)$ which $(v_{k_1},v_i),(v_{k_2},v_i),(v_{k_1},v_j),(v_{k_2},v_j)\in E$ and $\forall l\neq k_1,k_2, (v_l,v_i) \notin E$ or $(v_l,v_j)\notin E$

If $n$ is even, for instance, $n=12$, we can construct the graph like this: enter image description here

But I couldn't construct one when $n$ is odd, for instance, when $n=5$, etc.

If $n\geq 3$ is an odd number, is it possible to construct a graph meet the above-mentioned property?

$\endgroup$
7
  • $\begingroup$ I guess you mean "or" in the very last condition: $\forall\ l\ne k_1,k_2$ either $(v_l,v_i)\notin E$ or $(v_l,v_j)\notin E$. Or? :D $\endgroup$ Commented Mar 23, 2016 at 6:25
  • 1
    $\begingroup$ Also, are vertices $v$ with neither $(v,v_1)\in E$ nor $(v,v_2)\in E$ allowed? $\endgroup$ Commented Mar 23, 2016 at 6:53
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Yes, it's allowed. $\endgroup$
    – user79942
    Commented Mar 23, 2016 at 7:32
  • 5
    $\begingroup$ Is the following restatement correct? There are two adjacent vertices $v_1,v_2$ with no common neighbor; and any two nonadjacent vertices have exactly two common neighbors. $\endgroup$
    – bof
    Commented Mar 23, 2016 at 9:44
  • 1
    $\begingroup$ @bof Yes, correct. $\endgroup$
    – user79942
    Commented Mar 23, 2016 at 9:56

1 Answer 1

3
$\begingroup$

Notice that for every $n>3$ there should be a $C_4$ with no diagonal. For $n=5$, it is easy to see then that no such graphs exist.

For $n=7$, the Mycielski construction over $C_3$ fits. In other words, mark the vertices of an equilateral triangle with side length 2 and the midpoints of its sides; conect each two vertices at distance 1. Now add one more vertex which is connected to the three vertices of the initial triangle.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.