Quick search
Go!

ON {CLAW, ANTENNA, NET}-FREE GRAPHS


MIHAI TALMACIU
“Vasile Alecsandri" University of Bacău, Faculty of Sciences Department of Mathematics, Informatics and Education Sciences Calea Mărăşeşti 157, Bacău 600115, ROMANIA,
Corresponding author: mtalmaciu@ub.ro

Issue:

SSRSMI, Number 1, Volume XXIV

Section:

Volume 24, Number 1

Abstract:

In this article, we give a characterization of {claw; antenna; net}-free graphs, a characterization of claw-free graphs, using weakly decomposition. Also, we give a O(n(n + m)) recognition algorithm for {claw; antenna; net}-free graphs, but using weakly decomposition. During the last three decades, different types of decompositions have been processed in the field of graph theory. Among these we mention: decompositions based on the additivity of some characteristics of the graph, decompositions where the adjacency law between the subsets of the partition is known, decompositions where the subgraph induced by every subset of the partition must have predetermined properties, as well as combinations of such decompositions. In various problems in graph theory, for example in the construction of recognition algorithms, frequently appears the so-called weakly decomposition of graphs.

Keywords:

net-free graphs, claw-free graphs, antenna-free graphs, asteroidal triple-free graphs, weakly decomposition, recognition algorithm.

Code [ID]:

SSRSMI20140124V24S01A0012 [0004069]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacu