PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 27 | 3 | 611-622
Tytuł artykułu

A Sokoban-type game and arc deletion within irregular digraphs of all sizes

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Digraphs in which ordered pairs of out- and in-degrees of vertices are mutually distinct are called irregular, see Gargano et al. [3]. Our investigations focus on the problem: what are possible sizes of irregular digraphs (oriented graphs) for a given order n? We show that those sizes in both cases make up integer intervals. The extremal sizes (the endpoints of these intervals) are found in [1,5]. In this paper we construct, with help of Sokoban-type game, n-vertex irregular oriented graphs (irregular digraphs) of all intermediate sizes.
Słowa kluczowe
Wydawca
Rocznik
Tom
27
Numer
3
Strony
611-622
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-03-01
poprawiono
2006-12-07
zaakceptowano
2007-01-10
Twórcy
  • Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland
  • Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland
  • Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland
  • Faculty of Applied Mathematics, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland
Bibliografia
  • [1] 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.
  • [2] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael and Z. Skupień, Large minimal irregular digraphs, Opuscula Mathematica 23 (2003) 21-24.
  • [3] M. Gargano, J.W. Kennedy and L.V. Quintas, Irregular digraphs, Congr. Numer. 72 (1990) 223-231.
  • [4] 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.
  • [5] 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1387
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.