Saturday , April 27 2024

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

Mihai TĂLMACIU1, Victor LEPIN2
1“Vasile Alecsandri” University of Bacău,
Bacău, Romania
mtalmaciu@ub.ro
2 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

  1. Introduction

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

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.

REFERENCES

  1. 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
  2. ASRATIAN, A. S., Every 3-connected, Locally Connected, Claw-free Graph is Hamilton-connected, J. Graph Theory, vol. 23, 1996, pp. 191-201.
  3. BERGE, C. Graphs, Amsterdam, 1985.
  4. 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.
  1. 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.
  2. BROUSEK, J., Minimal 2-connected Non-Hamiltonian Claw-free Graphs, Discrete Math, vol. 191, 1998, pp. 57-64.
  3. 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.
  4. 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.
  5. CORNEIL, D. G., S. OLARIU, L. STEWART, Asteroidal Triple-free Graphs, SIAM J. Discrete Math., vol. 10, 1997, pp. 399-430.
  6. 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.
  7. 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.
  8. 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.
  9. DAMASCHKE, P., Hamiltonian-hereditary Graphs, unpublished.
  10. 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.
  11. EDMONDS J., Paths, Trees and Flowers, Canadian Journal of Math, vol. 17, 1965, pp. 449-467.
  12. EVEN, S., A. PNUELI, A. LEMPEL, Permutation Graphs and Transitive Graphs, J. ACM, vol. 19, 1972, pp. 400-410.
  13. FLANDRIN, E., J. L. FOUQUET, H. LI, On Hamiltonian Claw-free Graphs, Discrete Math., vol. 111, 1993, pp. 221-229.
  14. GOLUMBIC, M. C., C. L. MONMA, W. T. TROTTER Jr., Tolerance Graphs, Discrete Applied Mathematics, vol. 9, 1984, pp. 157-170.
  15. HABIB, M., C. PAUL, A Simple Linear Time Algorithm for Cograph Recognition, Discrete Applied Mathematics, vol. 145, 2005, pp. 183-197.
  16. 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.
  17. KLOKS, T., D. KRATSCH, H. MŰLLER, Finding and Counting Small Induced Subgraphs Efficiently, Information Proc. Letters, vol. 74(34), 2000, pp. 115-121
  18. KOHLER, E., Linear Time Algorithms for Hamiltonian Problems in Claw-Free AT-Free Graphs, manuscript, 1999.
  19. 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.
  20. 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.
  21. LI, M., Hamiltonian Cycles in 3-Connected Claw-free Graphs, J. Graph Theory, vol. 17, 1993, pp. 303-313.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26.  SHEPHERD, F. B., Hamiltonicity in Claw-free Graphs, J. Combin. Theory Ser. B, vol. 53, 1991, pp. 173-194.
  27. SUMNER, D. P., Graphs with 1-factors, Proceedings of the American Mathematical Society (American Mathematical Society), vol. 42(1), 1974, pp. 8-12.
  28. TALMACIU, M., Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization – Ph. D. Thesis, “Al. I. Cuza” University Iasi, Romania, 2002.
  29. TĂLMACIU, M., E. NECHITA, Recognition Algorithm for Diamond-free Graphs, Informatica, vol.18(3), 2007,     pp. 457-462.
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved