A simple proof for the lower bound of the girth of graphs D(n,q)

DOI10.1016/J.DISC.2023.113705MaRDI QIDQ6080170zbMATH OpenOpenAlexFDO

Authors Vladislav Taranchuk

Publication date 30 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algebraically defined graphshigh girthTurán numbers

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: The components of the graphs $D(n,q)$ provide the best-known general lower bound for the number of edges in a graph with $n$ vertices and no cycles of length less than $g$. In this paper, we give a new, short, and simpler proof of the fact that the length of the shortest cycle appearing in $D(n,q)$ is $n+5$ when $n$ is odd, and $n+4$ when $n$ is even.

Recommendations

• The number of cycle lengths in graphs of given minimum degree and girth
• Exact values of girth for some graphs D(k,q) and upper bounds of the order of cages
• On the connectivity of certain graphs of high girth.
• scientific article; zbMATH DE number 2187690
• Maximal cycles in graphs of large girth

Cites work

• A characterization of the components of the graphs \(D(k,q)\)
• Cycles of even length in graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit construction of graphs with an arbitrary large girth and of large size
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• General properties of some families of graphs defined by systems of equations
• Graphs of prescribed girth and bi-degree
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• On extremal graph theory and symbolic computations
• 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 spectrum of Wenger graphs
• Ramanujan graphs
• Recent Developments in Low-Density Parity-Check Codes
• Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey
• The eigenvalues of the graphs \(D(4,q)\)
• The Moore bound for irregular graphs

This page was built for publication: A simple proof for the lower bound of the girth of graphs \(D(n,q)\)

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