Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421097 | Discrete Applied Mathematics | 2015 | 12 Pages |
Abstract
A graph is (q,q−4)(q,q−4) if every subset of at most qq vertices induces at most q−4P4’s. It therefore generalizes some different classes, as cographs and P4P4-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)(q,q−4) graphs. All algorithms have linear-time complexity, for fixed qq, and then are fixed parameter tractable. Moreover, we prove that the Carathéodory number is at most three for every cograph, P4P4-sparse graph and every connected (q,q−4)(q,q−4)-graph with at least qq vertices.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Victor Campos, Rudini M. Sampaio, Ana Silva, Jayme L. Szwarcfiter,