Discrete Mathematics & Theoretical Computer Science, Vol 16, No 2

Font Size:  Small  Medium  Large

Complexity aspects of the computation of the rank of a graph

Igor da Fonseca Ramos, Vinícius F. dos Santos, Jayme L. Szwarcfiter


We consider the $P_3$-convexity on simple undirected graphs, in which a set of vertices $S$ is convex if no vertex outside $S$ has two or more neighbors in $S$. The convex hull $H(S)$ of a set $S$ is the smallest convex set containing $S$ as a subset. A set $S$ is a convexly independent set if $v \not \in H(S\setminus \{v\})$ for all $v$ in $S$. The rank $\rk(G)$ of a graph is the size of the largest convexly independent set. In this paper we consider the complexity of determining $\rk(G)$. We show that the problem is NP-complete even for split or bipartite graphs with small diameter. We also show how to determine $\rk(G)$ in polynomial time for the well structured classes of graphs of trees and threshold graphs. Finally, we give a tight upper bound for $\rk(G)$, which in turn gives a tight upper bound for the Radon number as byproduct, which is the same obtained before by Henning, Rautenbach and Sch\"afer. Additionally, we briefly show that the problem is NP-complete also in the monophonic convexity.

Full Text: PDF PostScript