Total Mutual-Visibility in Graphs with Emphasis on Lexicographic and Cartesian Products
Dorota Kuziak, Juan A. Rodríguez‐Velázquez
Abstract
Abstract Given a connected graph G , the total mutual-visibility number of G , denoted $$\mu _t(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , is the cardinality of a largest set $$S\subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> such that for every pair of vertices $$x,y\in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> there is a shortest x , y -path whose interior vertices are not contained in S . Several combinatorial properties, including bounds and closed formulae, for $$\mu _t(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> are given in this article. Specifically, we give several bounds for $$\mu _t(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> in terms of the diameter, order and/or connected domination number of G and show characterizations of the graphs achieving the limit values of some of these bounds. We also consider those vertices of a graph G that either belong to every total mutual-visibility set of G or does not belong to any of such sets, and deduce some consequences of these results. We determine the exact value of the total mutual-visibility number of lexicographic products in terms of the orders of the factors, and the total mutual-visibility number of the first factor in the product. Finally, we give some bounds and closed formulae for the total mutual-visibility number of Cartesian product graphs.