On the basis number of the lexicographic product of two graphs and some related problem
Küçük Resim Yok
Tarih
2009
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Maltepe Üniversitesi
Erişim Hakkı
CC0 1.0 Universal
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Kaynak
International Conference of Mathematical Sciences
WoS Q Değeri
Scopus Q Değeri
Cilt
Sayı
Künye
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.
