A smallest irregular oriented graph containing a given diregular one

DOI10.1016/J.DISC.2003.11.049MaRDI QIDQ1883255zbMATH OpenOpenAlexFDO

Authors Joanna Górska, Zdzisław Skupień, Zofia Majcher, Jerzy Michael

Publication date 1 October 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.11.049

zbMATH Keywords

irregular digraph oriented graph regular digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A smallest irregular oriented graph containing a given diregular one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883255)