IJPAM: Volume 81, No. 3 (2012)

INDEPENDENT AND VERTEX COVERING NUMBER
ON STRONG PRODUCT OF COMPLETE GRAPHS

Chanasak Baitiang$^1$, Thanin Sitthiwirattham$^2$
$^1$Department of Mathematics
Faculty of Applied Science
King Mongkut's University of Technology North Bangkok
Bangkok, 10800, THAILAND
$^2$Centre of Excellence in Mathematics, CHE
Sri Ayutthaya Road, Bangkok 10400, THAILAND


Abstract. Let $\alpha(G)$ and $\beta(G)$ be the independent number and vertex covering number, respectively. The strong Product $G_1 \boxtimes G_2$ of graph of $G_1$ and $G_2$ has vertex set $V(G_1 \boxtimes G_2)=V(G_1)\times V(G_2)$ and edge set $E(G_1 \boxtimes G_2)=\{(u_1v_1)(u_2v_2)\vert[u_1u_2 \in E(G_1)$ and $v_1v_2 \in E(G_2)]\cup[u_1=u_2$ and $v_1v_2 \in E(G_2)]\cup[u_1u_2 \in E(G_1)$ and $v_1=v_2]\}$. In this paper, let $G$ is a simple graph with order m, we prove that, $\alpha(K_n \boxtimes G)=\alpha(G)$ and $\beta(K_n \boxtimes G)=mn-\alpha(G)$.

Received: September 3, 2012

AMS Subject Classification: 05C69, 05C70, 05C76

Key Words and Phrases: strong product, independent number, vertex covering number

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 81
Issue: 3