IJPAM: Volume 72, No. 3 (2011)

MATCHING NUMBER AND EDGE COVERING NUMBER
ON KRONECKER PRODUCT OF $C_n$

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


Abstract. Let $\alpha'(G)$ and $\beta'(G)$ be the matching number and edge covering number, respectively. The Kronecker Product $G_1 \otimes G_2$ of graph $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

\begin{displaymath}\alpha'(C_n \otimes G)=\max \big\{n \alpha'(G),m\lfloor\frac{... ...mes G)=\min \big\{n \beta'(G ),m\lceil \frac{n}{2}\rceil\big\}.\end{displaymath}



Received: July 7, 2011

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

Key Words and Phrases: Kronecker product, matching number, edge 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: 72
Issue: 3