Which are the regular oriented graphs?

185 Views Asked by At

A digraph is regular if all its vertices have the same in-degrees and out-degrees.

An oriented graph $G=(V,E)$ on vertex set $V=\{1,2,\ldots,n\}$ is a digraph such that if $(i,j)\in E$, then $(j,i)\notin E$.

It is also known that

A graph $G$ on $n$ vertices is $r$-regular if and only if $nr$ is even.

  1. Is there any such relationship exist for oriented graphs?
  2. Which oriented graphs are regular?

I expect - $C_n$ and $K_n$ are the only possible types of regular connected oriented graphs, where $C_n$ is the unidirectional cycle on $n$ vertices and $K_n$ is a complete oriented graph.

Below is an example. Note: For $K_n$ to be regular, at least $n$ has to be odd. Fig

Is there any other such class of oriented regular graphs exist?

2

There are 2 best solutions below

0
On

Fi2

Used here two cycle digraphs to produce a new one.

3
On

Consider a graph with vertices $1,\ldots, 6$. Connect the vertices in a cycle $1\rightarrow2\rightarrow\ldots6\rightarrow1$. Also connect the odd vertices cyclically ($1\rightarrow3\rightarrow5\rightarrow1$) and the even vertices cyclically ($2\rightarrow4\rightarrow6\rightarrow2$).

Clearly this isn't $C_6$ or $K_6$, and it isn't made up of two cycles.