On a Nordhaus-Gaddum type problem for independent domination
type: Item
instance of: scholarly article
title: On a Nordhaus-Gaddum type problem for independent domination
zbMATH Open document ID: 0820.05039
DOI: 10.1016/0012-365X(94)00202-T
author: E. J. Cockayne
author: Gerd H. Fricke
author: Christina M. Mynhardt
published in: Discrete Mathematics
publication date: 1995-04-17T00:00:00Z
review text: The independent domination number \(i(G)\) of a graph \(G\) is the minimum number of vertices of a subset of the vertex set of \(G\) which is simultaneously independent (consisting of pairwise non-adjacent vertices) and dominating (each vertex either is in it, or is adjacent to a vertex in it). A function \(f\) is studied; \(f(p)\) is the minimum value of the product \(i(G)i (\overline G)\) over all graphs \(G\) with \(p\) vertices (the symbol \(\overline G\) denotes the complement of \(G)\). It is proved that \[ \lim_{p \to \infty} {f(p) \over p^ 2} = {1 \over 16}. \]
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 744011
zbMATH Keywords: Nordhaus-Gaddum type problem
zbMATH Keywords: independent domination number
MaRDI profile type: Publication
cites work: The product of the independent domination numbers of a graph and its complement
cites work: On the product of upper irredundance numbers of a graph and its complement
cites work: On Complementary Graphs
full work available at URL: 0012-365x(94)00202-t
OpenAlex ID: W2018411871
description: scientific article; zbMATH DE number 744011