Edge general position problem

Abstract

Given a graph $G$, the general position problem is to find a largest set $S$ of vertices of $G$ such that no three vertices of $S$ lie on a common geodesic. Such a set is called a $\mathrm{gp}$-$set$ of $G$ and its cardinality is the $\mathrm{gp}$-$number$, $\mathrm{gp}(G)$, of $G$. In this paper, the edge general position problem is introduced as the edge analogue of the general position problem. The edge general position number, $\mathrm{g}{\mathrm{p}}_{\mathrm{e}}(G)$, is the size of a largest edge general position set of $G$. It is proved that $\mathrm{g}{\mathrm{p}}_{\mathrm{e}}(Q_r)=2^r$ and that if $T$ is a tree, then $\mathrm{g}{\mathrm{p}}_{\mathrm{e}}(T)$ is the number of its leaves. The value of $\mathrm{g}{\mathrm{p}}_{\mathrm{e}}(P_r\square P_s)$ is determined for every $r,s\ge 2$. To derive these results, the theory of partial cubes is used. Mulder's meta-conjecture on median graphs is also discussed along the way.