Finding a Sun in Building-Free Graphs

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

5-2012

Publication Source

Graphs and Combinatorics

Abstract

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn³, m^1.5n²}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.

Inclusive pages

347–364

ISBN/ISSN

0911-0119

Comments

Permission documentation on file.

Copyright

Copyright © 2011, Springer

Publisher

Springer

Volume

28

Peer Reviewed

yes

Issue

3

eCommons Citation

Eschen, Elaine M.; Hoàng, Chính T.; Spinrad, Jeremy P.; and Sritharan, R., "Finding a Sun in Building-Free Graphs" (2012). Computer Science Faculty Publications. 169.
https://ecommons.udayton.edu/cps_fac_pub/169