On Graphs without a C4 or a Diamond

Author(s)

Elaine M. Eschen, West Virginia University
Chính T. Hoàng, Wilfrid Laurier University
Jeremy P. Spinrad, Vanderbilt University
R. Sritharan, University of DaytonFollow

Document Type

Article

Publication Date

4-6-2011

Publication Source

Discrete Applied Mathematics

Abstract

We consider the class of (C₄, diamond)-free graphs; graphs in this class do not contain a C₄ 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 (C₄, diamond)-free graph and the number of n-vertex, labeled (C₄, 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.

Copyright

Copyright © 2010, Elsevier

Publisher

Elsevier

Volume

159

Peer Reviewed

yes

Issue

7

eCommons Citation

Eschen, Elaine M.; Hoàng, Chính T.; Spinrad, Jeremy P.; and Sritharan, R., "On Graphs without a C4 or a Diamond" (2011). Computer Science Faculty Publications. 166.
https://ecommons.udayton.edu/cps_fac_pub/166