The rati of the irredundance and domination number of a graph
type: Item
instance of: scholarly article
title: The rati of the irredundance and domination number of a graph
zbMATH Open document ID: 0888.05037
DOI: 10.1016/S0012-365X(97)81829-8
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 1998-06-01T00:00:00Z
review text: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if each vertex of \(G\) either belongs to \(D\), or is adjacent to a vertex of \(D\). A vertex \(x\) of a subset \(I\) of \(V(G)\) is called redundant in \(I\), if each vertex adjacent to \(x\) is adjacent to another vertex of \(I\). If \(I\) does not contain redundant vertices, it is called irredundant. The minimum number of vertices of a dominating (or irredundant) set in \(G\) is the domination number \(\gamma(G)\) (or irredundance number \(\text{ir}(G)\) respectively) of \(G\). The main result of the paper states that if either the cyclomatic number \(\mu(G)\) of \(G\) is at most 2, or \(G\) is a block graph, then \(2\gamma(G)\leq 3\text{ ir}(G)\). It is conjectured that \(\text{ir}(G)/\gamma(G)> 5/8\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1110086
zbMATH Keywords: domination number
zbMATH Keywords: irredundance number
zbMATH Keywords: cyclomatic number
zbMATH Keywords: block graph
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Q4189317
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: Q4060985
cites work: Irredundance number versus domination number
cites work: Q3748280
Recommended article: The ratio of the distance irredundance and domination numbers of a graph
Recommended article: Partial domination and irredundance numbers in graphs
Recommended article: On the \(r\)-domination number of a graph
Recommended article: Q4847233
Recommended article: On the ratio of the domination number and the independent domination number in graphs
Recommended article: Distance irredundance and connected domination numbers of a graph
Recommended article: Q4871033
Recommended article: The ratio of the irredundance number and the domination number for block-cactus graphs
Recommended article: Q3070322
Recommended article: Generalized domination, independence and irredudance in graphs
description: scientific article; zbMATH DE number 1110086