Szczegóły publikacji
Opis bibliograficzny
Extremal irregular digraphs / Joanna GÓRSKA, Zdzisław SKUPIEŃ, Zyta Dziechcińska-Halamoda, Zofia Majcher, Jerzy Michael // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2018 — vol. 38 iss. 3, s. 791–800. — Bibliogr. s. 799–800
Autorzy (5)
- AGHGórska Joanna
- AGHSkupień Zdzisław
- Dziechcińska-Halamoda Zyta
- Majcher Zofia
- Michael Jerzy
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 114278 |
|---|---|
| Data dodania do BaDAP | 2018-06-13 |
| Tekst źródłowy | URL |
| DOI | 10.7151/dmgt.2031 |
| Rok publikacji | 2018 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Discussiones Mathematicae, Graph Theory |
Abstract
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) n3/2; maximum sizes, however, are asymptotic to n2 and n2/2, respectively. Let s stand for the sum of initial positive integers, s = 1, 3, 6, . . . . An oriented graph Hs and a digraph Fs, 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 Fn, respectively oriented graph Hn, are constructed for any of remaining orders n, n > 21, and of size asymptotic to n2, respectively to n2/2. Also a digraph Φn and an oriented graph Gn, both small maximal irregular of any order n ≥ 6, are constructed. The asymptotic value of the size of Gn is at least (2/3) n3/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 Θ(n3/2). © 2018 University of Zielona Gora. All Rights Reserved.
