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

DOI10.1016/J.DISC.2023.113500MaRDI QIDQ6098087zbMATH OpenOpenAlexFDO

Authors Ming Xu, Xiaoyan Cheng, Yuansheng Tang

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

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