Minimal reducible bounds for induced-hereditary properties Original Research Article

Let (Ma,⊆) and (La,⊆) be the lattices of additive induced-hereditary properties of graphs and additive hereditary properties of graphs, respectively. A property R∈Ma (∈La) is called a minimal reducible bound for a property P∈Ma (∈La) if in the interval (P,R) of the lattice Ma (La) there are only irreducible properties. The set of all minimal reducible bounds of a property P∈Ma in the lattice Ma we denote by BM(P). Analogously, the set of all minimal reducible bounds of a property P∈La in La is denoted by BL(P). We establish a method to determine minimal reducible bounds for additive degenerate induced-hereditary (hereditary) properties of graphs. We show that this method can be successfully used to determine already known minimal reducible bounds for k-degenerate graphs and outerplanar graphs in the lattice La. Moreover, in terms of this method we describe the sets of minimal reducible bounds for partial k-trees and the graphs with restricted order of components in La and k-degenerate graphs in Ma.