On a Generalization of the Bipartite Graph D(k,q)

Abstract: In this paper, we deal with a generalization

G a m m a (O m e g a, q)

of the bipartite graphs

D (k, q)

proposed by Lazebnik and Ustimenko, where

O m e g a

is a set of binary sequences that are adopted to index the entries of the vertices. A few sufficient conditions on

O m e g a

for

G a m m a (O m e g a, q)

to admit a variety of automorphisms are proposed. A sufficient condition for

G a m m a (O m e g a, q)

to be edge-transitive is proposed further. A lower bound of the number of the connected components of

G a m m a (O m e g a, q)

is given by showing some invariants for the components. For

G a m m a (O m e g a, q)

, paths and cycles which contain vertices of some specified form are investigated in details. Some lower bounds for the girth of

G a m m a (O m e g a, q)

are then shown. In particular, one can give very simple conditions on the index set

O m e g a

so as to assure the generalized graphs

G a m m a (O m e g a, q)

to be a family of graphs with large girth.

This page was built for publication: On a Generalization of the Bipartite Graph $D(k,q)$