26:
240:
with parameters (81, 20, 1, 6). This means that it has 81 vertices, 20 edges per vertex, 1 triangle per edge, and 6 length-two paths connecting each non-adjacent pair of distinct vertices. As a strongly regular graph with the third parameter equal to 1, the
Brouwer–Haemers graph
443:
490:; a 9-coloring of this graph describes a solved Sudoku puzzle. In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.
685:
480:
312:
222:
570:; Haemers, W. H. (1992), "Structure and uniqueness of the (81,20,1,6) strongly regular graph", A collection of contributions in honour of Jack van Lint,
741:
Gago-Vargas, Jesús; Hartillo-Hermoso, Maria Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), "Sudokus and Gröbner bases: Not only a
456:
puzzles by making a vertex for each square of the puzzle and connecting two squares by an edge when they belong to the same row, column, or
324:
793:
747:
Computer
Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings
134:
272:
and Willem H. Haemers, who in 1992 published a proof that it is the only strongly regular graph with the same parameters.
185:
The
Brouwer–Haemers graph has several related algebraic constructions. One of the simplest is as a degree-4 generalized
264:
Although
Brouwer writes that this graph's "construction is folklore", and cites as an early reference a 1964 paper on
830:
689:
246:
825:
253:
166:
114:
661:
Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with
63:
53:
664:
459:
291:
237:
162:
109:
483:
33:
195:
806:
720:
620:
587:
242:
124:
73:
640:
514:
321:, it is one of only three possible strongly regular graphs whose parameters have the form
8:
43:
724:
698:
601:
545:
83:
785:
740:
777:
637:
579:
728:
758:
750:
708:
575:
158:
93:
245:. Finding large dense graphs with this property is one of the formulations of the
802:
749:, Lecture Notes in Computer Science, vol. 4194, Springer, pp. 155–165,
716:
616:
583:
567:
510:
314:
281:
269:
174:
170:
119:
712:
487:
241:
has the property that every edge belongs to a unique triangle; that is, it is
177:
and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.
819:
155:
781:
452:, a different 20-regular 81-vertex graph. The Sudoku graph is derived from
449:
265:
225:
190:
147:
318:
285:
186:
143:
754:
745:", in Ganzha, Victor G.; Mayr, Ernst W.; Vorozhtsov, Evgenii V. (eds.),
25:
763:
600:
Clark, L. H.; Entringer, R. C.; McCanna, J. E.; Székely, L. A. (1991),
438:{\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}
645:
550:
703:
280:
The
Brouwer–Haemers graph is the first in an infinite family of
453:
189:: it can be defined by making a vertex for each element in the
635:
599:
173:. Although its construction is folklore, it was named after
542:
The spectra of generalized Paley graphs and applications
667:
462:
327:
294:
198:
224:
and an edge for every two elements that differ by a
660:
679:
602:"Extremal problems for local properties of graphs"
474:
437:
306:
216:
817:
566:
540:Podestá, Ricardo A.; Videla, Denis E. (2018),
288:over fields of characteristic three. With the
776:
539:
430:
330:
794:Notices of the American Mathematical Society
786:"Sudoku squares and chromatic polynomials"
482:block of the puzzle. It has many 9-vertex
252:As well as being strongly regular it is a
762:
702:
609:The Australasian Journal of Combinatorics
549:
236:The Brouwer–Haemers graph is the unique
161:with 81 vertices and 810 edges. It is a
818:
636:
268:by Dale M. Mesner, it is named after
631:
629:
562:
560:
535:
533:
448:It should be distinguished from the
734:
593:
509:
505:
503:
13:
14:
842:
770:
654:
626:
557:
530:
275:
500:
24:
690:Journal of Combinatorial Theory
180:
519:Descriptions of various graphs
425:
413:
398:
386:
364:
335:
211:
205:
135:Table of graphs and parameters
1:
493:
486:and requires 9 colors in any
231:
580:10.1016/0012-365X(92)90532-K
7:
152:Brouwer–Haemers graph
19:Brouwer–Haemers graph
10:
847:
713:10.1016/j.jctb.2013.05.005
680:{\displaystyle \lambda =1}
259:
475:{\displaystyle 3\times 3}
307:{\displaystyle 3\times 3}
254:distance-transitive graph
167:distance-transitive graph
133:
102:
92:
82:
72:
62:
52:
42:
32:
23:
18:
831:Strongly regular graphs
641:"Brouwer–Haemers Graph"
515:"Brouwer–Haemers graph"
284:defined as generalized
247:Ruzsa–Szemerédi problem
681:
476:
439:
308:
238:strongly regular graph
218:
217:{\displaystyle GF(81)}
163:strongly regular graph
682:
477:
440:
309:
219:
665:
572:Discrete Mathematics
460:
325:
292:
196:
755:10.1007/11870814_13
115:distance-transitive
778:Herzberg, Agnes M.
677:
638:Weisstein, Eric W.
574:, 106/107: 77–82,
472:
435:
304:
214:
826:Individual graphs
140:
139:
838:
810:
809:
790:
774:
768:
767:
766:
738:
732:
731:
706:
686:
684:
683:
678:
658:
652:
651:
650:
633:
624:
623:
606:
597:
591:
590:
564:
555:
554:
553:
537:
528:
527:
526:
525:
511:Brouwer, Andries
507:
481:
479:
478:
473:
444:
442:
441:
436:
434:
433:
385:
384:
372:
371:
347:
346:
334:
333:
313:
311:
310:
305:
282:Ramanujan graphs
223:
221:
220:
215:
159:undirected graph
110:strongly regular
94:Chromatic number
28:
16:
15:
846:
845:
841:
840:
839:
837:
836:
835:
816:
815:
814:
813:
788:
775:
771:
739:
735:
666:
663:
662:
659:
655:
634:
627:
604:
598:
594:
565:
558:
538:
531:
523:
521:
508:
501:
496:
461:
458:
457:
429:
428:
380:
376:
367:
363:
342:
338:
329:
328:
326:
323:
322:
293:
290:
289:
278:
270:Andries Brouwer
262:
234:
197:
194:
193:
183:
175:Andries Brouwer
171:Ramanujan graph
129:
12:
11:
5:
844:
834:
833:
828:
812:
811:
801:(6): 708–717,
769:
733:
697:(4): 521–531,
676:
673:
670:
653:
625:
592:
568:Brouwer, A. E.
556:
529:
498:
497:
495:
492:
488:graph coloring
471:
468:
465:
432:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
383:
379:
375:
370:
366:
362:
359:
356:
353:
350:
345:
341:
337:
332:
303:
300:
297:
277:
276:Related graphs
274:
261:
258:
243:locally linear
233:
230:
213:
210:
207:
204:
201:
182:
179:
138:
137:
131:
130:
128:
127:
125:locally linear
122:
117:
112:
106:
104:
100:
99:
96:
90:
89:
86:
80:
79:
76:
70:
69:
66:
60:
59:
56:
50:
49:
46:
40:
39:
36:
30:
29:
21:
20:
9:
6:
4:
3:
2:
843:
832:
829:
827:
824:
823:
821:
808:
804:
800:
796:
795:
787:
783:
782:Murty, M. Ram
779:
773:
765:
760:
756:
752:
748:
744:
737:
730:
726:
722:
718:
714:
710:
705:
700:
696:
692:
691:
674:
671:
668:
657:
648:
647:
642:
639:
632:
630:
622:
618:
614:
610:
603:
596:
589:
585:
581:
577:
573:
569:
563:
561:
552:
547:
543:
536:
534:
520:
516:
512:
506:
504:
499:
491:
489:
485:
469:
466:
463:
455:
451:
446:
422:
419:
416:
410:
407:
404:
401:
395:
392:
389:
381:
377:
373:
368:
360:
357:
354:
351:
348:
343:
339:
320:
316:
301:
298:
295:
287:
283:
273:
271:
267:
266:Latin squares
257:
255:
250:
248:
244:
239:
229:
227:
208:
202:
199:
192:
188:
178:
176:
172:
168:
164:
160:
157:
153:
149:
145:
136:
132:
126:
123:
121:
118:
116:
113:
111:
108:
107:
105:
101:
97:
95:
91:
87:
85:
84:Automorphisms
81:
77:
75:
71:
67:
65:
61:
57:
55:
51:
47:
45:
41:
37:
35:
31:
27:
22:
17:
798:
792:
772:
746:
743:divertimento
742:
736:
694:
693:, Series B,
688:
656:
644:
612:
608:
595:
571:
541:
522:, retrieved
518:
450:Sudoku graph
447:
315:Rook's graph
286:Paley graphs
279:
263:
251:
235:
226:fourth power
191:finite field
184:
181:Construction
151:
148:graph theory
144:mathematical
141:
764:11441/23605
319:Games graph
187:Paley graph
820:Categories
551:1812.03332
524:2019-02-11
494:References
232:Properties
103:Properties
704:1201.0383
669:λ
646:MathWorld
615:: 25–31,
467:×
358:−
299:×
146:field of
120:Ramanujan
784:(2007),
729:19220680
317:and the
169:, and a
154:is a 20-
64:Diameter
34:Vertices
807:2327972
721:3071380
621:1129266
588:1181899
484:cliques
260:History
156:regular
142:In the
88:233,280
805:
727:
719:
619:
586:
454:Sudoku
150:, the
54:Radius
789:(PDF)
725:S2CID
699:arXiv
605:(PDF)
546:arXiv
74:Girth
44:Edges
165:, a
759:hdl
751:doi
709:doi
695:103
687:",
576:doi
48:810
822::
803:MR
799:54
797:,
791:,
780:;
757:,
723:,
717:MR
715:,
707:,
643:.
628:^
617:MR
611:,
607:,
584:MR
582:,
559:^
544:,
532:^
517:,
513:,
502:^
445:.
256:.
249:.
228:.
209:81
38:81
761::
753::
711::
701::
675:1
672:=
649:.
613:4
578::
548::
470:3
464:3
431:)
426:)
423:1
420:+
417:n
414:(
411:n
408:,
405:1
402:,
399:)
396:3
393:+
390:n
387:(
382:2
378:n
374:,
369:2
365:)
361:1
355:n
352:3
349:+
344:2
340:n
336:(
331:(
302:3
296:3
212:)
206:(
203:F
200:G
98:7
78:3
68:2
58:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
