## On the basis number of the lexicographic product of two graphs and some related problem

#### Citation

Jaradat, M. M. M. ve Al-Qeyyam, M. K. (2009). On the basis number of the lexicographic product of two graphs and some related problem. Maltepe Üniversitesi. s. 246.#### Abstract

For a given graph G, the set E of all subsets of E(G) forms an |E(G)|-dimensional vector space over Z2 with vector
addition X ⊕ Y = (X\Y ) ∪ (Y \X) and scalar multiplication 1.X = X and 0.X = ∅ for all X, Y ∈ E. The cycle space, C(G),
of a graph G is the vector subspace of (E, ⊕, .) spanned by the cycles of G. Traditionally there have been two notions of
minimality among bases of C(G). First, a basis B of G is called a d-fold if each edge of G occurs in at most d cycles of the
basis B. The basis number, b(G), of G is the least non-negative integer d such that C(G) has a d-fold basis; a required basis
of C(G) is a basis for which each edge of G belongs to at most b(G) elements of B. Second, a basis B is called a minimum
cycle basis (MCB) if its total length P
B∈B |B| is minimum among all bases of C(G).
The lexicographic product G[H] has the vertex set V (GρH) = V (G)×V (H) and the edge set E(G[H]) = {(u1, v1)(u2, v2)|u1 =
u2 and v1v2 ∈ H, or u1u2 ∈ G}.
In this work, we give an upper bound of the basis number for the lexicographic product of two graphs. Moreover, in a
related problem, construct a minimum cycle bases for lexicographic product of the same.

#### Source

International Conference of Mathematical Sciences#### Collections

- Makale Koleksiyonu [586]

The following license files are associated with this item: