Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices $$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$ and edges as follows:

  • $(i,j) \in V$ is adjacent (outgoing) to $(k,i)$ for all $k\in\{1,\dots,m\}$ with $k \ne i$ and $k \ne j$.

This already defines the graph. For completeness, incoming edges are

  • $(i,j) \in V$ is adjacent (incoming) to $(j,k)$ for all $k\in\{1,\dots,m\}$ with $k \ne i$ and $k \ne j$.

Use both in case the graph is not directed, and a symmetric definition is needed.

Reformulated: When the vertices are written in a matrix, the main diagonal is empty, and to obtain the outgoing edges of a vertex, "transpose" the element (i.e. switch the entries in $(i,j)$, getting $(j,i)$) and take all elements in the corresponding column except the transposed element (i.e. all elements in the $i$th column except $(j,i)$).

My questions are:

  • Does this graph class have a name and if so, what is it?
  • Are these kind of graphs (directed or undirected) used somewhere and if so, where?

Any other kind of comments of this graph class is also welcome, but at this point this MathOverflow-question is mainly intended for acquiring references. :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.