A Note on Bound Graphs and Clique Covers

Shin-ichi IWAI1, Kenjiro OGAWA2, Morimasa TSUCHIYA3
1Department of Mathematical Sciences, Tokai University Hiratsuka 259-1292, JAPAN
2 Department of Mathematical Sciences, Tokai University Hiratsuka 259-1292, JAPAN
3 Department of Mathematical Sciences, Tokai University Hiratsuka 259-1292, JAPAN

Abstract

McMorris, Zaslavsky, and Diny give characterizations of upper bound graphs and double bound graphs in terms of edge clique covers, that is, a family of maximal complete subgraphs that covers all edges. Lundgren and Maybee give a characterization of upper bound graphs using a concept of non-maximal complete subgraphs. In this paper, we present characterizations of double bound graphs and semi-bound graphs in terms of edge covers of non-maximal complete subgraphs.