Discussiones Mathematicae Graph Theory 27(3) (2007) 611-622
doi: 10.7151/dmgt.1387

[BIBTex] [PDF] [PS]

A SOKOBAN-TYPE GAME AND ARC DELETION WITHIN IRREGULAR DIGRAPHS OF ALL SIZES

Zyta Dziechcińska-Halamoda,  Zofia Majcher, Jerzy Michael

Institute of Mathematics and Informatics
University of Opole
Oleska 48, 45-052 Opole, Poland
e-mail: zdziech@uni.opole.pl
e-mail: majcher@math.uni.opole.pl
e-mail: michael@uni.opole.pl

Zdzisław Skupień

Faculty of Applied Mathematics
AGH University of Science and Technology
al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: skupien@uci.agh.edu.pl

Abstract

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.

Keywords: irregular digraph, all sizes.

2000 Mathematics Subject Classification: 05C20.

References

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

Received 1 March 2006
Revised 7 December 2006
Accepted 10 January 2007