On girth-biregular graphs

Gyorgy Kiss ; Štefko Miklavič ; Tamás Szőnyi

Ars Mathematica Contemporanea, Tome 23 (2023) no. 4, article no. 01, 22 p.

Résumé

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 k2|̸ k1.

Détail

DOI : 10.26493/1855-3974.2935.a7b

Keywords: Girth cycle, girth-biregular graph, Steiner system, generalized polygons