3 papers
math.CO2022
On the arboreal jump number of a poset
Evellyn S. Cavalcante, Sebastián Urrutia, Vinicius F. dos Santos
A jump is a pair of consecutive elements in an extension of a poset which are incomparable in the original poset. The arboreal jump number is an NP-hard problem that aims to find a…
cs.CC2022
On the Computational Complexity of the Strong Geodetic Recognition Problem
Carlos V. G. C. Lima, Vinicius F. dos Santos, João H. G. Sousa +1
A strong geodetic set of a graph~ is a vertex set~ in which it is possible to cover all the remaining vertices of~ by assigning a uniqu…
cs.DM2021
Disconnected Matchings
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +2
In 2005, Goddard, Hedetniemi, Hedetniemi and Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 - 138] asked the computational comple…