Tight Upper Bounds for the Domination Numbers of Graphs with Given Order and Minimum Degree

Let $\gamma(n,\delta)$ denote the maximum possible domination number of a graph with $n$ vertices and minimum degree $\delta$. Using known results we determine $\gamma(n,\delta)$ for $\delta = 0, 1, 2, 3$, $n \ge \delta + 1$ and for all $n$, $\delta$ where $\delta = n-k$ and $n$ is sufficiently larg...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 1997-10, Vol.4 (1)
Main Authors: Clark, W. Edwin, Dunning, Larry A.
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let $\gamma(n,\delta)$ denote the maximum possible domination number of a graph with $n$ vertices and minimum degree $\delta$. Using known results we determine $\gamma(n,\delta)$ for $\delta = 0, 1, 2, 3$, $n \ge \delta + 1$ and for all $n$, $\delta$ where $\delta = n-k$ and $n$ is sufficiently large relative to $k$. We also obtain $\gamma(n,\delta)$ for all remaining values of $(n,\delta)$ when $n \le 14$ and all but 6 values of $(n,\delta)$ when $n = 15$ or 16.
ISSN:1077-8926
1077-8926
DOI:10.37236/1311