Article ID Journal Published Year Pages File Type
421097 Discrete Applied Mathematics 2015 12 Pages PDF
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
, , , ,