IJPAM: Volume 73, No. 2 (2011)

INDEPENDENT AND VERTEX COVERING NUMBER
ON KRONECKER PRODUCT OF $P_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(P_n \otimes G)=\max \big\{n \alpha(G),m\lceil \frac{n}{2} \rceil\big\}$ and $\beta(P_n \otimes G)=\min \big\{n \beta(G),m\lfloor\frac{n}{2}\rfloor \big\}$.

Received: September 7, 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: 73
Issue: 2