Title

On Graphs without a C4 or a Diamond

Document Type

Article

Publication Date

4-6-2011

Publication Source

Discrete Applied Mathematics

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.

Inclusive pages

581-587

ISBN/ISSN

0166-218X

Comments

Permission documentation on file.

Publisher

Elsevier

Volume

159

Issue

7

Peer Reviewed

yes


Share

COinS