Geodesic
Dominating sequences in grid-like and toroidal graphs
Boštjan Brešar1 ; Csilla Bujtás2 ; Tanja Gologranc3 ; Sandi Klavžar4 ; Gašper Košmrlj5 ; Balázs Patkós6 ; Zsolt Tuza2 ; Máté Vizer6
1Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics
2Department of Computer Science and Systems Technology and Alfréd Rényi Institute of Mathematics
3Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics
4Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics and Faculty of Mathematics and Physics
5Institute of Mathematics, Physics and Mechanics
6Alfréd Rényi Institute of Mathematics
The electronic journal of combinatorics, Tome 23 (2016) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$. In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.
DOI : 10.37236/6269
Classification : 05C76, 05C69
Mots-clés : Grundy domination, graph product, edge clique cover, isoperimetric inequality

Boštjan Brešar  1   ; Csilla Bujtás  2   ; Tanja Gologranc  3   ; Sandi Klavžar  4   ; Gašper Košmrlj  5   ; Balázs Patkós  6   ; Zsolt Tuza  2   ; Máté Vizer  6

1 Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics
2 Department of Computer Science and Systems Technology and Alfréd Rényi Institute of Mathematics
3 Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics
4 Faculty of Natural Sciences and Mathematics and Institute of Mathematics, Physics and Mechanics and Faculty of Mathematics and Physics
5 Institute of Mathematics, Physics and Mechanics
6 Alfréd Rényi Institute of Mathematics 
@article{10_37236_6269,
     author = {Bo\v{s}tjan Bre\v{s}ar and Csilla Bujt\'as and Tanja Gologranc and Sandi Klav\v{z}ar and Ga\v{s}per Ko\v{s}mrlj and Bal\'azs Patk\'os and Zsolt Tuza and M\'at\'e Vizer},
     title = {Dominating sequences in grid-like and toroidal graphs},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {4},
     doi = {10.37236/6269},
     zbl = {1353.05105},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6269/}
}
TY  - JOUR
AU  - Boštjan Brešar
AU  - Csilla Bujtás
AU  - Tanja Gologranc
AU  - Sandi Klavžar
AU  - Gašper Košmrlj
AU  - Balázs Patkós
AU  - Zsolt Tuza
AU  - Máté Vizer
TI  - Dominating sequences in grid-like and toroidal graphs
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6269/
DO  - 10.37236/6269
ID  - 10_37236_6269
ER  - 
%0 Journal Article
%A Boštjan Brešar
%A Csilla Bujtás
%A Tanja Gologranc
%A Sandi Klavžar
%A Gašper Košmrlj
%A Balázs Patkós
%A Zsolt Tuza
%A Máté Vizer
%T Dominating sequences in grid-like and toroidal graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6269/
%R 10.37236/6269
%F 10_37236_6269
Boštjan Brešar; Csilla Bujtás; Tanja Gologranc; Sandi Klavžar; Gašper Košmrlj; Balázs Patkós; Zsolt Tuza; Máté Vizer. Dominating sequences in grid-like and toroidal graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/6269

Cité par Sources :