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
The paper investigates mutual-visibility problems on graphs of diameter two, focusing on four visibility parameters: mutual-visibility, outer mutual-visibility, dual mutual-visibility, and total mutual-visibility. These parameters measure the largest set of vertices in a graph such that certain visibility conditions are satisfied. The study includes various graph classes, such as Cartesian and direct products of complete graphs, line graphs of complete and complete bipartite graphs, cographs, and non-trivial diameter-two graphs of minimum size. For the Cartesian product of two complete graphs $ K_n \Box K_m $, the paper derives exact formulas for the dual and outer mutual-visibility numbers, showing that they are $ n + m - 1 $ and $ n + m - 2 $, respectively. It also proves that the total mutual-visibility number is $ \max\{n, m\} $, and that the mutual-visibility number is equivalent to a known Zarankievicz problem. For the direct product of complete graphs $ K_n \times K_m $, the paper shows that all four visibility parameters are equal to $ nm - 4 $ for $ n, m \geq 5 $. The paper also studies line graphs of complete and complete bipartite graphs. It shows that the mutual-visibility number of the line graph of a complete graph $ L(K_n) $ is related to the Turán number $ \mathrm{ex}(n; C_4) $, and that the total mutual-visibility number of $ L(K_n) $ is equal to $ \mathrm{ex}(n; C_4) $. For line graphs of complete bipartite graphs, the paper shows that the mutual-visibility numbers are related to the Zarankievicz problem. The paper also considers cographs, a class of graphs with no induced paths of length 3. It proves that for cographs, either the mutual-visibility number equals the total mutual-visibility number, or the mutual-visibility number is $ n(G) - 1 $ and the total mutual-visibility number is $ n(G) - 2 $. Finally, the paper studies non-trivial diameter-two graphs of minimum size, including the Petersen graph and other graphs constructed by duplicating vertices in a cycle. It computes the four visibility parameters for these graphs and shows that they follow specific patterns based on the number of duplications.The paper investigates mutual-visibility problems on graphs of diameter two, focusing on four visibility parameters: mutual-visibility, outer mutual-visibility, dual mutual-visibility, and total mutual-visibility. These parameters measure the largest set of vertices in a graph such that certain visibility conditions are satisfied. The study includes various graph classes, such as Cartesian and direct products of complete graphs, line graphs of complete and complete bipartite graphs, cographs, and non-trivial diameter-two graphs of minimum size. For the Cartesian product of two complete graphs $ K_n \Box K_m $, the paper derives exact formulas for the dual and outer mutual-visibility numbers, showing that they are $ n + m - 1 $ and $ n + m - 2 $, respectively. It also proves that the total mutual-visibility number is $ \max\{n, m\} $, and that the mutual-visibility number is equivalent to a known Zarankievicz problem. For the direct product of complete graphs $ K_n \times K_m $, the paper shows that all four visibility parameters are equal to $ nm - 4 $ for $ n, m \geq 5 $. The paper also studies line graphs of complete and complete bipartite graphs. It shows that the mutual-visibility number of the line graph of a complete graph $ L(K_n) $ is related to the Turán number $ \mathrm{ex}(n; C_4) $, and that the total mutual-visibility number of $ L(K_n) $ is equal to $ \mathrm{ex}(n; C_4) $. For line graphs of complete bipartite graphs, the paper shows that the mutual-visibility numbers are related to the Zarankievicz problem. The paper also considers cographs, a class of graphs with no induced paths of length 3. It proves that for cographs, either the mutual-visibility number equals the total mutual-visibility number, or the mutual-visibility number is $ n(G) - 1 $ and the total mutual-visibility number is $ n(G) - 2 $. Finally, the paper studies non-trivial diameter-two graphs of minimum size, including the Petersen graph and other graphs constructed by duplicating vertices in a cycle. It computes the four visibility parameters for these graphs and shows that they follow specific patterns based on the number of duplications.
Reach us at info@study.space