Mutual-visibility problems on graphs of diameter two

Mutual-visibility problems on graphs of diameter two

January 5, 2024 | Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero
This paper investigates the mutual-visibility problem in graphs of diameter two, focusing on four visibility parameters: mutual-visibility set ($\mu$), outer mutual-visibility set ($\mu_o$), dual mutual-visibility set ($\mu_d$), and total mutual-visibility set ($\mu_t$). The authors study these parameters for graphs that are Cartesian products of complete graphs, direct products of complete graphs, line graphs of complete and complete bipartite graphs, cographs, and non-trivial diameter-two graphs of minimum size. They provide bounds and closed formulas for these parameters, answering open questions and establishing relationships between the visibility problems and classical Turán problems. Key results include: 1. **Cartesian Products of Complete Graphs**: The authors derive formulas for the dual and outer mutual-visibility numbers of the Cartesian product of two complete graphs, showing that the direct product has the same formula for all four parameters. They also show that the mutual-visibility number of the Cartesian product is greater than the outer mutual-visibility number. 2. **Direct Products of Complete Graphs**: They prove that the total mutual-visibility number of the direct product of two complete graphs is equal to the product of their sizes minus four. 3. **Line Graphs of Complete and Complete Bipartite Graphs**: The authors establish connections between the mutual-visibility problems and the Turán problem, showing that the mutual-visibility number of the line graph of a complete graph is related to the Turán graph $T(n, 3)$, and the total mutual-visibility number is related to the Turán graph $\operatorname{ex}(n; C_{4})$. 4. **Cographs**: They prove that if $G$ is a cograph, then either $\mu(G) = \mu_t(G) = \mu_o(G) = \mu_a(G)$, or $\mu(G) = \mu_d(G) = n(G) - 1$ and $\mu_t(G) = \mu_o(G) = n(G) - 2$. 5. **Non-Trivial Diameter-Two Graphs of Minimum Size**: The authors compute the values of the mutual-visibility parameters for graphs that achieve the minimum size bound for diameter-two graphs with no universal vertex, characterized by the family $\mathcal{G}$. The paper contributes to the understanding of mutual-visibility problems in various graph structures and provides insights into the relationships between these parameters and other graph theory concepts.This paper investigates the mutual-visibility problem in graphs of diameter two, focusing on four visibility parameters: mutual-visibility set ($\mu$), outer mutual-visibility set ($\mu_o$), dual mutual-visibility set ($\mu_d$), and total mutual-visibility set ($\mu_t$). The authors study these parameters for graphs that are Cartesian products of complete graphs, direct products of complete graphs, line graphs of complete and complete bipartite graphs, cographs, and non-trivial diameter-two graphs of minimum size. They provide bounds and closed formulas for these parameters, answering open questions and establishing relationships between the visibility problems and classical Turán problems. Key results include: 1. **Cartesian Products of Complete Graphs**: The authors derive formulas for the dual and outer mutual-visibility numbers of the Cartesian product of two complete graphs, showing that the direct product has the same formula for all four parameters. They also show that the mutual-visibility number of the Cartesian product is greater than the outer mutual-visibility number. 2. **Direct Products of Complete Graphs**: They prove that the total mutual-visibility number of the direct product of two complete graphs is equal to the product of their sizes minus four. 3. **Line Graphs of Complete and Complete Bipartite Graphs**: The authors establish connections between the mutual-visibility problems and the Turán problem, showing that the mutual-visibility number of the line graph of a complete graph is related to the Turán graph $T(n, 3)$, and the total mutual-visibility number is related to the Turán graph $\operatorname{ex}(n; C_{4})$. 4. **Cographs**: They prove that if $G$ is a cograph, then either $\mu(G) = \mu_t(G) = \mu_o(G) = \mu_a(G)$, or $\mu(G) = \mu_d(G) = n(G) - 1$ and $\mu_t(G) = \mu_o(G) = n(G) - 2$. 5. **Non-Trivial Diameter-Two Graphs of Minimum Size**: The authors compute the values of the mutual-visibility parameters for graphs that achieve the minimum size bound for diameter-two graphs with no universal vertex, characterized by the family $\mathcal{G}$. The paper contributes to the understanding of mutual-visibility problems in various graph structures and provides insights into the relationships between these parameters and other graph theory concepts.
Reach us at info@study.space