Common domination perfect graphs

DOI10.1016/J.DAM.2023.09.028MaRDI QIDQ6184333zbMATH OpenOpenAlexFDO

Authors Magda Dettlaff, Michael A. Henning, Jerzy Topp

Publication date 24 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.07092

common domination perfect domination perfect forbidden induced subgraphs

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Review text

A subset \(S\) of vertices of a graph \(G\) is said to be an independent set if no two vertices in \(S\) are adjacent. A dominating set of a graph \(G\) is a set \(S\) of vertices of \(G\) such that every vertex of \(G\) is in \(S\) or has a neighbor in \(S\), where two vertices are neighbors in \(G\) if they are adjacent. An independent dominating set of a graph \(G\) is a dominating set of vertices that is also an independent set of \(G\). The independence number of a graph \(G\), denoted \(\alpha(G)\), is the cardinality of a maximum independent set of \(G\). The domination number of a graph \(G\), denoted \(\gamma(G)\), is the cardinality of a minimum dominating set of \(G\), while the independent domination number of \(G\), denoted \(i(G)\), is the cardinality of a minimum independent dominating set of \(G\). The common independence number of a graph \(G\), denoted by \(α_c(G)\), is the greatest integer \(r\) such that every vertex of \(G\) belongs to some independent set in \(G\) of cardinality at least \(r\). Motivated by the concept of perfect graphs in the chromatic sense, \textit{D. P. Sumner} and \textit{J. L. Moore} [``Domination perfect graphs, Notices Am. Math. Soc. A-569 (1979)] defined a graph \(G\) to be domination perfect if \(\gamma(H)=i(H)\) for every induced subgraph \(H\) of \(G\). The authors define a graph \(G\) as common domination perfect if \(\gamma(H)=\alpha_c(H)\) for every induced subgraph \(H\) of \(G\). A characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs is provided.

Recommendations

Cites work

This page was built for publication: Common domination perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184333)