Variety of mutual-visibility problems in hypercubes
Danilo Korže, Aleksander Vesel · Applied Mathematics and Computation · 2024
Let G be a graph and M ⊆ V ( G ) . Vertices x , y ∈ M are M -visible if there exists a shortest x , y -path of G that does not pass through any vertex of M ∖ { x , y } . We say that M is a mutual-visibility set if each pair of vertices of M is M -visible, while the size of any largest mutual-visibility set of G is the mutual-visibility number of G . If some additional combinations for pairs of vertices x , y are required to be M -visible, we obtain the total (every x , y ∈ V ( G ) are M -visible), the outer (every x ∈ M and every y ∈ V ( G ) ∖ M are M -visible), and the dual (every x , y ∈ V ( G ) ∖ M are M -visible) mutual-visibility set of G . The cardinalities of the largest of the above defined sets are known as the total, the outer, and the dual mutual-visibility number of G , respectively. We present results on the variety of mutual-visibility problems in hypercubes. • Integer Linear Programming and reduction to SAT models are used to study mutual-visibility and its variations on hypercubes. • The study provides new upper bounds and exact values for the mutual-visibility number and its variations in hypercubes. • Finding a largest total mutual-visibility set in an h -cube equals finding a binary code of length h with minimum distance 4.