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

Zyta Dziechcińska-Halamoda; Zofia Majcher; Jerzy Michael; Zdzisław Skupień

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 3, page 611-622
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topZyta Dziechcińska-Halamoda, et al. "A Sokoban-type game and arc deletion within irregular digraphs of all sizes." Discussiones Mathematicae Graph Theory 27.3 (2007): 611-622. <http://eudml.org/doc/270376>.

@article{ZytaDziechcińska2007,

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.},

author = {Zyta Dziechcińska-Halamoda, Zofia Majcher, Jerzy Michael, Zdzisław Skupień},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {irregular digraph; all sizes},

language = {eng},

number = {3},

pages = {611-622},

title = {A Sokoban-type game and arc deletion within irregular digraphs of all sizes},

url = {http://eudml.org/doc/270376},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Zyta Dziechcińska-Halamoda

AU - Zofia Majcher

AU - Jerzy Michael

AU - Zdzisław Skupień

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

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 3

SP - 611

EP - 622

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

LA - eng

KW - irregular digraph; all sizes

UR - http://eudml.org/doc/270376

ER -

## References

top- [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. Zbl1142.05325
- [2] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael and Z. Skupień, Large minimal irregular digraphs, Opuscula Mathematica 23 (2003) 21-24. Zbl1093.05505
- [3] M. Gargano, J.W. Kennedy and L.V. Quintas, Irregular digraphs, Congr. Numer. 72 (1990) 223-231. Zbl0693.05038
- [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. Zbl1051.05045
- [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. Zbl0998.05028

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.