Article in volume
Authors:
Title:
On walk domination: weakly toll domination, $l_2$ and $l_3$ domination
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 837-861
Received: 2021-12-16 , Revised: 2022-09-16 , Accepted: 2022-09-18 , Available online: 2022-11-04 , https://doi.org/10.7151/dmgt.2475
Abstract:
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 \in \{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 \in \{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 \in \{3,4\}$), and show how these give
rise to characterizations of graph classes.
Keywords:
domination, paths, geodesic, chordal graphs, interval graphs
References:
- L. Alcón, A note of path domination, Discuss. Math. Graph Theory 36 (2016) 1021–1034.
https://doi.org/10.7151/dmgt.1917 - 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 - 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 - M.C. Dourado, M. Gutierrez, F. Protti and S. Tondato, Weakly toll convexity, submitted for publication.
- 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 - 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 - E. Howorka, A characterization of distance-hereditary graphs, Q. J. Math. 28 (1977) 417–420.
https://doi.org/10.1093/qmath/28.4.417 - 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 - S. Olariu, Weak bipolarizable graphs, Discrete Math. 74 (1989) 159–171.
https://doi.org/10.1016/0012-365X(89)90208-2 - I.M. Pelayo, Geodesic Convexity in Graphs (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-8699-2 - 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 - D.B. West, Introduction to Graph Theory, 2nd. Edition (Prentice-Hall, Upper Saddle River, 2000).
Close