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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.