On the girth cycles of the bipartite graph D(k, q)

DOI10.1016/J.DISC.2023.113500zbMATH Open1516.05190arXiv2207.12752OpenAlexW4377018118MaRDI QIDQ6098087FDOQ6098087

Authors: Ming Xu, Xiaoyan Cheng, Yuansheng Tang 

Publication date: 12 June 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For integer $kgeq2$ and prime power $q$, the algebraic bipartite graph $D(k,q)$ proposed by Lazebnik and Ustimenko (1995) is meaningful not only in extremal graph theory but also in coding theory and cryptography. This graph is $q$-regular, edge-transitive and of girth at least $k+4$. For its exact girth $g=g(D(k,q))$, F"{u}redi et al. (1995) conjectured $g=k+5$ for odd $k$ and $qgeq4$. This conjecture was shown to be valid in 2016 when $(k+5)/2$ is the product of an arbitrary factor of $q-1$ and an arbitrary power of the characteristic of $mathbb{F}_q$. In this paper, we determine all the girth cycles of $D(k,q)$ for $3leqkleq5$, $q>3$, and those for $3leqkleq8$, $q=3$.

Full work available at URL: https://arxiv.org/abs/2207.12752

Recommendations

• On the girth of the bipartite graph \(D(k, q)\)
• On the conjecture for the girth of the bipartite graph \(D(k,q)\)
• On the characterization of some algebraically defined bipartite graphs of girth eight
• A characterization of the components of the graphs \(D(k,q)\)
• New constructions of bipartite graphs on \(m\), \(n\) vertices with many edges and without small cycles

zbMATH Keywords

bipartite graphcyclegirthedge-transitivebacktrackless walk

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• New examples of graphs without small cycles and of large size
• On monomial graphs of girth eight
• Explicit Construction of Families of LDPC Codes With No<tex>$4$</tex>-Cycles
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• On the homogeneous algebraic graphs of large girth and their applications
• New upper bounds on the order of cages
• On the connectivity of certain graphs of high girth.
• Extremal properties of regular and affine generalized \(m\)-gons as tactical configurations
• Explicit construction of graphs with an arbitrary large girth and of large size
• Graphs of prescribed girth and bi-degree
• A characterization of the components of the graphs \(D(k,q)\)
• On small world semiplanes with generalised Schubert cells
• General properties of some families of graphs defined by systems of equations
• On the conjecture for the girth of the bipartite graph \(D(k,q)\)
• On the girth of the bipartite graph \(D(k, q)\)
• A new series of dense graphs of high girth
• An infinite series of regular edge- but not vertex-transitive graphs
• Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey

Cited In (6)

• The number of cycles in the square bipartite graphs \(B_{m\times n}\)
• On the conjecture for the girth of the bipartite graph \(D(k,q)\)
• On the girth of the bipartite graph \(D(k, q)\)
• Girth of the algebraic bipartite graph \(D(k,q)\)
• A characterization of the components of the graphs \(D(k,q)\)
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles

This page was built for publication: On the girth cycles of the bipartite graph \(D(k, q)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098087)