Finding a sun in building-free graphs

Details Finding a sun in building-free graphs Finding a sun in building-free graphs

2009-10-09

arxiv.org/abs/0910.1808v1

Computer Science

Discrete Mathematics

3 figures

Scientific paper

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) 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.

Affiliated with

Also associated with

No associations

Rating

Finding a sun in building-free graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding a sun in building-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding a sun in building-free graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51960