6 papers · 1 filter
On the generalized Helly property of hypergraphs, cliques, and bicliques
Mitre C. Dourado, Luciano N. Grippo, Martín D. Safe
A family of sets is -intersecting if every nonempty subfamily of or fewer sets has at least elements in its total intersection. A family of sets has the -Hell…
Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
Lucía M. González, Luciano N. Grippo, Martín D. Safe
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,…
Covering graphs with convex sets and partitioning graphs into convex sets
Lucía M. González, Luciano N. Grippo, Martín D. Safe +1
We present some complexity results concerning the problems of covering a graph with convex sets and of partitioning a graph into convex sets. The following convexities are…
Circularly compatible ones, -circularity, and proper circular-arc bigraphs
Martín D. Safe
In 1969, Alan Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also fou…
Partial characterization of graphs having a single large Laplacian eigenvalue
L. Emilio Allem, Antonio Cafure, Ezequiel Dratman +3
The parameter of a graph stands for the number of Laplacian eigenvalues greater than or equal to the average degree of . In this work, we address the problem of chara…
A - and sparsest basis for the null space of a forest in optimal time
Daniel A. Jaume, Gonzalo Molina, Adrián Pastine +1
Given a matrix, the Null Space Problem asks for a basis of its null space having the fewest nonzeros. This problem is known to be NP-complete and even hard to approximate. The null…