Common domination perfect graphs

Abstract: 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 a m m a (G)

of

G

is the minimum cardinality of a dominating set of

G

. The common independence number

a l p h a_{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

a l p h a (G)

of

G

, that is,

g a m m a (G) l e i (G) l e a l p h a_{c} (G) l e a l p h a (G)

. A graph

G

is domination perfect if

g a m m a (H) = i (H)

for every induced subgraph

H

of

G

. We define a graph

G

as common domination perfect if

g a m m a (H) = a l p h a_{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.

Recommendations

Cites work

This page was built for publication: Common domination perfect graphs