6533b7d8fe1ef96bd126af2a

RESEARCH PRODUCT

A smallest irregular oriented graph containing a given diregular one

Zdzisław SkupieńJoanna GórskaJerzy MichaelZofia Majcher

subject

Discrete mathematicsAlmost all verticesIrregularizationDigraphDirected graphSuperexponential cardinalityGraphTheoretical Computer ScienceCombinatoricsIndependent setOrdered pairDiscrete Mathematics and CombinatoricsDiregular digraphOriented graphMathematics

description

AbstractA digraph is called irregular if its vertices have mutually distinct ordered pairs of semi-degrees. Let D be any diregular oriented graph (without loops or 2-dicycles). A smallest irregular oriented graph F, F=F(D), is constructed such that F includes D as an induced subdigraph, the smallest digraph being one with smallest possible order and with smallest possible size. If the digraph D is arcless then V(D) is an independent set of F(D) comprising almost all vertices of F(D) as |V(D)|→∞. The number of irregular oriented graphs is proved to be superexponential in their order. We could not show that almost all oriented graphs are/are not irregular.

yearjournalcountryeditionlanguage
2004-09-01Discrete Mathematics
10.1016/j.disc.2003.11.049http://dx.doi.org/10.1016/j.disc.2003.11.049