Random Latin square graphs

DOI10.1002/rsa.20390zbMath1247.05216arXiv1106.0282OpenAlexW2011763375MaRDI QIDQ2909242

Klas Markström, Demetres Christofides

Publication date: 30 August 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Latin squaresrandom graphsCayley graphsindependence numberconnectivitychromatic numberclique numberHamiltonicity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

The thresholds for diameter 2 in random Cayley graphs ⋮ Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ The chromatic number of random Cayley graphs ⋮ The range of thresholds for diameter 2 in random Cayley graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Hamiltonian paths in Cayley graphs
• Can visibility graphs be represented compactly?
• The diameters of almost all Cayley digraphs
• Almost all Cayley graphs have diameter 2
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Concentration of measure and isoperimetric inequalities in product spaces
• List coloring of random and pseudo-random graphs
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Random regular graphs of high degree
• The thresholds for diameter 2 in random Cayley graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Explicit Concentrators from Generalized N-Gons
• Expander graphs and their applications
• Random Cayley graphs and expanders
• Sparse pseudo‐random graphs are Hamiltonian
• Repeated communication and Ramsey graphs
• Almost all Cayley graphs are hamiltonian
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• Quasi-random graphs

This page was built for publication: Random Latin square graphs