On girth-biregular graphs

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₁, e₂, …, e_k} be the set of edges incident to v ordered such that n(e₁) ≤ n(e₂) ≤ … ≤ n(e_k). Then (n(e₁),n(e₂),…,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 = 2d and signatures (a₁,a₂,…,a_k1) and (b₁,b₂,…,b_k2), and assume without loss of generality that k₁ ≥ k₂. Our first result is that {a₁, a₂, …, a_k1} = {b₁, b₂, …, b_k2}. Our next result is the upper bound a_k1 ≤ M, where M = (k₁−1)^⌊g/4⌋(k₂−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₂ − 1, then ε = 0. Similar result is valid for d = 3, ε ≤ 1 and k₂|̸ k₁.