IJPAM: Volume 44, No. 2 (2008)

CONNECTED GRAPHS AND THEIR CONNECTIVITIES

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


Abstract.Let $m$ and $n$ be positive integers with $n-1\le m\le {n\choose 2}$ and $\mathcal{CG}(m,n)$ be the set of all non-isomorphic connected graphs of order $n$ and size $m$. The vertex-connectivity and the edge-connectivity of a graph $G$ are denoted by $\kappa(G)$ and $\lambda(G)$, respectively. We prove that if $\pi\in\{\kappa, \lambda\}$, then there exist positive integers $a$ and $b$ such that $\{\pi(G):G\in \mathcal{CG}(m,n)\}=\{x\in \Z:a\le x\le b\}$. Thus $\{\pi(G):G\in \mathcal{CG}(m,n)\}$ is uniquely determined by $\min(\pi; m, n)=\min\{\pi(G):G\in \mathcal{CG}(m,n)\}$ and $\max(\pi; m, n)=\max\{\pi(G):G\in \mathcal{CG}(m,n)\}$. The values of $\min(\pi; m, n)$ and $\max(\pi; m, n)$ are obtained in all situations.

Received: February 10, 2008

AMS Subject Classification: 05C40

Key Words and Phrases: interpolation, connectivity

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 44
Issue: 2