Premium
k ‐Bounded classes of dominant‐independent perfect graphs
Author(s) -
Zverovich Igor E.
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199911)32:3<303::aid-jgt8>3.0.co;2-b
Subject(s) - combinatorics , mathematics , induced subgraph , conjecture , graph , independence number , domination analysis , bounded function , discrete mathematics , vertex (graph theory) , mathematical analysis
Let α( G ), γ( G ), and i ( G ) be the independence number, the domination number, and the independent domination number of a graph G , respectively. For any k ≥ 0, we define the following hereditary classes: α i ( k ) = { G : α( H ) − i ( H ) ≤ k for every H ∈ ISub( G )}; αγ( k ) = { G : α( H ) − γ( H ) ≤ k for every H ∈ ISub( G )}; and i γ( k ) = { G : i ( H ) − γ( H ) ≤ k for every H ∈ ISub( G )}, where ISub( G ) is the set of all induced subgraphs of a graph G . In this article, we present a finite forbidden induced subgraph characterization for α i ( k ) and αγ( k ) for any k ≥ 0. We conjecture that i γ( k ) also has such a characterization. Up to the present, it is known only for i γ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999