Source author record

Luciano N. Grippo

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On restricted completions of chordal and trivially perfect graphs

Let $G$ be a graph having a vertex $v$ such that $H = G - v$ is a trivially perfect graph. We give a polynomial-time algorithm for the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a trivially perfect graph. This is a slight variation of the well-studied {\sc Edge Completion}, also known as {\sc Minimum Fill-In}, problem. We also show that if $H$ is a chordal graph, then the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a chordal graph is \NP-complete.

preprint2022arXiv

On the generalized Helly property of hypergraphs, cliques, and bicliques

A family of sets is $(p,q)$ -intersecting if every nonempty subfamily of $p$ or fewer sets has at least $q$ elements in its total intersection. A family of sets has the $(p,q)$ -Helly property if every nonempty $(p,q)$ -intersecting subfamily has total intersection of cardinality at least $q$ . The $(2,1)$ -Helly property is the usual Helly property. A hypergraph is $(p,q)$ -Helly if its edge family has the $(p,q)$ -Helly property and hereditary $(p,q)$ -Helly if each of its subhypergraphs has the $(p,q)$ -Helly property. A graph is $(p,q)$ -clique-Helly if the family of its maximal cliques has the $(p,q)$ -the Helly property and hereditary $(p,q)$ -clique-Helly if each of its induced subgraphs is $(p,q)$ -clique-Helly. The classes of $(p,q)$ -biclique-Helly and hereditary $(p,q)$ -biclique-Helly graphs are defined analogously. We prove several characterizations of hereditary $(p,q)$ -Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. We give an improved time bound for the recognition of $(p,q)$ -Helly hypergraphs for each fixed $q$ and show that the recognition of hereditary $(p,q)$ -Helly hypergraphs can be solved in polynomial time if $p$ and $q$ are fixed but co-NP-complete if $p$ is part of the input. In addition, we generalize to $(p,q)$ -clique-Helly graphs the characterization of $p$ -clique-Helly graphs in terms of expansions and give different characterizations of hereditary $(p,q)$ -clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of $(p,q)$ -clique-Helly graphs and prove that the recognition problem of hereditary $(p,q)$ -clique-Helly graphs is polynomial-time solvable for $p$ and $q$ fixed but NP-hard if $p$ or $q$ is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (hereditary) $(p,q)$ -biclique-Helly graphs.

preprint2022arXiv

On the rank of the distance matrix of graphs

Let $G$ be a connected graph with $V(G)=\{v_1,\ldots,v_n\}$ . The $(i,j)$ -entry of the distance matrix $D(G)$ of $G$ is the distance between $v_i$ and $v_j$ . In this article, using the well-known Ramsey's theorem, we prove that for each integer $k\ge 2$ , there is a finite amount of graphs whose distance matrices have rank $k$ . We exhibit the list of graphs with distance matrices of rank $2$ and $3$ . Besides, we study the rank of the distance matrices of graphs belonging to a family of graphs with their diameters at most two, the trivially perfect graphs. We show that for each $η\ge 1$ there exists a trivially perfect graph with nullity $η$ . We also show that for threshold graphs, which are a subfamily of the family of trivially perfect graphs, the nullity is bounded by one.

preprint2020arXiv

Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs

We present formulas to compute the P3-geodetic number, the P3-hull number and the percolation time for a caterpillar, in terms of certain sequences associated with it. In addition, we find a connection between the percolation time of a unit interval graph and a parameter involving the diameter of a unit interval graph related to it. Finally, we present a hereditary graph class, defined by forbidden induced subgraphs, such that its percolation time is equal to one.

preprint2019arXiv

On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs

A $(0,1)$ -matrix has the Consecutive Ones Property (C1P) for the rows if there is a permutation of its columns such that the ones in each row appear consecutively. We say a $(0, 1)$ -matrix is nested if it has the consecutive ones property for the rows (C1P) and every two rows are either disjoint or nested. We say a $(0, 1)$ -matrix is 2-nested if it has the C1P and admits a partition of its rows into two sets such that the submatrix induced by each of these sets is nested. We say a split graph $G$ with split partition $(K, S)$ is nested (resp.\ 2-nested) if the matrix $A(S, K)$ which indicates the adjacency between vertices in $S$ and $K$ is nested (resp.\ 2-nested). In this work, we characterize nested and 2-nested matrices by minimal forbidden submatrices. This characterization leads to a minimal forbidden induced subgraph characterization for these classes of graphs, which are a superclass of threshold graphs and a subclass of split and circle graphs.

preprint2014arXiv

Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection

A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin, Soulignac, and Szwarcfiter [Discrete Appl. Math. 2013] characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used it to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden induced subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as certificate.

preprint2014arXiv

On circular-arc graphs having a model with no three arcs covering the circle

An interval graph is the intersection graph of a finite set of intervals on a line and a circular-arc graph is the intersection graph of a finite set of arcs on a circle. While a forbidden induced subgraph characterization of interval graphs was found fifty years ago, finding an analogous characterization for circular-arc graphs is a long-standing open problem. In this work, we study the intersection graphs of finite sets of arcs on a circle no three of which cover the circle, known as normal Helly circular-arc graphs. Those circular-arc graphs which are minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs were identified by Lin, Soulignac, and Szwarcfiter, who also posed the problem of determining the remaining minimal forbidden induced subgraphs. In this work, we solve their problem, obtaining the complete list of minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Luciano N. Grippo

Research overview

Is this your work?

7 publications

On restricted completions of chordal and trivially perfect graphs

On the generalized Helly property of hypergraphs, cliques, and bicliques

On the rank of the distance matrix of graphs

Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs

On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs

Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection

On circular-arc graphs having a model with no three arcs covering the circle

See the researcher in context

Building this map preview