A new series of dense graphs of high girth
From MaRDI portal
Publication:4320744
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
bipartite graphsgirthlower boundsedge-transitive graphnumber of edgesdense graphsdegenerate Turán type extremal problem
Related Items
On the conjecture for the girth of the bipartite graph \(D(k,q)\) ⋮ The cardinality of sets of \(k\)-independent vectors over finite fields ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ On small world semiplanes with generalised Schubert cells ⋮ Unnamed Item ⋮ Finite fields and Ramanujan graphs ⋮ Proof of a conjecture on monomial graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ A characterization of the components of the graphs \(D(k,q)\) ⋮ Degree Ramsey numbers for even cycles ⋮ On the girth of the bipartite graph \(D(k, q)\) ⋮ Girth of the algebraic bipartite graph \(D(k,q)\) ⋮ A randomized construction of high girth regular graphs ⋮ On regular hypergraphs of high girth ⋮ On the girth cycles of the bipartite graph \(D(k, q)\) ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Locally bounded coverings and factorial properties of graphs ⋮ Improved lower bounds for multiplicative square-free sequences ⋮ On sparse parity check matrices (extended abstract) ⋮ New results on EX graphs ⋮ On the eigenvalues of the graphs \(D(5,q)\) ⋮ Graphs with few paths of prescribed length between any two vertices ⋮ On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition ⋮ On New Examples of Families of Multivariate Stable Maps and their Cryptographical Applications ⋮ Matroid-constrained vertex cover ⋮ Unnamed Item ⋮ Some tight lower bounds for Turán problems via constructions of multi-hypergraphs ⋮ Covering point-sets with parallel hyperplanes and sparse signal recovery ⋮ On new protocols of Noncommutative Cryptography in terms of homomorphism of stable multivariate transformation groups ⋮ Extremal numbers of hypergraph suspensions of even cycles ⋮ On the structure of random graphs with constant \(r\)-balls ⋮ 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 ⋮ ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE ⋮ On a conjecture of Erdős and Simonovits: even cycles ⋮ Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs ⋮ The implementation of cubic public keys based on a new family of algebraic graphs ⋮ On LDPC codes corresponding to affine parts of generalized polygons ⋮ On the connectivity of certain graphs of high girth. ⋮ New bounds on even cycle creating Hamiltonian paths using expander graphs ⋮ Unnamed Item ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ On the characterization of some algebraically defined bipartite graphs of girth eight ⋮ On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2 ⋮ A tournament approach to pattern avoiding matrices ⋮ Keyed hash function from large girth expander graphs ⋮ General properties of some families of graphs defined by systems of equations ⋮ Recent developments on graphs of bounded clique-width ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ New families of graphs without short cycles and large size ⋮ On the girth of random Cayley graphs ⋮ The structure and the number of \(P_7\)-free bipartite graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ On the homogeneous algebraic graphs of large girth and their applications ⋮ Multi-color Ramsey numbers of even cycles ⋮ On an extremal hypergraph problem related to combinatorial batch codes ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ Calculating the extremal number \(ex(v;\{C_3,C_4,\dots,C_n\})\) ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ Minimum cuts, girth and a spectral threshold ⋮ Girth of sparse graphs ⋮ Distributed Spanner Approximation ⋮ Polarities and \(2k\)-cycle-free graphs ⋮ On Extremal Graphs with Bounded Girth ⋮ A hierarchy of randomness for graphs ⋮ Inverse Turán numbers ⋮ Extremal properties of regular and affine generalized \(m\)-gons as tactical configurations ⋮ Turán problems for integer-weighted graphs ⋮ Wavelength routing in optical networks of diameter two
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Explicit construction of regular graphs without small cycles
- A linear interpretation of the flag geometries of Chevalley groups
- 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
- Properties of certain families of \(2k\)-cycle-free graphs
- New examples of graphs without small cycles and of large size
- Cycles of even length in graphs
- Explicit construction of graphs with an arbitrary large girth and of large size
- Graphs of prescribed girth and bi-degree
- Minimal Regular Graphs of Girths Eight and Twelve
This page was built for publication: A new series of dense graphs of high girth
