Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets

DOI10.47443/DML.2020.0052MaRDI QIDQ5862679zbMATH OpenOpenAlexFDO

Authors

Publication date 9 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

domination numberexcellent graphgraph product

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A graph $G=(V,E)$ is $gamma$-excellent if $V$ is a union of all $gamma$-sets of $G$, where $gamma$ stands for the domination number. Let $mathcalI$ be a set of all mutually nonisomorphic graphs and $emptysetot=mathcalHsubsetneqmathcalI$. In this paper we initiate the study of the $mathcalH$-$gamma$-excellent graphs, which we define as follows. A graph $G$ is $mathcalH$-$gamma$-excellent if the following hold: (i) for every $HinmathcalH$ and for each $xinV(G)$ there exists an induced subgraph $H_x$ of $G$ such that $H$ and $H_x$ are isomorphic, $xinV(H_x)$ and $V(H_x)$ is a subset of some $gamma$-set of $G$, and (ii) the vertex set of every induced subgraph $H$ of $G$, which is isomorphic to some element of $mathcalH$, is a subset of some $gamma$-set of $G$. For each of some well known graphs, including cycles, trees and some cartesian products of two graphs, we describe its largest set $mathcalHsubsetneqmathcalI$ for which the graph is $mathcalH$-$gamma$-excellent. Results on $gamma$-excellent regular graphs and a generalized lexicographic product of graphs are presented. Several open problems and questions are posed.

Recommendations

• A note on excellent graphs.
• Every γ-excellent, γ-flexible graph is γ_bi-excellent
• Very excellent graphs and rigid very excellent graphs
• Total domination excellent trees
• Total domination of graphs

Cites work

• \(\gamma\)-excellent, critically dominated, end-dominated, and dot-critical trees are equivalent
• A characterization of \(i\)-excellent trees
• Domination critical graphs
• Domination in graphs of minimum degree five
• DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
• Fast generation of regular graphs and construction of cages
• scientific article; zbMATH DE number 5978816 (Why is no real title available?)
• scientific article; zbMATH DE number 3732108 (Why is no real title available?)
• scientific article; zbMATH DE number 21746 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1744072 (Why is no real title available?)
• scientific article; zbMATH DE number 2188623 (Why is no real title available?)
• Minimal dominating sets of cardinality two in a graph
• Paths, Stars and the Number Three
• Roman domination excellent graphs: trees
• Some covering concepts in graphs
• Total domination excellent trees
• Vertex domination-critical graphs
• Very excellent graphs and rigid very excellent graphs
• Well-covered graphs and extendability

Cited in

(7)

• Very excellent graphs and rigid very excellent graphs
• scientific article; zbMATH DE number 1744072 (Why is no real title available?)
• Every γ-excellent, γ-flexible graph is γ_bi-excellent
• Total domination of graphs
• scientific article; zbMATH DE number 5244573 (Why is no real title available?)
• A note on excellent graphs.
• \(\gamma\)-excellent, critically dominated, end-dominated, and dot-critical trees are equivalent

Describes a project that uses

Uses Software

• GENREG

This page was built for publication: Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets

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