Recognition Algorithm for Diamond-Free Graphs

Article type: Research Article

Authors: Talmaciu, Mihai | Nechita, Elena

Affiliations: Department of Mathematics and Informatics, University of Bacău, 8 Spiru Haret str., 600114 Bacău, Romania, e-mail: [email protected], [email protected]

Abstract: In this paper we recall the notion of weakly decomposition, we recall some necessary and sufficient conditions for a graph to admit such a decomposition, we introduce the recognition algorithm for the diamond-free graphs which keeps the combinatorial structure of the graph by means of the decomposition, as well as an easy possibility to determine the clique number for the diamond-free graphs.

Keywords: diamond graph, weakly decomposition, recognition algorithm

Journal: Informatica, vol. 18, no. 3, pp. 457-462, 2007