Back to Search
Start Over
Common domination perfect graphs
- Publication Year :
- 2022
-
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 $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. The common independence number $\alpha_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 $\alpha(G)$ of $G$, that is, $\gamma(G) \le i(G) \le \alpha_c(G) \le \alpha(G)$. A graph $G$ is domination perfect if $\gamma(H) = i(H)$ for every induced subgraph $H$ of $G$. We define a graph $G$ as common domination perfect if $\gamma(H) = \alpha_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.<br />Comment: 11 pages, 2 figures
- Subjects :
- Mathematics - Combinatorics
F.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2208.07092
- Document Type :
- Working Paper