Article in press
Authors:
Jing Tian
School of Mathematics, Nanjing University of Aeronautics \& Astronautics, Nanjing, Jiangsu 210016, PR China
email: jingtian526@126.com
Sandi Klavžar
Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
email: sandi.klavzar@fmf.uni-lj.si
Title:
Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-12-14 , Revised: 2023-03-22 , Accepted: 2023-03-24 , Available online: 2023-05-01 , https://doi.org/10.7151/dmgt.2496
Abstract:
If $G$ is a graph and $X\subseteq V(G)$, then $X$ is a total mutual-visibility
set if every pair of vertices $x$ and $y$ of $G$ admits a shortest $x,y$-path
$P$ with $V(P) \cap X \subseteq \{x,y\}$. The cardinality of a largest total
mutual-visibility set of $G$ is the total mutual-visibility number
$\mu_\textrm{t}(G)$ of $G$. Graphs with $\mu_\textrm{t}(G) = 0$ are characterized as
the graphs in which every vertex is the central vertex of a convex $P_3$. The total
mutual-visibility number of Cartesian products is bounded and several exact
results proved. For instance, $\mu_\textrm{t}(K_n \square K_m) = \max\{n,m\}$
and $\mu_\textrm{t}(T \square H) = \mu_\textrm{t}(T)\mu_\textrm{t}(H)$, where $T$ is
a tree and $H$ an arbitrary graph. It is also demonstrated that
$\mu_\textrm{t}(G \square H)$ can be arbitrary larger than
$\mu_\textrm{t}(G)\mu_\textrm{t}(H)$.
Keywords:
mutual-visibility set, total mutual-visibility set, bypass vertex, Cartesian product of graphs, tree
References:
- S. Cicerone, G. Di Stefano and S. Klavžar, On the mutual-visibility in Cartesian products and in triangle-free graphs, Appl. Math. Comput. 438 (2023) 127619.
https://doi.org/10.1016/j.amc.2022.127619 - S. Cicerone, G. Di Stefano, S. Klavžar and I.G. Yero, Mutual-visibility in strong products of graphs via total mutual-visibility (2022).
arXiv: 2210.07835 - G.A. Di Luna, P. Flocchini, S. Gan Chaudhuri, F. Poloni, N. Santoro and G. Viglietta, Mutual visibility by luminous robots without collisions, Inform. and Comput. 254 (2017) 392–418.
https://doi.org/10.1016/j.ic.2016.09.005 - G. Di Stefano, Mutual visibility in graphs, Appl.\ Math. Comput. 419 (2022) 126850.
https://doi.org/10.1016/j.amc.2021.126850 - P. Flocchini, G. Prencipe and N. Santoro, Distributed Computing by Oblivious Mobile Robots (Morgan & Claypool Publishers, 2012).
- M. Ghorbani, H.R. Maimani, M. Momeni, F. Rahimi-Mahid, S. Klavžar and G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
https://doi.org/10.7151/dmgt.2269 - W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory. Graphs and Their Cartesian Products (A K Peters/CRC Press, New York, 2008).
https://doi.org/10.1201/b10613 - S. Klavžar, B. Patkós, G. Rus and I.G. Yero, On general position sets in Cartesian products, Results Math. 76(3) (2021) 123.
https://doi.org/10.1007/s00025-021-01438-x - S. Klavžar and G. Rus, The general position number of integer lattices, Appl. Math. Comput. 390 (2021) 125664.
https://doi.org/10.1016/j.amc.2020.125664 - P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
https://doi.org/10.1017/S0004972718000473 - B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020) 273–280.
https://doi.org/10.26493/1855-3974.1957.a0f - P. Poudel, G. Sharma and A. Aljohani, Sublinear-time mutual visibility for fat oblivious robots, in: Proc. ICDCN'19, ACM (2019) 238–247.
https://doi.org/10.1145/3288599.3288602 - J. Tian and K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021) 126206.
https://doi.org/10.1016/j.amc.2021.126206 - J. Tian, K. Xu and S. Klavžar, The general position number of the Cartesian product of two trees, Bull. Aust. Math. Soc. 104 (2021) 1–10.
https://doi.org/10.1017/S0004972720001276 - U. Chandran S.V. and G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
- D.B. West, Combinatorial Mathematics (Cambridge University Press, Cambridge, 2020).
- Y. Yao, M. He and S. Ji, On the general position number of two classes of graphs, Open Math. 20 (2022) 1021–1029.
https://doi.org/10.1515/math-2022-0444 - K. Zarankiewicz, Problem P $101$, Colloq.\ Math. 2 (1951) 301.
- M. Zhai, L. Fang and J. Shu, On the Turán number of theta graphs, Graphs Combin. 37 (2021) 2155–2165.
https://doi.org/10.1007/s00373-021-02342-5
Close