4 papers
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…