Paleyjev graf
| Paleyjev graf | |
|---|---|
 Paleyjev graf reda 13 | |
| Ime | Raymond Paley |
| Točke | q ≡ 1 mod 4, q je praštevilska potenca |
| Povezave | q(q − 1)/4 |
| Značilnosti | krepkoregularen konferenčen sebikomplementaren |
| Označba | |
Paleyjevi grafi so v teoriji grafov gosti neusmerjeni grafi skonstruirani iz članov primernega končnega obsega s povezovanjem parov elementov, ki se razlikujejo v kvadratnem ostanku. Imenujejo se po angleškem matematiku Raymondu Paleyju. Paleyjevi grafi tvorijo neskončno družino konferenčnih grafov, kar vodi do neskončne množice simetričnih konferenčnih matrik. Paleyjevi grafi omogočajo rabo orodij iz teorije grafov pri raziskovanju teorije števil kvadratnih ostankov in imajo zanimive značilnosti, tako da so v teoriji grafov uporabni splošneje.
Paleyjevi grafi so v tesni povezavi s Payleyjevo konstrukcijo za konstruiranje Hadamardovih matrik iz kvadratnih ostankov.[1] Kot grafe so jih neodvisno vpeljali Horst Sachs leta 1962 ter Paul Erdős in Alfréd Rényi leta 1963.[2][3] Sachs se je zanimal zanje zaradi njihove sebi komplementarnosti, Erdős in Rényi pa sta raziskovala njihove simetrije.
Sklici
[uredi | uredi kodo]Viri
[uredi | uredi kodo]- Erdős, Paul; Rényi, Alfréd (1963). »Asymmetric graphs«. Acta Mathematica Academiae Scientiarum Hungaricae. Zv. 14. str. 295–315. doi:10.1007/BF01895716. .
- Paley, Raymond (1933). »On orthogonal matrices«. J. Math. Phys. Zv. 12. str. 311–320.
- Sachs, Horst (1962). »Über selbstkomplementäre Graphen«. Publicationes Mathematicae Debrecen. Zv. 9. str. 270–288. .
