Geodesic
Extremal Irregular Digraphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 791-800.

Voir la notice de l'article provenant de la source Library of Science

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum sizes among irregular n-vertex whether digraphs or oriented graphs are the same and are asymptotic to (√(2) // 3) n^3//2; maximum sizes, however, are asymptotic to n^2 and n^2 // 2, respectively. Let s stand for the sum of initial positive integers,s = 1, 3, 6, .... An oriented graph H_s and a digraph F_s, both large (in terms of the size), minimal irregular, and on any such s vertices, s ≥ 21, are constructed in [Large minimal irregular digraphs, Opuscula Math. 23 (2003) 21–24], co-authored by Z. D-H. and three more of the present co-authors (Z.M., J.M., Z.S.). In the present paper we nearly complete these constructions. Namely, a large minimal irregular digraph F_n, respectively oriented graph H_n, are constructed for any of remaining orders n, n gt; 21, and of size asymptotic to n^2, respectively to n^2 // 2. Also a digraph Φ_n and an oriented graph G_n, both small maximal irregular of any order n ≥ 6, are constructed. The asymptotic value of the size of G_n is at least ( √(2) // 3) n^3//2 and is just the least if n = s →∞, but otherwise the value is at most four times larger and is just the largest if n = s − 1 →∞. On the other hand, the size of Φ_n is of the asymptotic order Θ (n^3//2 ).
Keywords: irregular digraph, oriented graph, minimal subdigraph, maximal subdigraph, asymptotic size 
@article{DMGT_2018_38_3_a9,
     author = {G\'orska, Joanna and Skupie\'n, Zdzis{\l}aw and Dziechci\'nska-Halamoda, Zyta and Majcher, Zofia and Michael, Jerzy},
     title = {Extremal {Irregular} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {791--800},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a9/}
}
TY  - JOUR
AU  - Górska, Joanna
AU  - Skupień, Zdzisław
AU  - Dziechcińska-Halamoda, Zyta
AU  - Majcher, Zofia
AU  - Michael, Jerzy
TI  - Extremal Irregular Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 791
EP  - 800
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a9/
LA  - en
ID  - DMGT_2018_38_3_a9
ER  - 
%0 Journal Article
%A Górska, Joanna
%A Skupień, Zdzisław
%A Dziechcińska-Halamoda, Zyta
%A Majcher, Zofia
%A Michael, Jerzy
%T Extremal Irregular Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 791-800
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a9/
%G en
%F DMGT_2018_38_3_a9
Górska, Joanna; Skupień, Zdzisław; Dziechcińska-Halamoda, Zyta; Majcher, Zofia; Michael, Jerzy. Extremal Irregular Digraphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 791-800. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a9/

[1] G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd Edition (Chapman & Hall, 1996).

[2] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael and Z. Skupień, Large minimal irregular digraphs, Opuscula Math. 23 (2003) 21–24.

[3] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael and Z. Skupień, Extremum degree sets of irregular oriented graphs and pseudodigraphs, Discuss. Math. Graph Theory 26 (2006) 317–333. doi:10.7151/dmgt.1323

[4] M. Gargano, J.W. Kennedy and L.V. Quintas, Irregular digraphs, Congr. Numer. 72 (1990) 223–231.

[5] J. Górska, Z. Skupień, Z. Majcher and J. Michael, A smallest irregular oriented graph containing a given diregular one, Discrete Math. 286 (2004) 79–88. doi:10.1016/j.disc.2003.11.049

[6] Z. Majcher, J. Michael, J. Górska and Z. Skupień, The minimum size of fully irregular oriented graphs, Discrete Math. 236 (2001) 263–272. doi:10.1016/S0012-365X(00)00446-5

[7] Z. Skupień, Problems on fully irregular digraphs, in: Z. Skupień and R. Kalinowski, guest eds., Discuss. Math. Graph Theory 19 (1999) 253–255. doi:10.7151/dmgt.1102