Explicit construction of graphs with an arbitrary large girth and of large size

DOI10.1016/0166-218X(94)00058-LzbMath0840.05045MaRDI QIDQ1894370

Vasiliy A. Ustimenko, Felix Lazebnik

Publication date: 6 September 1995

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

zbMATH Keywords

coveringincidence graphsLie algebrasgirthvertex-transitiveincidence systemChevalley group geometriesflag-transitive semiplane

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Other designs, configurations (05B30) Distance in graphs (05C12) Other finite incidence structures (geometric aspects) (51E30)

Related Items (56)

On Even-Degree Subgraphs of Linear Hypergraphs ⋮ Dirac-type theorems in random hypergraphs ⋮ On the conjecture for the girth of the bipartite graph \(D(k,q)\) ⋮ Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles ⋮ The eigenvalues of the graphs \(D(4,q)\) ⋮ New small regular graphs of girth 5 ⋮ Mean-field conditions for percolation on finite graphs ⋮ Recent Developments in Low-Density Parity-Check Codes ⋮ A characterization of the components of the graphs \(D(k,q)\) ⋮ On the girth of the bipartite graph \(D(k, q)\) ⋮ Girth of the algebraic bipartite graph \(D(k,q)\) ⋮ On the spectrum of Wenger graphs ⋮ A simple proof for the lower bound of the girth of graphs \(D(n,q)\) ⋮ A new series of dense graphs of high girth ⋮ On the girth cycles of the bipartite graph \(D(k, q)\) ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ On the eigenvalues of the graphs \(D(5,q)\) ⋮ Graphs with few paths of prescribed length between any two vertices ⋮ Digraph redicolouring ⋮ On New Examples of Families of Multivariate Stable Maps and their Cryptographical Applications ⋮ Turán problems for \(k\)-geodetic digraphs ⋮ Covering point-sets with parallel hyperplanes and sparse signal recovery ⋮ Unnamed Item ⋮ Extremal numbers of hypergraph suspensions of even cycles ⋮ On the comparison of cryptographical properties of two different families of graphs with large cycle indicator ⋮ A Bound on the Number of Edges in Graphs Without an Even Cycle ⋮ Families of small regular graphs of girth 5 ⋮ On the key expansion of \(D(n, K)\)-based cryptographical algorithm ⋮ On LDPC codes corresponding to affine parts of generalized polygons ⋮ Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography ⋮ On the connectivity of certain graphs of high girth. ⋮ Regular graphs of large girth and arbitrary degree ⋮ Spectral and combinatorial properties of some algebraically defined graphs ⋮ Counting polynomials with distinct zeros in finite fields ⋮ On some cycles in Wenger graphs ⋮ LDPC Codes Based on Algebraic Graphs ⋮ A note on the spectrum of linearized Wenger graphs ⋮ Keyed hash function from large girth expander graphs ⋮ Eigenvalues and expansion of bipartite graphs ⋮ General properties of some families of graphs defined by systems of equations ⋮ Obstructions for three-coloring graphs without induced paths on six vertices ⋮ Role colouring graphs in hereditary classes ⋮ Small regular graphs of girth 7 ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ Linear representations of finite geometries and associated LDPC codes ⋮ The dimensions of \(LU(3,q)\) codes ⋮ Extremal Numbers of Cycles Revisited ⋮ Girth of sparse graphs ⋮ LDPC codes constructed from cubic symmetric graphs ⋮ Polarities and \(2k\)-cycle-free graphs ⋮ A note on the Turán function of even cycles ⋮ On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree ⋮ Semisymmetric graphs defined by finite-dimensional generalized Kac-Moody algebras ⋮ Linearized Wenger graphs ⋮ Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs ⋮ Extremal properties of regular and affine generalized \(m\)-gons as tactical configurations

Cites Work

• Explicit construction of regular graphs without small cycles
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Note on the girth of Ramanujan graphs
• On a class of degenerate extremal graph problems
• The sextet construction for cubic graphs
• Girths of bipartite sextet graphs
• Ramanujan graphs
• Explicit constructions of graphs without short cycles and low density codes
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• New examples of graphs without small cycles and of large size
• Cycles of even length in graphs
• Minimal Regular Graphs of Girths Eight and Twelve
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Explicit construction of graphs with an arbitrary large girth and of large size