IJPAM: Volume 41, No. 4 (2007)

THE DOMINATION NUMBER OF CONNECTED GRAPHS

Aunyarat Bunyawat$^1$, Araya Chaemchan$^2$
$^1$Department of Mathematics
Mahidol Wittayanusorn School
Salaya, Nakhon Pathom, 73170, THAILAND
$^2$Department of Mathematics and Statistics
Faculty of Science and Technology
Thammasat University
Rangsit, Pathumthani, 12120, THAILAND
e-mail: araya@mathstat.sci.tu.ac.th


Abstract.Let $\gamma(G)$ be the domination number of a graph $G$ and $\C(m,n)$ be the class of all non-isomorphic connected graphs of order $n$ and size $m$. Punnim [#!NP!#] proved that for any positive integers $n$ and $m$ with $n-1\le m\le {n\choose 2}$, there exist positive integers $a$ and $b$ in which there exists a graph $G\in \C(m,n)$ such that $\gamma(G)=c$ if and only if $c$ is an integer and $a\le c\le b$. Thus for any positive integers $m$ and $n$, $\{\gamma(G):G\in \C(m,n)\}$ is uniquely determined by
\begin{align*} &a := \min(\gamma;m,n) = \min\{\gamma(G) : G \in \C(m,n)\}\,,\qua... ...and}\\ &b := \max(\gamma;m,n) = \max\{\gamma(G) : G \in \C(m,n)\}. \end{align*}

We are able to find the values of $\min(\gamma;m,n)$ and $\max(\gamma;m,n)$ in all situations.

Received: September 28, 2007

AMS Subject Classification: 05C35, 05C69

Key Words and Phrases: domination number, interpolation theorem, extremal problem

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 41
Issue: 4