On girth-biregular graphs

Authors

  • Gyorgy Kiss Eotvos Lorand University, Hungary and University of Primorska, Slovenia
  • Štefko Miklavič University of Primorska, Slovenia
  • Tamás Szőnyi Eotvos Lorand University, Hungary and University of Primorska, Slovenia

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 {e1, e2, …, ek} be the set of edges incident to v ordered such that n(e1) ≤ n(e2) ≤ … ≤ n(ek). Then (n(e1),n(e2),…,n(ek)) 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 (a1,a2,…,ak1) and (b1,b2,…,bk2), and assume without loss of generality that k1 ≥ k2. Our first result is that {a1, a2, …, ak1} = {b1, b2, …, bk2}. Our next result is the upper bound ak1 ≤ M, where M = (k1−1)g/4⌋(k2−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 ak1 = M − ε for some non-negative integer ε < k2 − 1, then ε = 0. Similar result is valid for d = 3, ε ≤ 1 and k2k1.

Downloads

Published

2022-11-22

Issue

Section

Articles