| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420105 | Discrete Applied Mathematics | 2011 | 7 Pages |
Abstract
We consider the class of (C4C4, diamond)-free graphs; graphs in this class do not contain a C4C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C4C4, diamond)-free graph and the number of nn-vertex, labeled (C4C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Elaine M. Eschen, Chính T. Hoàng, Jeremy P. Spinrad, R. Sritharan,