Well-dominated graphs without cycles of lengths 4 and 5

DOI10.1016/J.DISC.2017.02.021MaRDI QIDQ2397523zbMATHOpenAlexFDO

Authors Vadim E. Levit, David Tankus

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

maximal independent setwell-covered graphvector spaceminimal dominating setwell-dominated graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a graph. A set $S$ of vertices in $G$ dominates the graph if every vertex of $G$ is either in $S$ or a neighbor of a vertex in $S$. Finding a minimal cardinality set which dominates the graph is an NP-complete problem. The graph $G$ is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths $4$ and $5$, by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function $w$ is defined on the vertices of $G$. Then $G$ is $w$-well-dominated} if all its minimal dominating sets are of the same weight. We prove that the set of weight functions $w$ such that $G$ is $w$-well-dominated is a vector space, and denote that vector space by $WWD(G)$. We prove that $WWD(G)$ is a subspace of $WCW(G)$, the vector space of weight functions $w$ such that $G$ is $w$-well-covered. We provide a polynomial characterization of $WWD(G)$ for the case that $G$ does not contain cycles of lengths $4$, $5$, and $6$.

Recommendations

• scientific article; zbMATH DE number 4063149
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• Well-covered graphs without cycles of lengths 4, 5 and 6
• The structure of well-covered graphs with no cycles of length 4
• Well-totally-dominated graphs

Cites work

• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A characterization of well covered graphs of girth 5 or greater
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Complexity results for generating subgraphs
• Complexity results for well‐covered graphs
• Domination in Graphs
• Local Structure When All Maximal Independent Sets Have Equal Weight
• Recognizing Greedy Structures
• The structure of well-covered graphs with no cycles of length 4
• The well-covered dimension of random graphs
• Weighted well-covered claw-free graphs
• Well covered simplicial, chordal, and circular arc graphs
• Well-Covered Vector Spaces of Graphs
• Well-covered graphs without cycles of lengths 4, 5 and 6

Cited in

(8)

• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• \((C_3, C_4, C_5, C_7)\)-free almost well-dominated graphs
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• On well-dominated graphs
• Well-totally-dominated graphs
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• A characterization of well-dominated Cartesian products
• Recognizing well-dominated graphs is coNP-complete

This page was built for publication: Well-dominated graphs without cycles of lengths 4 and 5

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