DSpace Arşivi :: by Yazar "Al-Qeyyam, M. K." değerine göre listeleniyor

Listeleniyor 1 - 1 / 1

On the basis number of the lexicographic product of two graphs and some related problem
(Maltepe Üniversitesi, 2009) Jaradat, M. M. M.; Al-Qeyyam, M. K.
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.