Algorithms for the Recognition of Net-free Graphs and for Computing Maximum Cardinality Matchings in Claw-free Graphs

Mihai TĂLMACIU¹, Victor LEPIN²
¹“Vasile Alecsandri” University of Bacău,
Bacău, Romania
mtalmaciu@ub.ro
²The Institute of Mathematics of the National Academy of Sciences of Belarus
lepin@im.bas-net.by

Abstract: During the last decades, numerous studies have been undertaken on the classes of net-free graphs, claw-free graphs, and the relationship between them. The notion of weakly decomposition (a partition of the set of vertices in three classes A, B, C such that A induces a connected graph and C is totally adjacent to B and totally non-adjacent to A) and the study of its properties allow us to obtain several important results such as: characterization of cographs, {P4,C4}-free and paw-free graphs. In this article, we give a characterization of net-free graphs, a characterization of claw-free graphs, using weakly decomposition. Also, we give a recognition algorithm for net-free graphs, an algorithm for determining a maximum matching in claw-free graphs, comparable with existing algorithms in terms of complexity, but using weakly decomposition.

Keywords: net-free graphs, claw-free graphs, asteroidal triple-free graphs, weakly decomposition, recognition algorithm, maximum matching in graphs.

>>Full text
CITE THIS PAPER AS:
Mihai TĂLMACIU, Victor LEPIN, Algorithms for the Recognition of Net-free Graphs and for Computing Maximum Cardinality Matchings in Claw-free Graphs, Studies in Informatics and Control, ISSN 1220-1766, vol. 23 (2), pp. 183-188, 2014. https://doi.org/10.24846/v23i2y201406