675:
691:
659:
703:
643:
29:
273:
356:
610:
472:) for which the strong regularity parameters do not determine that graph uniquely but are shared with a different graph, namely the Shrikhande graph (which is not a rook's graph).
424:
525:
of the
Shrikhande graph is of order 192. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Shrikhande graph is a
674:
658:
690:
175:
897:
943:
642:
807:
702:
234:
917:
476:
278:
219: 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.
933:
889:
500:
533:
511:
503:
in the torus, with 32 triangular faces. The skeleton of the dual of this map (as embedded in the torus) is the
488:
452:
539:
938:
196:
79:
69:
515:
391:
204:
152:
617:
216:
208:
49:
913:
397:
89:
212:
59:
883:
785:
522:
99:
893:
732:
709:
156:
775:
759:
665:
200:
109:
42:
833:
681:
526:
433:. The Shrikhande graph shares these parameters with exactly one other graph, the 4×4
160:
129:
119:
434:
836:
28:
649:
624:
613:
496:
168:
164:
927:
816:
735:
495:
in which each vertex is surrounded by six triangles. Thus, the
Shrikhande graph is a
803:
628:
228:
188:
139:
480:
184:
483:
of six vertices. As with any locally cyclic graph, the
Shrikhande graph is the
780:
504:
484:
438:
740:
427:
491:
of some surface; in the case of the
Shrikhande graph, this surface is a
789:
492:
374:
have two distinct neighbors in common (excluding the two vertices
275:. Two vertices are adjacent if and only if the difference is in
430:
426:. This equality implies that the graph is associated with a
815:, Massachusetts: Addison-Wesley, p. 79, archived from
268:{\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4}}
853:, New York: Springer-Verlag, pp. 104–105 and 136
542:
400:
281:
237:
849:Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989),
148:
138:
128:
118:
108:
98:
88:
78:
68:
58:
48:
38:
21:
604:
418:
350:
267:
351:{\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\}}
479:; that is, the neighbors of each vertex form a
868:. Master Thesis, University of Tübingen, 2018
382:themselves), which holds true whether or not
227:The Shrikhande graph can be constructed as a
16:Undirected graph named after S. S. Shrikhande
8:
345:
282:
461:. The latter graph is the only line graph
394:and its parameters are: {16,6,2,2}, i.e.,
366:In the Shrikhande graph, any two vertices
779:
696:The Shrikhande graph drawn symmetrically.
596:
574:
541:
399:
280:
259:
255:
254:
244:
240:
239:
236:
612:. Therefore, the Shrikhande graph is an
723:
638:
605:{\displaystyle (x-6)(x-2)^{6}(x+2)^{9}}
18:
754:
752:
7:
882:Holton, D. A.; Sheehan, J. (1993),
866:Engineering Linear Layouts with SAT
684:of the Shrikhande graph is 6.
668:of the Shrikhande graph is 4.
536:of the Shrikhande graph is :
14:
768:Annals of Mathematical Statistics
518:that is not distance-transitive.
762:(1959), "The uniqueness of the L
701:
689:
673:
657:
641:
27:
620:consists entirely of integers.
419:{\displaystyle \lambda =\mu =2}
593:
580:
571:
558:
555:
543:
510:The Shrikhande graph is not a
342:
330:
321:
309:
300:
288:
176:Table of graphs and parameters
1:
507:, a cubic symmetric graph.
960:
890:Cambridge University Press
648:The Shrikhande graph is a
215:, with each vertex having
534:characteristic polynomial
512:distance-transitive graph
174:
26:
708:The Shrikhande graph is
499:. The embedding forms a
475:The Shrikhande graph is
453:complete bipartite graph
390:. In other words, it is
944:Strongly regular graphs
851:Distance-Regular Graphs
806:(1972), "Theorem 8.7",
781:10.1214/aoms/1177706207
606:
516:distance-regular graph
420:
352:
269:
205:strongly regular graph
766:association scheme",
607:
514:. It is the smallest
489:Whitney triangulation
421:
353:
270:
231:. The vertex set is
914:The Shrikhande Graph
540:
398:
279:
235:
33:The Shrikhande graph
822:on November 9, 2013
885:The Petersen Graph
736:"Shrikhande Graph"
733:Weisstein, Eric W.
602:
523:automorphism group
416:
348:
265:
934:Individual graphs
760:Shrikhande, S. S.
477:locally hexagonal
203:in 1959. It is a
181:
180:
951:
902:
869:
862:
856:
854:
846:
840:
837:Shrikhande graph
831:
825:
823:
821:
814:
800:
794:
792:
783:
756:
747:
746:
745:
728:
705:
693:
677:
666:chromatic number
661:
645:
611:
609:
608:
603:
601:
600:
579:
578:
425:
423:
422:
417:
392:strongly regular
357:
355:
354:
349:
274:
272:
271:
266:
264:
263:
258:
249:
248:
243:
201:S. S. Shrikhande
193:Shrikhande graph
153:Strongly regular
110:Chromatic number
43:S. S. Shrikhande
31:
22:Shrikhande graph
19:
959:
958:
954:
953:
952:
950:
949:
948:
924:
923:
910:
900:
892:, p. 270,
881:
878:
873:
872:
863:
859:
848:
847:
843:
832:
828:
819:
812:
802:
801:
797:
765:
758:
757:
750:
731:
730:
729:
725:
720:
713:
706:
697:
694:
685:
682:chromatic index
678:
669:
662:
653:
646:
637:
592:
570:
538:
537:
527:symmetric graph
470:
460:
450:
396:
395:
386:is adjacent to
364:
277:
276:
253:
238:
233:
232:
225:
167:
163:
159:
155:
120:Chromatic index
34:
17:
12:
11:
5:
957:
955:
947:
946:
941:
939:Regular graphs
936:
926:
925:
922:
921:
920:, August 2010.
909:
908:External links
906:
905:
904:
898:
877:
874:
871:
870:
864:Jessica Wolz,
857:
841:
834:Brouwer, A. E.
826:
795:
763:
748:
722:
721:
719:
716:
715:
714:
707:
700:
698:
695:
688:
686:
679:
672:
670:
663:
656:
654:
650:toroidal graph
647:
640:
636:
633:
625:book thickness
614:integral graph
599:
595:
591:
588:
585:
582:
577:
573:
569:
566:
563:
560:
557:
554:
551:
548:
545:
497:toroidal graph
468:
458:
448:
415:
412:
409:
406:
403:
363:
360:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
262:
257:
252:
247:
242:
224:
221:
199:discovered by
179:
178:
172:
171:
150:
146:
145:
142:
136:
135:
132:
130:Book thickness
126:
125:
122:
116:
115:
112:
106:
105:
102:
96:
95:
92:
86:
85:
82:
76:
75:
72:
66:
65:
62:
56:
55:
52:
46:
45:
40:
36:
35:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
956:
945:
942:
940:
937:
935:
932:
931:
929:
919:
918:Peter Cameron
915:
912:
911:
907:
901:
899:0-521-43594-3
895:
891:
887:
886:
880:
879:
875:
867:
861:
858:
852:
845:
842:
838:
835:
830:
827:
818:
811:
810:
805:
799:
796:
791:
787:
782:
777:
773:
769:
761:
755:
753:
749:
743:
742:
737:
734:
727:
724:
717:
711:
704:
699:
692:
687:
683:
676:
671:
667:
660:
655:
651:
644:
639:
634:
632:
630:
626:
621:
619:
615:
597:
589:
586:
583:
575:
567:
564:
561:
552:
549:
546:
535:
530:
528:
524:
519:
517:
513:
508:
506:
502:
498:
494:
490:
486:
482:
478:
473:
471:
464:
457:
454:
447:
443:
440:
436:
432:
429:
413:
410:
407:
404:
401:
393:
389:
385:
381:
377:
373:
369:
361:
359:
339:
336:
333:
327:
324:
318:
315:
312:
306:
303:
297:
294:
291:
285:
260:
250:
245:
230:
222:
220:
218:
214:
210:
206:
202:
198:
194:
190:
186:
177:
173:
170:
166:
162:
158:
154:
151:
147:
143:
141:
137:
133:
131:
127:
123:
121:
117:
113:
111:
107:
103:
101:
100:Automorphisms
97:
93:
91:
87:
83:
81:
77:
73:
71:
67:
63:
61:
57:
53:
51:
47:
44:
41:
37:
30:
25:
20:
884:
865:
860:
850:
844:
829:
817:the original
809:Graph Theory
808:
798:
771:
767:
739:
726:
629:queue number
622:
531:
520:
509:
474:
466:
462:
455:
445:
441:
437:, i.e., the
435:rook's graph
387:
383:
379:
375:
371:
367:
365:
229:Cayley graph
226:
223:Construction
192:
189:graph theory
185:mathematical
182:
140:Queue number
774:: 781–798,
710:Hamiltonian
501:regular map
157:Hamiltonian
39:Named after
928:Categories
876:References
804:Harary, F.
505:Dyck graph
485:1-skeleton
439:line graph
362:Properties
149:Properties
741:MathWorld
565:−
550:−
451:) of the
428:symmetric
408:μ
402:λ
328:±
307:±
286:±
251:×
187:field of
161:Symmetric
618:spectrum
209:vertices
207:with 16
169:Integral
165:Eulerian
80:Diameter
50:Vertices
790:2237417
635:Gallery
623:It has
211:and 48
183:In the
896:
788:
627:4 and
616:: its
217:degree
191:, the
70:Radius
820:(PDF)
813:(PDF)
786:JSTOR
718:Notes
493:torus
487:of a
481:cycle
213:edges
197:graph
195:is a
90:Girth
60:Edges
894:ISBN
680:The
664:The
532:The
521:The
431:BIBD
378:and
370:and
776:doi
631:3.
469:n,n
459:4,4
449:4,4
104:192
930::
916:,
888:,
784:,
772:30
770:,
751:^
738:.
529:.
358:.
64:48
54:16
903:.
855:.
839:.
824:.
793:.
778::
764:2
744:.
712:.
652:.
598:9
594:)
590:2
587:+
584:x
581:(
576:6
572:)
568:2
562:x
559:(
556:)
553:6
547:x
544:(
467:K
465:(
463:L
456:K
446:K
444:(
442:L
414:2
411:=
405:=
388:J
384:I
380:J
376:I
372:J
368:I
346:}
343:)
340:1
337:,
334:1
331:(
325:,
322:)
319:1
316:,
313:0
310:(
304:,
301:)
298:0
295:,
292:1
289:(
283:{
261:4
256:Z
246:4
241:Z
144:3
134:4
124:6
114:4
94:3
84:2
74:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
