Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

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

Highlights
Master Server