Geodesic
On walk domination: weakly toll domination, $l_2$ and $l_3$ domination
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 837-861 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper we study domination between different types of walks connecting two non-adjacent vertices of a graph. In particular, we center our attention on weakly toll walk and l_k-path for k ∈{2,3}. A walk between two non-adjacent vertices in a graph G is called a weakly toll walk if the first and the last vertices in the walk are adjacent, respectively, only to the second and second-to-last vertices, which may occur more than once in the walk. And an l_k-path is an induced path of length at most k between two non-adjacent vertices in a graph G. We study the domination between weakly toll walks, l_k-paths (k ∈{2,3}) and different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks, weakly toll walks, l_k-paths for k ∈{3,4}), and show how these give rise to characterizations of graph classes.
Keywords: domination, paths, geodesic, chordal graphs, interval graphs 
@article{DMGT_2024_44_3_a1,
     author = {Gutierrez, Marisa and Tondato, Silvia},
     title = {On walk domination: weakly toll domination, $l_2$ and $l_3$ domination},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {837--861},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a1/}
}
TY  - JOUR
AU  - Gutierrez, Marisa
AU  - Tondato, Silvia
TI  - On walk domination: weakly toll domination, $l_2$ and $l_3$ domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 837
EP  - 861
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a1/
LA  - en
ID  - DMGT_2024_44_3_a1
ER  - 
%0 Journal Article
%A Gutierrez, Marisa
%A Tondato, Silvia
%T On walk domination: weakly toll domination, $l_2$ and $l_3$ domination
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 837-861
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a1/
%G en
%F DMGT_2024_44_3_a1
Gutierrez, Marisa; Tondato, Silvia. On walk domination: weakly toll domination, $l_2$ and $l_3$ domination. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 837-861. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a1/

[1] L. Alcón, A note of path domination, Discuss. Math. Graph Theory 36 (2016) 1021–1034. https://doi.org/10.7151/dmgt.1917

[2] L. Alcón, B. Brešar, T. Gologranc, M. Gutierrez, T. Kraner Šumenjak, I. Peterin and A. Tepeh, Toll convexity, European J. Combin. 46 (2015) 161–175. https://doi.org/10.1016/j.ejc.2015.01.002

[3] F.F. Dragan, F. Nicolai and A. Brandstädt, Convexity and HHD-free graphs, SIAM J. Discrete Math. 12 (1999) 119–135. https://doi.org/10.1137/S0895480195321718

[4] M.C. Dourado, M. Gutierrez, F. Protti and S. Tondato, Weakly toll convexity, submitted for publication.

[5] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986) 433–444. https://doi.org/10.1137/0607049

[6] M. Gutierrez, F. Protti and S.B. Tondato, Convex geometries over induced paths with bounded length, Discrete Math. 346 (2023) 113133. https://doi.org/10.1016/j.disc.2022.113133

[7] E. Howorka, A characterization of distance-hereditary graphs, Q. J. Math. 28 (1977) 417–420. https://doi.org/10.1093/qmath/28.4.417

[8] C. Lekkerkerker and J. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45–64. https://doi.org/10.4064/fm-51-1-45-64

[9] S. Olariu, Weak bipolarizable graphs, Discrete Math. 74 (1989) 159–171. https://doi.org/10.1016/0012-365X(89)90208-2

[10] I.M. Pelayo, Geodesic Convexity in Graphs (Springer, New York, 2013). https://doi.org/10.1007/978-1-4614-8699-2

[11] M. Preissmann, D. de Werra and N.V.R. Mahadev, A note on superbrittle graphs, Discrete Math. 61 (1986) 259–267. https://doi.org/10.1016/0012-365X(86)90097-X

[12] D.B. West, Introduction to Graph Theory, 2nd. Edition (Prentice-Hall, Upper Saddle River, 2000).