2022/08/15 by Dettlaff, Magda, Henning, Michael A., Topp, Jerzy
#Combinatorics (math.CO) #F.2.2 #FOS: Mathematics
paper · doi:10.48550/arxiv.2208.07092
A dominating set in a graph G is a set S of vertices such that every vertex that does not belong to S is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. The common independence number αc(G) of G is the greatest integer r such that every vertex of G belongs to some independent set of cardinality at least~r. The common independence number is squeezed between the independent domination number i(G) and the independence number α(G) of G, that is, γ(G) ≤ i(G) ≤ αc(G) ≤ α(G). A graph G is domination perfect if γ(H) = i(H) for every induced subgraph H of G. We define a graph G as common domination perfect if γ(H) = αc(H) for every induced subgraph H of G. We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs.