The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the mobile general position problem , in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.

Let gp t ( G ) , gp o ( G ) , and gp d ( G ) be the total, the outer, and the dual general position number of a graph G , respectively. This paper investigates how removing a vertex or removing an edge affects these graph invariants. It is proved that if x is not a cut vertex, then gp t ( G ) − 1 ≤ gp t ( G − x ) ≤ gp t ( G ) + deg G ( x ) . On the other hand, gp o ( G − x ) and gp d ( G − x ) can be respectively arbitrarily larger/smaller than gp o ( G ) and gp d ( G ) . On the positive side, it is proved that if x lies in some gp o -set, then gp o ( G ) − 1 ≤ gp o ( G − x ) , and that if x is not a cut vertex and lies in some gp d -set of G , then gp d ( G ) − 1 ≤ gp d ( G − x ) . For the edge removal, it is proved that (i) gp t ( G ) − | S ( G ) e | ≤ gp t ( G − e ) ≤ gp t ( G ) + 2 , where S ( G ) e is the set of simplicial vertices adjacent to both endvertices of e , (ii) gp o ( G ) / 2 ≤ gp o ( G − e ) ≤ 2 gp o ( G ) , and (iii) that gp d ( G ) − gp d ( G − e ) can be arbitrarily large. All bounds are demonstrated to be sharp.

The Maker–Breaker domination game (MBD game) is a two-player game played on a graph G by Dominator and Staller. They alternately select unplayed vertices of G . The goal of Dominator is to form a dominating set with the set of vertices selected by him while that of Staller is to prevent this from happening. In this paper MBD game critical graphs are studied. Their existence is established and critical graphs are characterized for most of the cases in which the first player can win the game in one or two moves.

Let G be a graph and X⊆V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutual-visibility number μ(G) of G is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.

The orientable domination number, DOM(G), of a graph G is the largest domination number over all orientations of G. In this paper, DOM is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. (1996) is extended by establishing the values of DOM(Kn1,n2,n3) for arbitrary positive integers n1,n2 and n3. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in Brešar et al. (2022).

Let G be a graph. A dominating set D⊆V(G) is a super dominating set if for every vertex x∈V(G)∖D there exists y∈D such that NG(y)∩(V(G)∖D))={x}. The cardinality of a smallest super dominating set of G is the super domination number of G. An exact formula for the super domination number of a tree T is obtained, and it is demonstrated that a smallest super dominating set of T can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph G is at most a given integer if G is a bipartite graph of girth at least 8. The super domination number is determined for all k-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine.

If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩X⊆{u,v}. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.

A general position set of a graph G is a set of vertices S in G such that no three vertices from S lie on a common shortest path. In this paper we introduce and study the general position achievement game. The game is played on a graph G by players A and B who alternatively pick vertices of G. A selection of a vertex is legal if has not been selected before and the set of vertices selected so far forms a general position set of G. The player who selects the last vertex wins the game. Playable vertices at each step of the game are described, and sufficient conditions for each of the players to win is given. The game is studied on Cartesian and lexicographic products. Among other results it is proved that A wins the game on Kn□Km if and only if both n and m are odd, and that B wins the game on G∘Kn if and only if either B wins on G or n is even.

The general position number gp( G) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G[Formula: see text] of G is the graph formed from the disjoint union of G and its complement [Formula: see text] by adding the edges of a perfect matching between them. It is proved that gp( G[Formula: see text]) ≤ n( G) + 1 if G is connected and gp( G[Formula: see text]) ≤ n( G) if G is disconnected. Graphs G for which gp( G[Formula: see text]) = n( G) + 1 holds, provided that both G and [Formula: see text] are connected, are characterized. A sharp lower bound on gp( G[Formula: see text]) is proved. If G is a connected bipartite graph or a split graph then gp( G[Formula: see text]) ∈ { n( G), n( G)+1}. Connected bipartite graphs and block graphs for which gp( G[Formula: see text]) = n( G) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.

Given a graph G, the (graph theory) general position problem is to find the maximum number of vertices such that no three vertices lie on a common geodesic. This graph invariant is called the general position number (gp-number for short) of G and denoted by gp( G). In this paper, the gp-number is determined for a large class of subgraphs of the infinite grid graph and for the infinite diagonal grid. To derive these results, we introduce monotone-geodesic labeling and prove a Monotone Geodesic Lemma that is in turn developed using the Erdös-Szekeres theorem on monotone sequences. The gp-number of the 3-dim infinite grid is bounded. Using isometric path covers, the gp-number is also determined for Beneš networks.

Average distance is an important parameter for measuring the communication cost of computer networks. A popular approach for its computation is to first partition the edge set of a network into convex components using the transitive closure of the Djoković–Winkler's relation and then to compute the average distance from the respective invariants of the components. In this article, we refine this idea further by shrinking the quotient graphs into smaller weighted graph called reduced graph, so that the average distance of the original graph is obtained from the reduced graphs. We demonstrate the significance of this technique by computing the average distance of butterfly and hypertree architectures. Along the way, a computational error from Klavžar and Nadjafi-Arani ((2014) Wiener index in weighted graphs via unification of Θ*-classes⁠, Eur. J. Combin. 36, 71–76) is corrected.

If |$d(x,y)$| denotes the distance between vertices |$x$| and |$y$| in a graph |$G$|⁠, then an |$L(2,1)$|-labeling of a graph |$G$| is a function |$f$| from vertices of |$G$| to nonnegative integers such that |$\boldsymbol {\vert f(x) - f(y)\vert \ge 2}$| if |$\boldsymbol {d(x,y) = 1}$|⁠, and |$\boldsymbol {\vert f(x) - f(y)\vert \ge 1}$| if |$\boldsymbol {d(x,y) = 2}$|⁠. Griggs and Yeh conjectured that for any graph with maximum degree |$\boldsymbol {\Delta \ge 2}$|⁠, there is an |$\boldsymbol {L(2,1)}$|-labeling with all labels not greater than |$\boldsymbol {\Delta ^2}$|⁠. We prove that the conjecture holds for dot-Cartesian products and dot-lexicographic products of two graphs with possible minor exceptions in some special cases. The bounds obtained are in general much better than the |$\boldsymbol {\Delta ^2}$|-bound.

The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r > 2, there exists a connected graph H, such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G,J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

The domination game played on a graph G consists of two players, Dominator and Staller, who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. Dominator wishes to dominate the graph in as few steps as possible, and Staller wishes to delay the process as much as possible. The game domination number $\gamma_g(G)$ (resp., $\gamma_g'(G)$) is the number of vertices chosen when Dominator (resp., Staller) starts the game. An imagination strategy is developed as a general tool for proving results on the domination game. We show that for any graph G, $\gamma(G)\leq\gamma_g(G)\leq2\gamma(G)-1$, and that all possible values can be realized. It is proved that for any graph G, $\gamma_g(G)-1\leq\gamma'_g(G)\leq\gamma_g(G)+2$, and that most of the possibilities for mutual values of $\gamma_g(G)$ and $\gamma_g'(G)$ can be realized. A connection with Vizing's conjecture is established, and a lower bound on the game domination number of an arbitrary Cartesian product is proved. Several problems and conjectures are also stated.

The power system monitoring problem asks for as few as possible measurement devices to be put in an electric power system. The problem has a graph theory model involving power dominating sets in graphs. The power domination number $\gamma_P(G)$ of G is the minimum cardinality of a power dominating set. Dorfling and Henning [Discrete Appl. Math., 154 (2006), pp. 1023–1027] determined the power domination number of the Cartesian product of paths. In this paper the power domination number is determined for all direct products of paths except for the odd component of the direct product of two odd paths. For instance, if n is even and C a connected component of $P_m\times P_n$, where m is odd or $m\geq n$, then $\gamma_P(C)=\left\lceil n/4 \right\rceil$. For the strong product we prove that $\gamma_P(P_n \boxtimes P_m) = \max\{\lceil n/3\rceil, \lceil (n+m-2)/4\rceil\}$, unless $3m-n-6 \equiv 4\pmod 8$. The power domination number is also determined for an arbitrary lexicographic product.

For a partial cube G its crossing graph $G^#$ is the graph whose vertices are the ϴ‐classes of G, two classes being adjacent if they cross on some cycle in G. The following problem posed in [S. Klavžar and H. M. Mulder, SIAM J. Discrete Math., 15 (2002), pp. 235–251, Problem 7.1] is considered: What can be said about the partial cube G if $G^#$ is the join $A\oplus B$ of graphs A and B with at least one edge? It is proved that for arbitrary graphs A and B, where at least one of them contains an edge, there exists a Cartesian prime partial cube G such that $G^# = A\oplus B$. On the other hand, if G is a median graph, then $G^# = A\oplus B$ if and only if $G=H\,\square\, K$, where $H^# = A$ and $K^# = B$. Along the way some new facts about partial cubes are obtained; for instance, a bipartite graph of radius 2 is a partial cube if and only if it is $K_{2,3}$‐free.

Let G be a connected bipartite graph. An involution $\alpha$ of G that preserves the bipartition of G is called bipartite. Let $G^\alpha$ be the graph obtained from G by adding to G the natural perfect matching induced by $\alpha$. We show that the k-cube Q k is isomorphic to the direct product $G \times H$ if and only if G is isomorphic to $Q_{k-1}^\alpha$ for some bipartite involution $alpha$ of $Q_{k-1}$ and H=K 2 .

Partial cubes are defined as isometric subgraphs of hypercubes. For a partial cube G, its crossing graph G # is introduced as the graph whose vertices are the equivalence classes of the Djoković--Winkler relation $\Theta$, two vertices being adjacent if they cross on a common cycle. It is shown that every graph is the crossing graph of some median graph and that a partial cube G is 2-connected if and only if G # is connected. A partial cube G has a triangle-free crossing graph if and only if G is a cube-free median graph. This result is used to characterize the partial cubes having a tree or a forest as its crossing graph. An expansion theorem is given for the partial cubes with complete crossing graphs. Cartesian products are also considered. In particular, it is proved that G # is a complete bipartite graph if and only if G is the Cartesian product of two trees.

We formalize the problem of analog data compression and analyze the existence of a polynomial data compression function. Under relaxed conditions we explore the existence of a solution employing digital signature analysis in the analog domain.

Let M(m,n) be the complexity of checking whether a graph G with medges and n vertices is a median graph. We show that the complexity of checking whether Gis triangle-free is at most O(M(m,m)). Conversely, we prove that the complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n,n)), where T(m,n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, there are as many median graphs as there are triangle-free graphs. Finally, these results enable us to prove that the complexity of recognizing planar median graphs is linear.