4
$\begingroup$

If $G$ is a connected finite graph which has no triangles, and $G$ has the property that if two vertices have a common neighbour then they have exactly two common neighbours, does $G$ have to be strongly regular?

Note: I showed it is regular, but how to prove/disprove it's strongly regular?

  • 0
    Now I get a proof. The idea is to show each pair of adjacent vertices has the same degree.(The proof does not need the triangle free condition)2012-05-03
  • 0
    The proof is for regularity, but for strongly regularity I have not found any counterexample so far, does the triangle-free condition play any role in this context?2012-05-03
  • 0
    For the benefit of other users, and to get this question off the unanswered list, you could submit your proof of regularity as an answer. Answering your own questions is encouraged.2012-05-03
  • 0
    I can't answer my own question within 8 hours of asking~I will soon it allows me to do so.2012-05-04
  • 0
    The title doesn't correspond to the question.2012-05-04
  • 0
    Any strongly regular graph with no triangles, is a $srg(n,k,0,\mu)$, and according to http://en.wikipedia.org/wiki/Strongly_regular_graph#Examples there is only 7 examples of such graphs. Since you require $\mu$ to be either 0 or 2, the only two examples left are the Gewirtz Graph, and the Clebsch Graph.2012-07-08

2 Answers 2

1

The answer is "no". A counterexample is provided by the hypercube graph $Q_n$ for any $n\gt2$, in particular by the nearest-neighbour graph of the corners of a cube. The conditions are fulfilled, but some non-adjacent vertices have $2$ common neighbours while others have $0$.

  • 0
    $Q_n$ (for $n > 2$) does not fullfil the requirement that any two vertices with a common neighbor have exactly 2 common neighbors. Look at the drawing of $Q_3$ here: http://en.wikipedia.org/wiki/File:Hypercubeconstruction.png. The vertex in the lower left and the upper right have exactly one common neighbor.2012-07-08
  • 0
    Actually, it seems the drawing on Wikipedia which I referred too is wrong.2012-07-08
  • 0
    @utdiscant: You're right; I fixed the Wikipedia image.2012-07-08
0

Let u, v be two adjacent vertices. let v' be a neighbour of v distinct from u, then u and v' has common neighbour v, by the condition there must exists another vertex u' wihch is adjacent to both u and v'. So repeat this argument to each neighbour of v (distinct from u) to get deg(u) is not less than deg(v). By symmetry of u and v to get the other direction.