Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Graphs with few P 4 ’s under the convexity of paths of order three

2014; Elsevier BV; Volume: 192; Linguagem: Inglês

10.1016/j.dam.2014.05.005

1872-6771

Víctor Campos, Rudini Sampaio, Ana Silva, Jayme L. Szwarcfiter,

graph theory and CDMA systems

A graph is (q,q−4) if every subset of at most q vertices induces at most q−4P4's. It therefore generalizes some different classes, as cographs and P4-sparse graphs. In this work, we propose algorithms for determining various NP-Hard graph convexity parameters within the convexity of paths of order three, for (q,q−4) graphs. All algorithms have linear-time complexity, for fixed q, and then are fixed parameter tractable. Moreover, we prove that the Carathéodory number is at most three for every cograph, P4-sparse graph and every connected (q,q−4)-graph with at least q vertices.