IJPAM: Volume 77, No. 1 (2012)

INDEPENDENT AND VERTEX COVERING NUMBER
ON KRONECKER PRODUCT OF $K_n$

Thanin Sitthiwirattham$^{1,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 Kronecker Product $G_1 \otimes G_2$ of graph of $G_1$ and $G_2$ has vertex set $V(G_1 \otimes G_2)=V(G_1)\times V(G_2)$ and edge set $E(G_1 \otimes G_2)=\{(u_1v_1)(u_2v_2)\vert u_1u_2 \in E(G_1)$ and $v_1v_2 \in E(G_2)\}$. In this paper, let $G$ is a simple graph with order m, we prove that, $\alpha(K_n \otimes G)=\max \big\{n\alpha(G),m \big\}$ and $\beta(K_n \otimes G)=\min \big\{n \beta(G),m(n-1) \big\}$.

Received: March 3, 2012

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

Key Words and Phrases: Kronecker 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: 77
Issue: 1