Back to Search
Start Over
On graphs without a C4 or a diamond
- Publication Year :
- 2009
-
Abstract
- We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 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 (C4, diamond)-free graph and the number of n-vertex, labeled (C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.
- Subjects :
- Computer Science - Discrete Mathematics
G.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.0909.4719
- Document Type :
- Working Paper