A smallest irregular oriented graph containing a given diregular one (Q1883255)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A smallest irregular oriented graph containing a given diregular one |
scientific article |
Statements
A smallest irregular oriented graph containing a given diregular one (English)
0 references
1 October 2004
0 references
Let \(D\) be an oriented graph. Then \(D\) is regular if there is a number \(r\) so that \(\text{od}(v)= \text{id}(v)=r\) for each vertex \(v\) of \(D\); and \(D\) is irregular if for any two vertices \(v\neq w\) of \(D\) we have \((\text{od}(v), \text{id}(v))\neq (\text{od}(w),\text{id}(w))\). In the paper, for any oriented regular graph \(D\), a smallest irregular oriented graph \(F\) is constructed such that \(F\) includes \(D\) as induced subgraph. Further, it is shown that the total number of irregular oriented graphs is superexponential in their order.
0 references
oriented graph
0 references
regular digraph
0 references
irregular digraph
0 references
0 references