2
$\begingroup$

Studying some problem I've arrived to the following notion.

Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a matching in $G.$

Doing some computation, it appears that such graphs are quite rare. There is one such graph on 9 vertices (generalized quadrangle) and two such graphs on 12 vertices. An interesting example of such a graph is Brouwer–Haemers graph of order 81.

I am interested in the following (hopefully not obvious) questions

  1. Is the notion of such graphs already known under some other name?
  2. Is there a nice characterization of such graph? Do they have any interesting properties?
Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

This answer just suggests a couple of directions that you can continue searching, rather than being definitive.

Brouwer, Cohen and Neumaier use the term edge regular for the property that every pair of adjacent vertices have the same number of common neighbours (in other words, like strongly regular but dropping the condition on non-adjacent vertices). So your property is then edge regular with $\lambda = 1$. Of course any graph that is actually strongly regular with $\lambda = 1$ will do the trick, hence the Brouwer-Haemers graph and the Paley graph on 9 vertices that you already found. There are other SRGs with $\lambda=1$. There are various papers on edge-regular graphs of different types, but I don't know offhand if $\lambda=1$ has been tackled.

On another tack, a graph is called locally $X$ if every neighbourhood is isomorphic to $X$, and so you are looking for graphs that are locally $rK_2$. Again there is lots of work on graphs that are locally this, locally that and locally the other, but I don't know offhand for $X =rK_2$.

A third direction in which you may search is to observe that your condition is equivalent to every edge being in a unique triangle (+ regularity). This sounds like a condition that somebody should have studied, but at the risk of sounding like a broken record, I don't know offhand of any such results.

However I think that there is definitely scope there for some interesting work.

Improve this answer
$\endgroup$
3
$\begingroup$

I would not say that these graph are rare. Line graphs of a cubic graph with girth at least four have $2K_2$ neighborhoods.

Next take a semiregular bipartite graph with valencies $r$ and $3$, and with girth at least eight. Then the square of the incidence graph has neighborhoods $rK_2$. (This `explains' the GQ examples - any GQ with lines of size three will work.) Also this construction is equivalent to Flo Pender's comment with a girth restriction added.)

Finally it usually possible to build graphs with given neighbourhoods from smaller ones by constructing covering graphs. While this can work pretty well when you start with a given base graph, I do not see an easy way of getting infinite families.

Improve this answer
$\endgroup$
3
$\begingroup$

Aren't these just $r$-regular $3$-uniform triangle-free linear hypergraphs? Replace every edge in your hypergraph by a triangle (i.e., three $2$-edges), and you arrive at your graph class, and vice versa.

note: added triangle-free after Brendan's comment. Note that the notion of a triangle is properly defined in a linear hypergraph (it's the loose triangle).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think that can create more triangles than the ones that used to be edges. As well as being linear you need no triple of edges that each intersect the others. $\endgroup$
    – Brendan McKay
    Commented Jan 20, 2014 at 6:23
  • $\begingroup$ Correcting my comment, you need to avoid triples of edges, each intersecting the other two, but without a point common to all three. $\endgroup$
    – Brendan McKay
    Commented Jan 20, 2014 at 22:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .