Article in press
Authors:
Title:
On a problem of L. Alcón concerning path domination
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-04-03 , Revised: 2023-10-30 , Accepted: 2023-11-04 , Available online: 2023-11-16 , https://doi.org/10.7151/dmgt.2528
Abstract:
A walk $W$ between two non-adjacent vertices in a graph $G$ is
called tolled if the first vertex of $W$ is among vertices from
$W$ adjacent only to the second vertex of $W$, and the last vertex
of $W$ is among vertices from $W$ adjacent only to the second-last
vertex of $W$. In this article, we solve a problem posed by
Alcón that seeks to characterize the class of graphs such that
for every pair of non-adjacent vertices $u$ and $v$, every $uv$
shortest path dominates every $uv$ tolled walk.
Keywords:
domination, walks, interval graphs
References:
- L. Alcón, A note on 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 - A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (Philadelphia, 1999).
https://doi.org/10.1137/1.9780898719796 - 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.B. Tondato, Weakly toll convexity (2022).
arXiv: 2203.17056 - M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Math. 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(1) (2023) 113133.
https://doi.org/10.1016/j.disc.2022.113133 - M. Gutierrez and S.B. Tondato, On walk domination: weakly toll domination, $l_2$ and $l_3$ domination, Discuss. Math. Graph Theory(2022), in press.
https://doi.org/10.7151/dmgt.2475 - C. Lekkerkerker and J. Boland, Representation of 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. Tondato, Walk domination and HHD-free graphs, submitted for publication (2023).
- D.B. West, Introduction to Graph Theory, 2nd. Edition (Prentice-Hall, Upper Saddle River, 2000).
Close