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

• Autorzy: Zyta Dziechcińska-Halamoda , Zofia Majcher , Jerzy Michael , Zdzisław Skupień
• 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

EN

irregular digraph; all sizes

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 3
• Strony: 611-622

Daty

wydano

2007

otrzymano

2006-03-01

poprawiono

2006-12-07

zaakceptowano

2007-01-10

Twórcy

autor

Zyta Dziechcińska-Halamoda

• Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland

autor

Zofia Majcher

• Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland

autor

Jerzy Michael

• Institute of Mathematics and Informatics, University of Opole, Oleska 48, 45-052 Opole, Poland

autor

Zdzisław Skupień

• 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.

Identyfikatory

DOI

10.7151/dmgt.1387