Random Latin square graphs
From MaRDI portal
Cayley graphschromatic numberclique numberconnectivityHamiltonicityindependence numberLatin squaresrandom graphs
Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Eulerian and Hamiltonian graphs (05C45) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)
Abstract: In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case.
Recommendations
- Quasirandom Latin squares
- scientific article; zbMATH DE number 18978
- scientific article; zbMATH DE number 1231233
- scientific article; zbMATH DE number 1540669
- Random Graphs
- scientific article; zbMATH DE number 5610906
- scientific article; zbMATH DE number 3875330
- scientific article; zbMATH DE number 863475
- scientific article; zbMATH DE number 3904630
- scientific article; zbMATH DE number 857026
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Almost all Cayley graphs are hamiltonian
- Almost all Cayley graphs have diameter 2
- Can visibility graphs be represented compactly?
- Concentration of measure and isoperimetric inequalities in product spaces
- Counting sets with small sumset, and the clique number of random Cayley graphs
- Expander graphs and their applications
- Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
- Explicit Concentrators from Generalized N-Gons
- Hamiltonian paths in Cayley graphs
- scientific article; zbMATH DE number 4099367 (Why is no real title available?)
- scientific article; zbMATH DE number 1159719 (Why is no real title available?)
- scientific article; zbMATH DE number 2159656 (Why is no real title available?)
- List coloring of random and pseudo-random graphs
- Quasi-random graphs
- Random Cayley graphs and expanders
- Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
- Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
- Random regular graphs of high degree
- Repeated communication and Ramsey graphs
- Sparse pseudo‐random graphs are Hamiltonian
- The diameters of almost all Cayley digraphs
- The thresholds for diameter 2 in random Cayley graphs
Cited in
(9)- Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups
- The chromatic number of random Cayley graphs
- The range of thresholds for diameter 2 in random Cayley graphs
- The thresholds for diameter 2 in random Cayley graphs
- Random Latin squares and 2-dimensional expanders
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Hamilton cycles in pseudorandom graphs
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Hamilton cycles in pseudorandom graphs (extended abstract)
This page was built for publication: Random Latin square graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909242)
