# On girth-biregular graphs

## DOI:

https://doi.org/10.26493/1855-3974.2935.a7b## Keywords:

girth cycle, girth-biregular graph## Abstract

Let *Γ* denote a finite, connected, simple graph. For an edge *e* of *Γ* let *n*(*e*) denote the number of girth cycles containing *e*. For a vertex *v* of *Γ* let {*e*_{1}, *e*_{2}, …, *e*_{k}} be the set of edges incident to *v* ordered such that *n*(*e*_{1}) ≤ *n*(*e*_{2}) ≤ … ≤ *n*(*e*_{k}). Then (*n*(*e*_{1}),*n*(*e*_{2}),…,*n*(*e*_{k})) is called the *signature* of *v*. The graph *Γ* is said to be *girth-biregular* if it is bipartite, and all of its vertices belonging to the same bipartition have the same signature.

Let *Γ* be a girth-biregular graph with girth *g* = 2*d* and signatures (*a*_{1},*a*_{2},…,*a*_{k1}) and (*b*_{1},*b*_{2},…,*b*_{k2}), and assume without loss of generality that *k*_{1} ≥ *k*_{2}. Our first result is that {*a*_{1}, *a*_{2}, …, *a*_{k1}} = {*b*_{1}, *b*_{2}, …, *b*_{k2}}. Our next result is the upper bound *a*_{k1} ≤ *M*, where *M* = (*k*_{1}−1)^{⌊g/4⌋}(*k*_{2}−1)^{⌈g/4⌉}. We describe the graphs attaining equality. For *d* = 3 or *d* ≥ 4 even they are incidence graphs of Steiner systems and generalized polygons, respectively. Finally, we show that when *d* is even and *a*_{k1} = *M* − *ε* for some non-negative integer *ε* < *k*_{2} − 1, then *ε* = 0. Similar result is valid for *d* = 3, *ε* ≤ 1 and *k*_{2}*|̸* *k*_{1}.

## Downloads

## Published

## Issue

## Section

## License

Articles in this journal are published under Creative Commons Attribution 4.0 International License

https://creativecommons.org/licenses/by/4.0/