Contents Online

# Journal of Combinatorics

## Volume 8 (2017)

### Number 2

### On the geodetic rank of a graph

Pages: 323 – 340

DOI: http://dx.doi.org/10.4310/JOC.2017.v8.n2.a5

#### Authors

#### Abstract

A graph convexity is a finite graph $G$, together with a family of subsets $\mathcal{C}$ of its vertices, such that $\emptyset , V (G) \in \mathcal{C}$, and $\mathcal{C}$ is closed under intersections. The members of $\mathcal{C}$ are called convex sets. The graph convexity is geodetic when its convex sets are closed under shortest paths. For a subset $S \subseteq V (G) $, the smallest convex set containing $S$, denoted by $H(S)$, is the hull of $S$. On the other hand, $S$ is convexly independent when $v \notin H(S \backslash \{ v \})$, for any $v \in S$. The rank of $G$ is the cardinality of its largest convexly independent set. In this paper, we consider complexity aspects of the determination of the rank in the geodetic convexity. Among the results, we prove that it is NP-hard to approximate the geodetic rank of bipartite graphs by a factor of $n^{1-\varepsilon}$, for every $\varepsilon \gt 0$. On the other hand, we describe polynomial time algorithms for finding the rank of $P_4$-sparse graphs and split graphs. Also, by applying monadic second-order logic we obtain further complexity results, including a linear time algorithm for determining the rank of a distance-hereditary graph. Some of the results obtained are extended to other graph convexities.

#### Keywords

bipartite graphs, geodetic convexity, inapproximability, monophonic convexity, NP-completeness, $P_3$-convexity, $P^*_3$-convexity, rank

#### 2010 Mathematics Subject Classification

Primary 05C85, 68R10. Secondary 68Q25.