ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 66, 2 (1997)
pp. 261-283

FURTHER RESULTS ON VERTEX COVERING OF POWERS OF COMPLETE GRAPHS
S. Y. ALSARDARY

Abstract. A snake in a graph $G$ is defined to be a closed path in $G$ without proper chords. Let $K_n^d$ be the product of $d$ copies of the complete graph $K_n$. Wojciechowski Ref. 13 proved that for any $d\geq 2$ the hypercube $K_2^d$ can be vertex covered with at most $16$ disjoint snakes. Alsardary Ref. 6 proved that for any odd integer $n\geq 3$,$d\geq 2$ the graph $K_n^d$ can be vertex covered with $2n^3$ snakes. We show that for any even integer $n\geq 4$, $d\geq 2$ the graph $K_n^d$, can be vertex covered with $n^3$ snakes.

AMS subject classification. 05C35, 05C38
Keywords.

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc