IJPAM: Volume 62, No. 4 (2010)

THE BASIS NUMBER AND MINIMAL CYCLE BASES
OF THE STRONG PRODUCT OF PATHS
AND CYCLES WITH TENETS

Maref Y.M. Alzoubi
Department of Mathematics
College of Science
Al-Qassim University
P.O. Box 6655, Buraidah, Al-Qassim, KINGDOM OF SAUDI ARABIA
e-mail: [email protected]


Abstract.The basis number of the graph $G$, denoted by b $\left( G\right) $, is the smallest integer $k$ such that the cycle space, $\mathcal{C}\left( G\right)
$, has a $k$-fold basis. A basis is called $k$-fold basis if each edge of $%
G $ occurs in at most $k$ of the cycles in the basis. In this paper we prove that the basis number of the strong product of paths with tenets is at most $4$, the basis number of the strong product of cycles with tenets is at most $5$. Also, we give explicit minimal cycle bases for these graphs.

Received: April 25, 2010

AMS Subject Classification: 05C38, 15A03

Key Words and Phrases: cycle basis, cycle space, minimal cycle basis, fold and basis number

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2010
Volume: 62
Issue: 4