Discussiones Mathematicae Graph Theory 27(3) (2007)
611-622
DOI: https://doi.org/10.7151/dmgt.1387
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 | Zdzisław Skupień
Faculty of Applied Mathematics |
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
Close