A new series of dense graphs of high girth

DOI10.1090/S0273-0979-1995-00569-0zbMath0822.05039arXivmath/9501231MaRDI QIDQ4320744

Andrew J. Woldar, Felix Lazebnik, Vasiliy A. Ustimenko

Publication date: 5 October 1995

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphs; girth; lower bounds; edge-transitive graph; number of edges; dense graphs; degenerate Turán type extremal problem

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C38: Paths and cycles

Related Items

Unnamed Item, Coloring and Covering Nowhere Dense Graphs, Unnamed Item, A Hierarchy of Lower Bounds for Sublinear Additive Spanners, Boundary Properties of Factorial Classes of Graphs, Distributed Spanner Approximation, Graphs with few paths of prescribed length between any two vertices, Keyed hash function from large girth expander graphs, Improved Guarantees for Vertex Sparsification in Planar Graphs, The Impact of Locality in the Broadcast Congested Clique Model, On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2, Unnamed Item, The structure and the number of \(P_7\)-free bipartite graphs, Girth of the algebraic bipartite graph \(D(k,q)\), A randomized construction of high girth regular graphs, On the girth cycles of the bipartite graph \(D(k, q)\), Matroid-constrained vertex cover, On the conjecture for the girth of the bipartite graph \(D(k,q)\), Proof of a conjecture on monomial graphs, On the girth of the bipartite graph \(D(k, q)\), On regular hypergraphs of high girth, Degrees of nonlinearity in forbidden 0-1 matrix problems, Locally bounded coverings and factorial properties of graphs, A tournament approach to pattern avoiding matrices, Boundary properties of graphs for algorithmic graph problems, New results on EX graphs, New families of graphs without short cycles and large size, On an extremal hypergraph problem related to combinatorial batch codes, Recent developments on graphs of bounded clique-width, On the homogeneous algebraic graphs of large girth and their applications, Calculating the extremal number \(ex(v;\{C_3,C_4,\dots,C_n\})\), Minimum cuts, girth and a spectral threshold, Polarities and \(2k\)-cycle-free graphs, Finite fields and Ramanujan graphs, On the connectivity of certain graphs of high girth., Wavelength routing in optical networks of diameter two, Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs, Extremal properties of regular and affine generalized \(m\)-gons as tactical configurations, A characterization of the components of the graphs \(D(k,q)\), On families of graphs of large cycle indicator, matrices of large order and key exchange protocols with nonlinear polynomial maps of small degree, On the comparison of cryptographical properties of two different families of graphs with large cycle indicator, Inverse Turán numbers, Some tight lower bounds for Turán problems via constructions of multi-hypergraphs, New bounds on even cycle creating Hamiltonian paths using expander graphs, On the characterization of some algebraically defined bipartite graphs of girth eight, The cardinality of sets of \(k\)-independent vectors over finite fields, Degree Ramsey numbers for even cycles, On a conjecture of Erdős and Simonovits: even cycles, The implementation of cubic public keys based on a new family of algebraic graphs, On LDPC codes corresponding to affine parts of generalized polygons, Multi-color Ramsey numbers of even cycles, A hierarchy of randomness for graphs, On small world semiplanes with generalised Schubert cells, Covering point-sets with parallel hyperplanes and sparse signal recovery, On the structure of random graphs with constant \(r\)-balls, General properties of some families of graphs defined by systems of equations, Colouring and Covering Nowhere Dense Graphs, On Extremal Graphs with Bounded Girth, On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition, On New Examples of Families of Multivariate Stable Maps and their Cryptographical Applications, ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE, On the girth of random Cayley graphs, Turán problems for integer-weighted graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Lower Bounds for Subgraph Detection in the CONGEST Model, Girth of sparse graphs

Cites Work