On interval number in cycle convexity

Abstract : Many notions in graph convexity have been defined and studied for various applications, such as geode-tic convexity (generalizing the classical convexity in Euclidean space to graphs), monophonic convexity (to model spreading of rumor or disease in a network), etc. Each of the convexity notions led to the study of important graph invariants such as the hull number (minimum number of vertices whose hull set is the entire graph) or the interval number (minimum number of vertices whose interval is the whole graph). Recently, Araujo et al. introduced the notion of Cycle Convexity of graphs for its application in Knot Theory. Roughly, the tunnel number of a knot embedded in a plane is equivalent to the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we study the interval number of a graph in cycle convexity. Precisely, given a graph G, its interval number in cycle convexity, denoted by incc(G), is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S]. In this work, first we provide bounds on incc(G) and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether incc(G) ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[1]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that it cannot be approximated up to a constant factor in the class of split graphs (unless P = N P). On the positive side, we present polynomial-time algorithms to compute incc(G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present FPT algorithms to compute it for (q, q − 4)-graphs, where q is the parameter and for bounded treewidth graphs.
Type de document :
[Research Report] Inria Sophia Antipolis; I3S. 2016

Contributeur : Nicolas Nisse <>
Soumis le : mardi 8 novembre 2016 - 19:32:59
Dernière modification le : jeudi 10 novembre 2016 - 01:05:43


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01394201, version 1



Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan. On interval number in cycle convexity. [Research Report] Inria Sophia Antipolis; I3S. 2016. <hal-01394201>



Consultations de
la notice


Téléchargements du document