Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone

Author(s)

Pinar Heggernes, University of Bergen
Federico Mancini, University of Bergen
Charis Papadopoulos, University of Ioannina
R. Sritharan, University of DaytonFollow

Document Type

Article

Publication Date

10-2011

Publication Source

Journal of Combinatorial Optimization

Abstract

A graph class is sandwich monotone if, for every pair of its graphs G₁=(V,E₁) and G₂=(V,E₂) with E₁⊂E₂, there is an ordering e₁,…,e_k of the edges in E₂∖E₁ such that G=(V,E₁∪{e₁,…,e_i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.

Inclusive pages

438–456

ISBN/ISSN

1382-6905

Comments

Permission documentation on file.

Copyright

Copyright © 2010, Springer

Publisher

Springer

Volume

22

Peer Reviewed

yes

Issue

3

eCommons Citation

Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; and Sritharan, R., "Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone" (2011). Computer Science Faculty Publications. 167.
https://ecommons.udayton.edu/cps_fac_pub/167