Well-dominated graphs without cycles of lengths 4 and 5

DOI10.1016/J.DISC.2017.02.021zbMATH Open1362.05098arXiv1409.1466OpenAlexW167884697MaRDI QIDQ2397523FDOQ2397523

Authors: Vadim E. Levit, David Tankus 

Publication date: 22 May 2017

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

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$.

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

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

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)

Cites Work

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

Cited In (7)

• Recognizing well-dominated graphs is coNP-complete
• \((C_3, C_4, C_5, C_7)\)-free almost well-dominated graphs
• Title not available (Why is that?)
• On well-dominated graphs
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• Well-totally-dominated graphs
• A characterization of well-dominated Cartesian products

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)