Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0848.05063
Al-Rhayyel, A.A.
On the basis of the direct product of paths and wheels. (English)
[J] Int. J. Math. Math. Sci. 19, No.2, 411-414 (1996). ISSN 0161-1712; ISSN 1687-0425/e

For (finite, undirecte, simple) graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, the direct product $G_1 \wedge G_2$ is defined to be the graph $G = (V,E)$ with vertex set $V = V_1 \times V_2$ and edge set $$E = \{uv \mid u = (u_1, u_2) \in V,\ v = (v_1, v_2) \in V,\ u_1v_1 \in E_1, \quad u_2 v_2 \in E_2\}.$$ The cycle space $C(G)$ of a graph $G = (V,E)$ with $p$ vertices, $q$ edges, and $\omega$ (connected) components consists of all subsets of $E$ each of which corresponds to a (possibly empty) subgraph of $G$ whose components are Eulerian graphs. It is known that $C(G)$ is a subspace of the $q$-dimensional vector space over the Galois field $GF(2) = \{0,1\}$ formed (in the usual way) by the subsets of $E$, that $C(G)$ is generated ``by the cycles of $G$'' (i.e. by all subsets of $E$ corresponding to (elementary) cycles of $G)$, and that its dimension is the cyclomatic number $\gamma (G) = q - p + \omega$. A cycle basis of $G$ is a basis of the space $C (G)$ consisting of cycles of $G$. For a cycle basis $B$ of $G$ and an edge $e \in E$, the number of cycles in $B$ containing $e$ is denoted by $f_B(e)$, and $B$ is said to be $k$-fold if $f_B (e) \le k$ for every $e \in E$. The basis number $b(G)$ of $G$ is the smallest integer $k$ such that $G$ has a $k$-fold cycle basis.\par Let $P_m$ denote a path with $m$ vertices, and $W_n$ a wheel with $n$ vertices. Now, the following statements are proved: (1) $b(P_2 \wedge W_n) \le 2$ and therefore, according to a result of {\it S. MacLane} [Fundam. Math. 28, 22-32 (1937; Zbl 0015.37501)], $P_2 \wedge W_n$ is planar for $n \ge 4$; and (2) $b(P_m \wedge W_n) = 3$ (and therefore, $P_m \wedge W_n$ is nonplanar) for all $m \ge 3$ and $n \ge 4$.
[G.Schaar (Freiberg)]

MSC 2000:: *05C99 Graph theory

Keywords: direct product; cycle space; Eulerian graphs; cyclomatic number; cycle basis; basis number; path; wheel

Citations: Zbl 0015.37501

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]