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, Tome 27 (2007), p. 611-622 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270376 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1387,
     author = {Zyta Dziechci\'nska-Halamoda and Zofia Majcher and Jerzy Michael and Zdzis\l aw Skupie\'n},
     title = {A Sokoban-type game and arc deletion within irregular digraphs of all sizes},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {611-622},
     zbl = {1142.05036},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1387}
}

Zyta Dziechcińska-Halamoda; Zofia Majcher; Jerzy Michael; Zdzisław Skupień. A Sokoban-type game and arc deletion within irregular digraphs of all sizes. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 611-622. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1387/

[000] [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. | Zbl 1142.05325

[001] [2] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael and Z. Skupień, Large minimal irregular digraphs, Opuscula Mathematica 23 (2003) 21-24. | Zbl 1093.05505

[002] [3] M. Gargano, J.W. Kennedy and L.V. Quintas, Irregular digraphs, Congr. Numer. 72 (1990) 223-231. | Zbl 0693.05038

[003] [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. | Zbl 1051.05045

[004] [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. | Zbl 0998.05028