IJPAM: Volume 71, No. 1 (2011)

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

Thanin Sitthiwirattham$^1$, Jarunee Soontharanon$^2$
$^1$Department of Mathematics
Faculty of Applied Science
King Mongkut's University of Technology
North 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(C_n \otimes G)=\max \big\{n \alpha(G),m\lfloor\frac{n}{2}\rfloor \big\}$ and $\beta(C_n \otimes G)=\min \big\{n \beta(G),m\lceil \frac{n}{2}\rceil\big\}$.

Received: May 31, 2011

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: 2011
Volume: 71
Issue: 1