**Algorithms for the Recognition of Net-free Graphs and**

for Computing Maximum Cardinality Matchings in

Claw-free Graphs

for Computing Maximum Cardinality Matchings in

Claw-free Graphs

**Mihai TĂLMACIU ^{1}, Victor LEPIN^{2}**

^{1}*“*Vasile Alecsandri” University of Bacău,

Bacău, Romania

mtalmaciu@ub.ro

**The Institute of Mathematics of the National Academy of Sciences of Belarus**

^{2 }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.

**Introduction**

A graph is *claw-free *if it has no induced subgraph isomorphic to the claw, i.e., the four-vertex star .

A *net* is a graph obtained from a triangle by attaching to each vertex a new dangling edge.

The interval graphs [24], permutation graphs [16] and co-comparability graphs [18] have a linear structure. Each of these classes is a subfamily of the asteroidal triple graphs (AT-free graphs, for short). An independent set of three vertices is called an asteroidal triple if between any pair in the triple there exists a path that avoids the neighbourhood of the third. AT-free graphs were introduced by Lekkerkerker and Boland [24]. Corneil, Olariu and Stewart showed a number of results on the linear structure of AT-free [8, 9, 10].

A maximal subclass of a class of net-free graphs is the class (claw,net)-free graphs (CN-free graphs, for short). Also note that CN-free graphs are exactly the Hamiltonian-hereditary graphs[13] (was cited in [4]). CN-free graphs turn out to be closely related to AT-free graphs form their structure properties [4]. There are, however, few results about the structure of these graphs [4]. In [4] the authors give results on the linear and circular structure of CN-free graphs. AT-free graphs can be generalized in a manner obvious to admit circular structure [4]. CN-free graphs were introduced by Duffus [14]. Although CN-free graphs seems to be quite restrictive, it contains a couple of families of graphs that are interesting in their own right.

In this paper we give an algorithm for the recognition of net-free graph of complexity O(n(n+ m1,63)). Also, we give an interesting property of claw-free graph that leads to a algorithm for the construction a maximum matching in claw-free graphs.

The content of the paper is organized as follows. In Preliminaries, we give the usual terminology in graph theory. In Section 3 we give a characterization of net-free graphs and a recognition algorithm using the weakly decomposition. In Section 4 we determine a maximum matching in the claw-free graph. Ideas for future work conclude the paper.

**R EFERENCES**

- ALON, N., R. YUSTER, U. ZWICK,
**Finding and Counting Given Length Cycles**, Proc. 2nd European Symposium on Algorithms, Utrecht, The Netherlands, 1994, pp. 354-364 - ASRATIAN, A. S.,
**Every 3-connected, Locally Connected, Claw-free Graph is Hamilton-connected**, J. Graph Theory, vol. 23, 1996, pp. 191-201. - BERGE, C.
**Graphs**, Amsterdam, 1985. - BRANDSTEDTA, A., F. F. DRĂGAN,
**On Linear and Circular Structure of (Claw, Net)-free Graphs**, Discrete Applied Mathematics, vol. 129(23), 2003, pp. 285-303.

- BRANDSTADT, A., F. F. DRĂGAN, E. KOHLER,
**Linear Time Algorithms for Hamiltonian Problems on (Claw, Net)-free Graphs**, SIAM J. COMPUT., Vol. 30(5), 2000, pp. 1662-1677. - BROUSEK, J.,
**Minimal 2-connected Non-Hamiltonian Claw-free Graphs**, Discrete Math, vol. 191, 1998, pp. 57-64. - CHUDNOVSKY, M., P. SEYMOUR,
**The Structure of Claw-free Graphs**, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 327, Cambridge: Cambridge Univ. Press, 2005, pp. 153-171. - CORNEIL, D. G., S. OLARIU, L. STEWART,
**A Linear Time Algorithm to Compute a Dominating Path in an AT-free Graph**, Inform. Proc. Lett. Vol. 54, 1995, pp. 253-257. - CORNEIL, D. G., S. OLARIU, L. STEWART,
**Asteroidal Triple-free Graphs**, SIAM J. Discrete Math., vol. 10, 1997, pp. 399-430. - CORNEIL, D. G., S. OLARIU, L. STEWART,
**Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs**, SIAM J. Comput. vol. 28, 1999, pp. 1284-1297. - CROITORU, C., E. OLARU, M. TALMACIU,
**Confidentially connected Graphs**, The annals of “Dunarea de Jos” Univ. of Galati, Proc. of the Intl. Conf. “The Risk in Contemporary Economy”, Suppl. to Tome XVIII (XXII), 2000, pp. 17-20. - CROITORU, C., M. TĂLMACIU,
**On Confidentially Connected Graphs**, Bul. Stiint. Univ. Baia Mare, Ser B, Matematica – Informatica, vol. XVI(1), 2000, pp. 13-16. - DAMASCHKE, P.,
**Hamiltonian-hereditary Graphs**, unpublished. - DUFFUS, D., M. S. JACOBSON, R. J. GOULD,
**Forbidden Subgraphs and the Hamiltonian Theme,**in The Theory and Applications of Graphs, (Kalamazoo, Mich, 1980), Wiley, New York, pp. 297-316. - EDMONDS J.,
**Paths**,**Trees and Flowers**, Canadian Journal of Math, vol. 17, 1965, pp. 449-467. - EVEN, S., A. PNUELI, A. LEMPEL,
**Permutation Graphs and Transitive Graphs**, J. ACM, vol. 19, 1972, pp. 400-410. - FLANDRIN, E., J. L. FOUQUET, H. LI,
**On Hamiltonian Claw-free Graphs**, Discrete Math., vol. 111, 1993, pp. 221-229. - GOLUMBIC, M. C., C. L. MONMA, W. T. TROTTER Jr.,
**Tolerance Graphs**, Discrete Applied Mathematics, vol. 9, 1984, pp. 157-170. - HABIB, M., C. PAUL,
**A Simple Linear Time Algorithm for Cograph Recognition**, Discrete Applied Mathematics, vol. 145, 2005, pp. 183-197. - HERNANDEZ-MARTINEZ, E. G., E. ARANDA-BRICAIRE,
**Decentralized Formation Control of Multi-agent Robot Systems based on Formation Graphs**, Studies in Informatics and Control, vol. 21(1), pp. 7-16, 2012. - KLOKS, T., D. KRATSCH, H. MŰLLER,
**Finding and Counting Small Induced Subgraphs Efficiently**, Information Proc. Letters, vol. 74(34), 2000, pp. 115-121 - KOHLER, E.,
**Linear Time Algorithms for Hamiltonian Problems in Claw-Free AT-Free Graphs**, manuscript, 1999. - Las VERGNAS, M.
**A Note on Matchings in Graphs**, Cahiers du Centre d’etudes de Recherche Operationnelle, vol. 17(2-3-4), 1975, pp. 257-260. - LEKKERKERKER, C. G., J. C. BOLAND,
**Representation of a Finite Graph by a Set of Intervals on the Real Line**, Fund. Math., vol. 51, 1962, pp. 45-64. - LI, M.,
**Hamiltonian Cycles in 3-Connected Claw-free Graphs**, J. Graph Theory, vol. 17, 1993, pp. 303-313. - MINTY, G. J.,
**On Maximal Independent Sets of Vertices in Claw-free Graphs**, Journal of Combinatorial Theory. Series B, vol. 28(3), 1980, pp. 284-304. - NAKAMURA, D., A. TAMURA,
**A Revision of Minty’s Algorithm for Finding a Maximum Weighted Stable Set of a Claw-free Graph**, Journal of the Operations Research Society of Japan, vol. 44(2), 2001, pp. 194-204. - POCATILU, P., I. IVAN,
**A Genetic Algorithm-based System for Automatic Control of Test Data Generation**, Studies in Informatics and Control, vol. 22(2), 2013, pp. 219-226. - SBIHI, N.,
**Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile**, Discrete Mathematics, vol. 29(1), 1980, pp. 53-76. - SHEPHERD, F. B.,
**Hamiltonicity in Claw-free Graphs**, J. Combin. Theory Ser. B, vol. 53, 1991, pp. 173-194. - SUMNER, D. P.,
**Graphs with 1-factors**, Proceedings of the American Mathematical Society (American Mathematical Society), vol. 42(1), 1974, pp. 8-12. - TALMACIU, M.,
**Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization**– Ph. D. Thesis, “Al. I. Cuza” University Iasi, Romania, 2002. - TĂLMACIU, M., E. NECHITA,
**Recognition Algorithm for Diamond-free Graphs**, Informatica, vol.18(3), 2007, pp. 457-462.