Geodesic
Generalized cages
Marko Boben1 ; Robert Jajcay2 ; Tomaz Pisanski3
1University of Primorska, IAM, Faculty of Computer Science, University of Ljubljana, and Institute of Mathematics, Physics, and Mechanics Ljubljana, Slovenia
2Comenius University Bratislava Slovakia
3University of Primorska, IAM, Faculty of Mathematics and Physics, University of Ljubljana and Institute of Mathematics, Physics, and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $2 \leq k_1 < k_2 < \ldots < k_t $, $3 \leq g_1 < g_2 < \ldots < g_s < N$ be integer parameters. A $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph is a graph that contains vertices of degrees $k_1,k_2,\ldots,k_t$ but no other degrees and cycles of lengths $g_1,g_2,\dots,g_s$ but no other cycles of length $< N$. For any given set of parameters satisfying the above conditions, we present an explicit construction of $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graphs and extend the concept of a cage (a smallest graph of given degree and girth) to that of a generalized cage -- a smallest $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph. We introduce several infinite families of generalized cages and study their basic properties in the context of connected, bipartite, and vertex-transitive graphs, as well as combinatorial configurations (in the context of multilaterals).
DOI : 10.37236/4680
Classification : 05C07, 05C38, 05B30
Mots-clés : cages, vertex degrees, cycles

Marko Boben  1   ; Robert Jajcay  2   ; Tomaz Pisanski  3

1 University of Primorska, IAM, Faculty of Computer Science, University of Ljubljana, and Institute of Mathematics, Physics, and Mechanics Ljubljana, Slovenia
2 Comenius University Bratislava Slovakia
3 University of Primorska, IAM, Faculty of Mathematics and Physics, University of Ljubljana and Institute of Mathematics, Physics, and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia 
@article{10_37236_4680,
     author = {Marko Boben and Robert Jajcay and Tomaz Pisanski},
     title = {Generalized cages},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/4680},
     zbl = {1310.05060},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4680/}
}
TY  - JOUR
AU  - Marko Boben
AU  - Robert Jajcay
AU  - Tomaz Pisanski
TI  - Generalized cages
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4680/
DO  - 10.37236/4680
ID  - 10_37236_4680
ER  - 
%0 Journal Article
%A Marko Boben
%A Robert Jajcay
%A Tomaz Pisanski
%T Generalized cages
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4680/
%R 10.37236/4680
%F 10_37236_4680
Marko Boben; Robert Jajcay; Tomaz Pisanski. Generalized cages. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4680

Cité par Sources :