Szczegóły publikacji
Opis bibliograficzny
A smallest irregular oriented graph containing a given diregular one / Joanna GÓRSKA, Zdzisław SKUPIEŃ, Zofia Majcher, Jerzy Michael // Discrete Mathematics ; ISSN 0012-365X. — 2004 — vol. 286 iss. 1–2, s. 79–88. — Bibliogr. s. 87–88, Abstr. — Publikacja dostępna online od: 2004-07-08. — Workshop on Cycles and Colourings : Stara Lesna, Slovakia, September 09-14, 2001
Autorzy (4)
- AGHGórska Joanna
- AGHSkupień Zdzisław
- Majcher Zofia
- Michael Jerzy
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 19189 |
|---|---|
| Data dodania do BaDAP | 2005-01-25 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2003.11.049 |
| Rok publikacji | 2004 |
| Typ publikacji | referat w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Discrete Mathematics |
Abstract
A 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)\ –> infinity. 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. (C) 2004 Elsevier B.V. All rights reserved.
