Kanté and Nourine [ SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm for the computation of the hull number of chordal graphs. We point out a gap in the correctness proof of their algorithm for chordal graphs and show that computing the hull number of a chordal graph is NP-hard, which most likely rules out the existence of a polynomial time algorithm.

We study perfect matchings in graphs that have the two properties of being robust as well as recoverable; where robust means that the failure of a set of not too many edges of can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, has a perfect matching for which the symmetric difference of and is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 210–213 2015

Let $G$ be a finite, simple, and undirected graph and let $S$ be a set of vertices of $G$. If no vertex of $G$ that does not belong to $S$ has two neighbors in $S$, then $S$ is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ of $S$ is the smallest $P_3$-convex set containing $S$. The $P_3$-Carathéodory number of $G$ is the smallest integer $c$ such that for every set $S$ and every vertex $u$ in $H_G(S)$, there is a set $F\subseteq S$ with $|F|\leq c$ and $u\in H_G(F)$. We study structural and algorithmic aspects of the $P_3$-Carathéodory number. We characterize the $P_3$-Carathéodory number of trees and block graphs, establish upper bounds on the $P_3$-Carathéodory number of general graphs and of claw-free graphs, and prove that it is NP-complete to decide for a given bipartite graph $G$ and a given integer $k$ whether the $P_3$-Carathéodory number of $G$ is at least $k$.

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number $h(G)$ of a graph G is the smallest cardinality of a set of vertices whose convex hull is the vertex set of G. For a connected triangle-free graph G of order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ if G has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if G is cubic. Furthermore for a connected graph G of order n, girth g at least 5, minimum degree at least 2, and diameter d, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.