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

Küçük Resim Yok

2009

## Yayıncı

Maltepe Üniversitesi

## Erişim Hakkı

CC0 1.0 Universal
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.

## Kaynak

International Conference of Mathematical Sciences

## 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.

## Koleksiyon

Maltepe Üniversitesi Kütüphane ve Dokümantasyon Daire Başkanlığı, İstanbul, TÜRKİYE
İçerikte herhangi bir hata görürseniz lütfen bize bildirin