On the geodetic rank of a graph

Vinícius F. dos Santos (Departamento de Computação, Centro Federal de Educação Tecnológica de Minas Gerais, Belo Horizonte, Brazil; and Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil)

Jayme L. Szwarcfiter (IM. COPPE, NCE, Universidade Federal do Rio de Janeiro, Brazil; and Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Brazil)

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.

Full Text (PDF format)

Published 14 February 2017