2003:
546:
2491:. However, these cycles may involve moves between squares that are far apart within a single row or column of the chessboard. Instead, the study of "rook's tours", in the mathematics of chess, has generally concentrated on a special case of these Hamiltonian cycles where the rook is restricted to move only to adjacent squares. These single-step rook's tours only exist on boards with an even number of squares. They play a central role in the proof of
1288:
1900:
33:
2178:
2171:
2164:
2157:
2150:
2143:
2136:
2129:
2123:
2287:
largest independent set is equal to the number of cliques in a partition of the graph's vertices into a minimum number of cliques. In a rook's graph, the sets of rows or the sets of columns (whichever has fewer sets) form such an optimal partition. The size of the largest independent set in the graph is therefore
267:
Rook's graphs are highly symmetric, having symmetries taking every vertex to every other vertex. In rook's graphs defined from square chessboards, more strongly, every two edges are symmetric, and every pair of vertices is symmetric to every other pair at the same distance in moves (making the graph
243:
between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of
319:
of a rook's graph both equal the smaller of the chessboard's width and height. In terms of chess, the independence number is the maximum number of rooks that can be placed without attacking each other; the domination number is the minimum number needed to attack all unoccupied board squares. Rook's
1692:
Any two vertices in a rook's graph are either at distance one or two from each other, according to whether they are adjacent or nonadjacent respectively. Any two nonadjacent vertices may be transformed into any other two nonadjacent vertices by a symmetry of the graph. When the rook's graph is not
2286:
in a rook's graph is a set of vertices, no two of which belong to the same row or column of the graph; in chess terms, it corresponds to a placement of rooks no two of which attack each other. Perfect graphs may also be described as the graphs in which, in every induced subgraph, the size of the
1232:. These parameters describe the number of vertices, the number of edges per vertex, the number of triangles per edge, and the number of shared neighbors for two non-adjacent vertices, respectively. Conversely, every strongly regular graph with these parameters must be an
2017:
Because a rook's graph is perfect, the number of colors needed in any coloring of the graph is just the size of its largest clique. The cliques of a rook's graph are the subsets of a single row or a single column, and the largest of these have size
2338:
of a graph is the minimum cardinality among all dominating sets. On the rook's graph a set of vertices is a dominating set if and only if their corresponding squares either occupy, or are a rook's move away from, all squares on the
1101:, these properties uniquely characterize the rook's graph. That is, the rook's graphs are the only graphs with these numbers of vertices, edges, triangles per edge, and with a unique 4-cycle through each two non-adjacent vertices.
1697:
of the symmetry group according to whether they are adjacent horizontally or vertically, but when the graph is square any two adjacent vertices may also be mapped into each other by a symmetry and the graph is therefore
1948:, and two vertices of the rook's graph are adjacent if and only if the corresponding edges of the complete bipartite graph share a common endpoint. In this view, an edge in the complete bipartite graph from the
1460:
rook's graph, the neighborhood of each vertex forms two triangles, one for its rank and another for its file, without any edges from one part of the neighborhood to the other. Another way of distinguishing the
1230:
1907:), colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph.
280:. With one exception, the rook's graphs can be distinguished from all other graphs using only two properties: the numbers of triangles each edge belongs to, and the existence of a unique
1846:
3527:
Burichenko, V. P.; Makhnev, A. A. (2011), "Об автоморфизмах сильно регулярных локально циклических графов" [On automorphisms of strongly regular locally cyclic graphs],
1787:
946:
876:
299:
so that no two squares in a row or column have the same color, using a number of colors equal to the maximum number of squares from the subset in any single row or column (the
2955:
2859:
2062:
different values in such a way that the same value does not appear twice in any row or column. In the same way, a coloring of a rectangular rook's graph corresponds to a
3657:
3046:
2981:
2725:
1485:
1458:
1405:
1379:
1319:
1256:
1154:
719:
633:
2957:
rook's graph. Other examples are known, and for some rook's graphs, a complete classification is known. For instance, there are two graphs whose neighborhoods are all
1999:
to characterize the perfect graphs and to show that every graph with no odd hole and no odd antihole is perfect. In particular, rook's graphs are themselves perfect.
1687:
1595:
1565:
1036:
832:
666:
3016:
2917:
2495:
that, if two squares of opposite colors are removed from a standard chessboard, the remaining squares can always be covered by dominoes. They are featured alongside
2783:
2557:
1099:
751:
534:. Its dimension as a Hamming graph is two, and every two-dimensional Hamming graph is a rook's graph for a square chessboard. Square rook's graphs are also called "
1628:
2751:
2609:
2583:
1654:
1515:
1349:
1282:
1128:
998:
972:
902:
803:
777:
4246:
Finite
Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988
2659:
2632:
1873:
693:
3122:
2823:
2803:
2699:
2679:
1743:
1723:
1430:
1059:
1517:
rook's graph can be covered by four cliques (the four ranks or the four files of the chessboard) whereas six cliques are needed to cover the
Shrikhande graph.
3300:
1529:, meaning that they have symmetries taking every vertex to every other vertex. This implies that every vertex has an equal number of edges: they are
3558:. From the first page of the translation: "The Shrikhande graph is the only strongly regular locally hexagonal graph with parameters (16, 6, 2, 2)."
4309:
4299:
3202:
204:
3328:
2638:. There are only three classes of graphs (and finitely many exceptional graphs) that can have four eigenvalues with one of the four being
4201:
3917:
4165:
4074:
3448:
3411:
4031:
For an equivalent statement to the well-covered property of rook's graphs, in terms of matchings in complete bipartite graphs, see
4319:
1995:. Line graphs of bipartite graphs form an important family of perfect graphs: they are one of a small number of families used by
1886:, meaning that every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.
3737:
3239:
2277:
A non-attacking placement of eight rooks on a chessboard, forming a maximum independent set in the corresponding rook's graph
3837:
3784:
3606:
3490:
2386:-tuple dominating set on the rook's graph is a set of vertices whose corresponding squares attack all other squares at least
2307:
2283:
1163:
4118:
Hurley, C. B.; Oldford, R. W. (February 2011), "Graphs as navigational infrastructure for high dimensional data spaces",
530:. Because the rook's graph for a square chessboard is the Cartesian product of equal-size cliques, it is an example of a
3995:
3845:
3841:
3200:
Azizoğlu, M. Cemil; Eğecioğlu, Ömer (2003), "Extremal sets minimizing dimension-normalized boundary in
Hamming graphs",
2870:
2074:). Equivalently, it is NP-complete to determine whether a partial Latin square can be completed to a full Latin square.
1381:
rook's graph. The
Shrikhande graph obeys the same properties listed by Moon and Moser. It can be distinguished from the
308:
2378:-dominating set is a set of vertices whose corresponding squares attack all other squares (via a rook's move) at least
1408:
508:
245:
1597:, the symmetries of the rook's graph are formed by independently permuting the rows and columns of the graph, so the
542:
are rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values.
324:, meaning that placing non-attacking rooks one at a time can never get stuck until a set of maximum size is reached.
3773:
For the equivalence between
Cartesian products of complete graphs and line graphs of complete bipartite graphs, see
1849:
3698:
This follows from the definition of the rook's graph as a
Cartesian product graph, together with Proposition 4 of
2070:
to determine whether a partial coloring can be extended to a coloring of the whole graph (this problem is called
1699:
1571:. The rook's graphs are the only regular graphs formed from the moves of standard chess pieces in this way. When
269:
538:
graphs"; applied to a Latin square, its edges describe pairs of squares that cannot contain the same value. The
1976:
1916:
273:
257:
4035:
Graph Theory and
Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős
1795:
545:
307:). This class of induced subgraphs are a key component of a decomposition of perfect graphs used to prove the
489:
The squares of a single rank or file are all directly connected to each other, so each rank and file forms a
4314:
4304:
2311:
1526:
189:
83:
1157:
808:
The triangles within the rook's graph are formed by triples of squares within a single rank or file. When
3764:. See in particular Theorem 1, which identifies these graphs as line graphs of complete bipartite graphs.
2727:
rook's graph is spectrally unique: no other graph has the same spectrum. In particular this is true when
1295:
embedded on a torus. This is not a rook's graph, but is strongly regular with the same parameters as the
3857:
3529:
2516:
2071:
1992:
1656:, the graph has additional symmetries that swap the rows and columns, so the number of automorphisms is
490:
236:
140:
43:
4033:
Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984), "Equi-matchable graphs", in Bollobás, Béla (ed.),
1752:
907:
837:
3237:
Goethals, J.-M.; Seidel, J. J. (1970), "Strongly regular graphs derived from combinatorial designs",
3066:
1694:
1062:
285:
95:
3326:
Matschke, Benjamin; Pfeifle, Julian; Pilaud, Vincent (2011), "Prodsimplicial-neighborly polytopes",
3572:
2922:
2492:
635:
rook's graph (or equivalently, as they describe it, the line graph of the complete bipartite graph
574:
312:
240:
57:
4199:
Doob, Michael (1970), "On characterizing certain graphs with four eigenvalues by their spectra",
4135:
3912:
3892:
3884:
3866:
3849:
3363:
3337:
3266:
3161:
3062:
2828:
2303:
1598:
321:
194:
3909:
For the equivalence between edge-coloring complete bipartite graphs and Latin squares, see e.g.
3636:
3025:
2960:
2704:
2002:
1464:
1437:
1384:
1358:
1298:
1235:
1133:
698:
612:
352:
chessboard. Its vertices represent the squares of the chessboard, and may be given coordinates
4272:
4161:
4070:
3284:
3077:
3057:
2488:
2335:
1883:
316:
4157:
4064:
1979:
of a complete bipartite graph, and correspondingly any line graph of a bipartite graph is an
1659:
1574:
1532:
1003:
811:
638:
4210:
4181:
4127:
4004:
3990:
3963:
3926:
3876:
3833:
3793:
3746:
3709:
3615:
3551:
3499:
3457:
3420:
3389:
3347:
3248:
3211:
3173:
3131:
3088:
3019:
2986:
2887:
2874:
2524:
2496:
1980:
1746:
1352:
1292:
304:
221:
120:
4253:
4224:
4042:
4018:
3977:
3940:
3807:
3760:
3721:
3685:
3629:
3542:
3513:
3471:
3359:
3313:
3262:
3223:
3187:
3143:
3120:; Wallis, Charles (1999), "Chessboard graphs, related designs, and domination parameters",
2756:
2530:
1072:
724:
4249:
4220:
4038:
4014:
3973:
3936:
3803:
3756:
3717:
3681:
3669:
3625:
3538:
3509:
3467:
3443:
3355:
3309:
3258:
3219:
3183:
3139:
2063:
1972:
1876:
1604:
570:
554:
277:
4244:, in Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.),
3072:
2730:
2588:
2562:
1633:
1494:
1328:
1261:
1107:
977:
951:
881:
782:
756:
3911:
LeSaulnier, Timothy D.; Stocker, Christopher; Wenger, Paul S.; West, Douglas B. (2010),
2641:
2614:
1855:
675:
3393:
3385:
3117:
2808:
2788:
2684:
2664:
2635:
1988:
1728:
1708:
1415:
1044:
494:
296:
249:
174:
3798:
3292:
3135:
565:
Geometrically, the rook's graphs can be formed by sets of the vertices and edges (the
4293:
4215:
4009:
3896:
3270:
3082:
2882:
1987:: in them, and in any of their induced subgraphs, the number of colors needed in any
1984:
1568:
531:
300:
292:
261:
184:
179:
4139:
4060:
4056:
3954:
Stones, Douglas S. (2010), "The many formulae for the number of Latin rectangles",
3597:
3367:
3288:
2661:; one of the three classes is the class of rook's graphs. For most combinations of
2066:. Although finding an optimal coloring of a rook's graph is straightforward, it is
2045:
2011:
2007:
1904:
1790:
1488:
578:
550:
539:
535:
225:
213:
4238:
3713:
3488:
Fiala, Nick C.; Haemers, Willem H. (2006), "5-chromatic strongly regular graphs",
3633:. See in particular equation (10), p. 748 for the automorphism group of the
3601:
3659:
rook's graph, and the discussion above the equation for the order of this group.
3568:
2067:
1956:
th vertex on the other side corresponds to a chessboard square with coordinates
228:
4276:
3880:
3751:
3504:
1287:
4131:
3555:
3462:
3425:
3351:
3215:
2520:
1912:
566:
253:
232:
3085:, the graph of horizontal and vertical adjacencies of squares on a chessboard
4281:
3700:
Broere, Izak; Hattingh, Johannes H. (1990), "Products of circulant graphs",
1899:
32:
3735:
Gray, R.; Macpherson, D. (2010), "Countable connected-homogeneous graphs",
3620:
3253:
2413:-tuple domination number, respectively. On the square board, and for even
2310:
in a rook's graph can be extended to a maximum independent set, and every
470:, the vertices share a file and are connected by a vertical rook move; if
2499:
in the first work to discuss chess-piece tours, the 9th century
Sanskrit
582:
4248:, Oxford Science Publications, Oxford University Press, pp. 85–94,
3888:
2504:
239:
of a rook's graph represents a square on a chessboard, and there is an
3776:
244:
graphs through their alternative constructions: rook's graphs are the
3871:
3380:
Moore, Doug (1992), "Understanding simploids", in Kirk, David (ed.),
581:
is a four-dimensional shape formed as the
Cartesian product of two
3342:
2001:
1898:
1286:
544:
486:, they share a rank and are connected by a horizontal rook move.)
3968:
3931:
3409:
Moon, J. W. (1963), "On the line-graph of the complete bigraph",
3178:
507:
chessboard can be formed from these two kinds of cliques, as the
4239:"Local recognition of graphs, buildings, and related geometries"
1996:
948:
edges (the ones connecting squares on the same file) belong to
878:
edges (the ones connecting squares on the same rank) belong to
3993:(1984), "The complexity of completing partial Latin squares",
1411:
of each vertex in the
Shrikhande graph is connected to form a
1065:, namely the only rectangle using the two vertices as corners.
3446:(1964), "On the line graph of the complete bipartite graph",
295:. In other words, every subset of chessboard squares can be
4066:
Challenging Mathematical Problems with Elementary Solutions
2048:: it describes a way of filling the rows and columns of an
1983:
of a rook's graph. The line graphs of bipartite graphs are
4098:-tuple domination on the rook's graph and other results",
272:). For rectangular chessboards whose width and height are
260:. The square rook's graphs constitute the two-dimensional
1875:
vertices. Therefore, in this case, the rook's graph is a
1130:, these conditions may be abbreviated by stating that an
4154:
Across the Board: The Mathematics of Chessboard Problems
2030:, so this is also the chromatic number of the graph. An
4090:
Burchett, Paul; Lane, David; Lachniet, Jason (2009), "
3162:"The many formulae for the number of Latin rectangles"
1225:{\displaystyle \operatorname {srg} (n^{2},2n-2,n-2,2)}
915:
845:
3639:
3028:
2989:
2963:
2925:
2890:
2831:
2811:
2791:
2759:
2733:
2707:
2687:
2667:
2644:
2617:
2591:
2565:
2533:
1991:
is the same as the number of vertices in the largest
1858:
1798:
1755:
1731:
1711:
1693:
square, the pairs of adjacent vertices fall into two
1662:
1636:
1607:
1577:
1535:
1497:
1467:
1440:
1418:
1387:
1361:
1331:
1301:
1264:
1238:
1166:
1136:
1110:
1075:
1047:
1006:
980:
954:
910:
884:
840:
814:
785:
759:
727:
701:
678:
641:
615:
2634:. Because these are all integers, rook's graphs are
167:
139:
119:
94:
82:
56:
42:
25:
3651:
3040:
3010:
2975:
2949:
2911:
2853:
2817:
2797:
2777:
2745:
2719:
2693:
2673:
2653:
2626:
2603:
2577:
2551:
1867:
1840:
1781:
1737:
1717:
1681:
1648:
1622:
1589:
1559:
1509:
1479:
1452:
1424:
1399:
1373:
1343:
1313:
1276:
1250:
1224:
1148:
1122:
1093:
1053:
1041:Every two nonadjacent vertices belong to a unique
1030:
992:
966:
940:
896:
870:
826:
797:
771:
745:
713:
687:
660:
627:
342:rook's graph represents the moves of a rook on an
2006:8-coloring of a chessboard graph obtained from a
2919:, for which the neighbors of each vertex form a
2083:
1952:th vertex on one side of the bipartition to the
1789:of the rook's graph contains as a subgroup the
1351:, there is another strongly regular graph, the
1933:— that is, it has one vertex for each edge of
311:, which characterizes all perfect graphs. The
288:connecting each nonadjacent pair of vertices.
3820:
3123:Journal of Statistical Planning and Inference
931:
918:
861:
848:
8:
4037:, London: Academic Press, pp. 239–254,
3301:Notices of the American Mathematical Society
2825:sum to at least 18 and do not have the form
1903:The 3×3 rook's graph (the graph of the
1487:rook's graph from the Shrikhande graph uses
3579:, Harvard University Mathematics Department
3577:Freshman Seminar 23j: Chess and Mathematics
2390:times and are themselves attacked at least
3293:"Sudoku squares and chromatic polynomials"
2983:rook's graphs: they are the Johnson graph
31:
4214:
4182:"The knight's tour: ancient and oriental"
4008:
3967:
3930:
3913:"Rainbow matching in edge-colored graphs"
3870:
3797:
3750:
3638:
3619:
3503:
3461:
3438:
3436:
3424:
3341:
3252:
3177:
3027:
2988:
2962:
2924:
2889:
2839:
2830:
2810:
2790:
2758:
2732:
2706:
2686:
2666:
2643:
2616:
2590:
2564:
2532:
2397:times. The minimum cardinality among all
1911:A rook's graph can also be viewed as the
1857:
1832:
1819:
1803:
1797:
1773:
1760:
1754:
1730:
1710:
1673:
1661:
1635:
1606:
1576:
1534:
1496:
1466:
1439:
1417:
1386:
1360:
1330:
1300:
1263:
1237:
1180:
1165:
1135:
1109:
1074:
1046:
1005:
979:
953:
930:
917:
914:
909:
883:
860:
847:
844:
839:
813:
784:
758:
726:
700:
677:
646:
640:
614:
328:Definition and mathematical constructions
4188:, vol. 22, no. 1, pp. 1–7
3155:
3153:
1841:{\displaystyle C_{mn}=C_{m}\times C_{n}}
3672:(1974), "The symmetry of line graphs",
3100:
721:chessboard. Each vertex is adjacent to
668:) has all of the following properties:
606:
224:that represents all legal moves of the
4156:, Princeton University Press, p.
3404:
3402:
22:
3483:
3481:
3329:Discrete & Computational Geometry
2314:in a rook's graph has the same size,
2177:
2170:
2163:
2156:
2149:
2142:
2135:
2128:
2119:
2044:rook's graph may be interpreted as a
695:vertices, one for each square of the
573:, the Cartesian products of pairs of
7:
3602:"On the number of bi-colored graphs"
3203:SIAM Journal on Discrete Mathematics
3112:
3110:
3108:
3106:
3104:
602:
4202:Linear Algebra and Its Applications
4063:(1987), "Solution to problem 34b",
3956:Electronic Journal of Combinatorics
3918:Electronic Journal of Combinatorics
3166:Electronic Journal of Combinatorics
2527:) consists of the four eigenvalues
422:are adjacent if and only if either
3850:"The strong perfect graph theorem"
3777:"On perfectness of sums of graphs"
3394:10.1016/b978-0-08-050755-2.50057-9
1355:, with the same parameters as the
1069:They show that except in the case
922:
852:
14:
4180:Murray, H. J. R. (January 1902),
3449:Annals of Mathematical Statistics
3412:Annals of Mathematical Statistics
1782:{\displaystyle S_{m}\times S_{n}}
941:{\displaystyle m{\tbinom {n}{2}}}
871:{\displaystyle n{\tbinom {m}{2}}}
779:squares on the same rank and the
3775:de Werra, D.; Hertz, A. (1999),
2877:a rook's graph have been called
2176:
2169:
2162:
2155:
2148:
2141:
2134:
2127:
2121:
497:. The whole rook's graph for an
493:—a subset of vertices forming a
386:. Two vertices with coordinates
3738:Journal of Combinatorial Theory
3240:Canadian Journal of Mathematics
2405:-tuple dominating sets are the
2359:board the domination number is
3607:Pacific Journal of Mathematics
3005:
2993:
2944:
2932:
2906:
2894:
2487:Every rook's graph contains a
1554:
1536:
1219:
1173:
589:rook's graph as its skeleton.
205:Table of graphs and parameters
1:
4310:Parametric families of graphs
4257:; see in particular pp. 89–90
3799:10.1016/S0012-365X(98)00168-X
3714:10.1080/16073606.1990.9631612
3136:10.1016/S0378-3758(98)00132-3
2950:{\displaystyle k\times (n-k)}
4216:10.1016/0024-3795(70)90037-6
4010:10.1016/0166-218X(84)90075-1
3996:Discrete Applied Mathematics
2457:-tuple domination number is
2453:. In a similar fashion, the
1852:by cyclically permuting the
753:edges, connecting it to the
561:rook's graph as its skeleton
309:strong perfect graph theorem
4300:Mathematical chess problems
3821:de Werra & Hertz (1999)
3160:Stones, Douglas S. (2010),
2854:{\displaystyle 2t^{2}\pm t}
2409:-domination number and the
509:Cartesian product of graphs
4336:
4186:The British Chess Magazine
3881:10.4007/annals.2006.164.51
3752:10.1016/j.jctb.2009.04.002
3505:10.1016/j.disc.2004.03.023
2785:, or when the two numbers
4152:Watkins, John J. (2004),
4132:10.1007/s00180-011-0228-6
3652:{\displaystyle n\times n}
3556:10.1134/S1064562411070076
3352:10.1007/s00454-010-9311-y
3216:10.1137/S0895480100375053
3041:{\displaystyle 4\times 4}
2976:{\displaystyle 3\times 3}
2869:The graphs for which the
2720:{\displaystyle m\times n}
1882:Square rook's graphs are
1480:{\displaystyle 4\times 4}
1453:{\displaystyle 4\times 4}
1407:rook's graph in that the
1400:{\displaystyle 4\times 4}
1374:{\displaystyle 4\times 4}
1314:{\displaystyle 4\times 4}
1251:{\displaystyle n\times n}
1149:{\displaystyle n\times n}
904:triangles; the remaining
805:squares on the same file.
714:{\displaystyle m\times n}
628:{\displaystyle m\times n}
258:complete bipartite graphs
203:
30:
18:Graph of chess rook moves
4237:Cohen, Arjeh M. (1990),
4120:Computational Statistics
3702:Quaestiones Mathematicae
1997:Chudnovsky et al. (2006)
1917:complete bipartite graph
276:, the rook's graphs are
4320:Strongly regular graphs
3573:"Graph theory glossary"
3550:84 (3): 778–782, 2011,
3463:10.1214/aoms/1177703593
3426:10.1214/aoms/1177704179
2881:. Examples include the
2519:of a rook's graph (the
2312:maximal independent set
1682:{\displaystyle 2n!^{2}}
1590:{\displaystyle m\neq n}
1560:{\displaystyle (m+n-2)}
1031:{\displaystyle m-2=n-2}
1000:, each edge belongs to
827:{\displaystyle m\neq n}
661:{\displaystyle K_{m,n}}
593:Regularity and symmetry
4100:Congressus Numerantium
3653:
3621:10.2140/pjm.1958.8.743
3254:10.4153/CJM-1970-067-9
3042:
3012:
3011:{\displaystyle J(6,3)}
2977:
2951:
2913:
2912:{\displaystyle J(n,k)}
2855:
2819:
2799:
2779:
2747:
2721:
2695:
2675:
2655:
2628:
2605:
2579:
2553:
2421:-domination number is
2374:On the rook's graph a
2014:
1908:
1869:
1842:
1783:
1739:
1719:
1683:
1650:
1624:
1591:
1561:
1511:
1481:
1454:
1434:. In contrast, in the
1426:
1401:
1375:
1345:
1322:
1315:
1278:
1252:
1226:
1158:strongly regular graph
1150:
1124:
1095:
1055:
1032:
994:
968:
942:
898:
872:
828:
799:
773:
747:
715:
689:
662:
629:
562:
4069:, Dover, p. 77,
3858:Annals of Mathematics
3654:
3530:Doklady Akademii Nauk
3043:
3013:
2978:
2952:
2914:
2856:
2820:
2800:
2780:
2778:{\displaystyle n=m-1}
2748:
2722:
2696:
2676:
2656:
2629:
2606:
2580:
2554:
2552:{\displaystyle m+n-2}
2472:is odd and less than
2072:precoloring extension
2005:
1902:
1884:connected-homogeneous
1870:
1843:
1784:
1749:, the symmetry group
1740:
1720:
1684:
1651:
1625:
1592:
1562:
1512:
1482:
1455:
1427:
1402:
1376:
1346:
1316:
1290:
1279:
1258:rook's graph, unless
1253:
1227:
1151:
1125:
1096:
1094:{\displaystyle m=n=4}
1056:
1033:
995:
969:
943:
899:
873:
829:
800:
774:
748:
746:{\displaystyle m+n-2}
716:
690:
663:
630:
553:, a four-dimensional
548:
3991:Colbourn, Charles J.
3785:Discrete Mathematics
3674:Utilitas Mathematica
3637:
3491:Discrete Mathematics
3388:, pp. 250–255,
3172:(1): Article 1, 46,
3067:independence complex
3026:
2987:
2961:
2923:
2888:
2829:
2809:
2789:
2757:
2731:
2705:
2685:
2665:
2642:
2615:
2589:
2563:
2531:
1856:
1796:
1753:
1729:
1709:
1660:
1634:
1623:{\displaystyle m!n!}
1605:
1575:
1533:
1495:
1465:
1438:
1416:
1385:
1359:
1329:
1299:
1262:
1236:
1164:
1134:
1108:
1073:
1045:
1004:
978:
952:
908:
882:
838:
812:
783:
757:
725:
699:
676:
639:
613:
577:. For instance, the
575:neighborly polytopes
162:− 2, −2}
3548:Doklady Mathematics
3069:of the rook's graph
2746:{\displaystyle n=2}
2604:{\displaystyle n-2}
2578:{\displaystyle m-2}
2304:well-covered graphs
1700:distance-transitive
1649:{\displaystyle m=n}
1510:{\displaystyle n=4}
1344:{\displaystyle n=4}
1277:{\displaystyle n=4}
1123:{\displaystyle m=n}
993:{\displaystyle m=n}
967:{\displaystyle n-2}
897:{\displaystyle m-2}
798:{\displaystyle n-1}
772:{\displaystyle m-1}
322:well-covered graphs
313:independence number
270:distance-transitive
4273:Weisstein, Eric W.
3649:
3285:Herzberg, Agnes M.
3063:Chessboard complex
3038:
3008:
2973:
2947:
2909:
2851:
2815:
2795:
2775:
2743:
2717:
2691:
2671:
2654:{\displaystyle -2}
2651:
2627:{\displaystyle -2}
2624:
2601:
2575:
2549:
2302:Rook's graphs are
2015:
1909:
1868:{\displaystyle mn}
1865:
1838:
1779:
1735:
1715:
1679:
1646:
1620:
1599:automorphism group
1587:
1557:
1525:Rook's graphs are
1507:
1477:
1450:
1422:
1397:
1371:
1341:
1323:
1311:
1274:
1248:
1222:
1156:rook's graph is a
1146:
1120:
1091:
1051:
1028:
990:
964:
938:
936:
894:
868:
866:
824:
795:
769:
743:
711:
688:{\displaystyle mn}
685:
658:
625:
563:
291:Rook's graphs are
3962:(1): A1:1–A1:46,
3925:(1): Note 26, 5,
3834:Chudnovsky, Maria
3498:(23): 3083–3096,
3382:Graphics Gems III
2818:{\displaystyle n}
2798:{\displaystyle m}
2694:{\displaystyle n}
2674:{\displaystyle m}
2489:Hamiltonian cycle
2336:domination number
2275:
2274:
1993:complete subgraph
1738:{\displaystyle n}
1718:{\displaystyle m}
1601:of the graph has
1527:vertex-transitive
1425:{\displaystyle 6}
1054:{\displaystyle 4}
929:
859:
609:observe that the
598:Strong regularity
569:) of a family of
317:domination number
246:Cartesian product
210:
209:
190:vertex-transitive
4327:
4286:
4285:
4258:
4256:
4243:
4234:
4228:
4227:
4218:
4196:
4190:
4189:
4177:
4171:
4170:
4149:
4143:
4142:
4115:
4109:
4107:
4097:
4094:-domination and
4093:
4087:
4081:
4079:
4053:
4047:
4045:
4029:
4023:
4021:
4012:
3987:
3981:
3980:
3971:
3951:
3945:
3943:
3934:
3907:
3901:
3899:
3874:
3854:
3830:
3824:
3818:
3812:
3810:
3801:
3781:
3771:
3765:
3763:
3754:
3732:
3726:
3724:
3696:
3690:
3688:
3666:
3660:
3658:
3656:
3655:
3650:
3632:
3623:
3594:
3588:
3586:
3585:
3584:
3565:
3559:
3546:. Translated in
3545:
3524:
3518:
3516:
3507:
3485:
3476:
3474:
3465:
3440:
3431:
3429:
3428:
3406:
3397:
3396:
3377:
3371:
3370:
3345:
3323:
3317:
3316:
3297:
3281:
3275:
3273:
3256:
3234:
3228:
3226:
3197:
3191:
3190:
3181:
3157:
3148:
3146:
3130:(1–2): 285–294,
3114:
3047:
3045:
3044:
3039:
3020:complement graph
3017:
3015:
3014:
3009:
2982:
2980:
2979:
2974:
2956:
2954:
2953:
2948:
2918:
2916:
2915:
2910:
2860:
2858:
2857:
2852:
2844:
2843:
2824:
2822:
2821:
2816:
2804:
2802:
2801:
2796:
2784:
2782:
2781:
2776:
2752:
2750:
2749:
2744:
2726:
2724:
2723:
2718:
2700:
2698:
2697:
2692:
2680:
2678:
2677:
2672:
2660:
2658:
2657:
2652:
2633:
2631:
2630:
2625:
2610:
2608:
2607:
2602:
2584:
2582:
2581:
2576:
2558:
2556:
2555:
2550:
2525:adjacency matrix
2493:Gomory's theorem
2478:
2471:
2467:
2456:
2452:
2442:
2427:
2420:
2416:
2412:
2408:
2404:
2401:-dominating and
2400:
2396:
2389:
2385:
2381:
2377:
2370:
2358:
2348:
2325:
2298:
2180:
2179:
2173:
2172:
2166:
2165:
2159:
2158:
2152:
2151:
2145:
2144:
2138:
2137:
2131:
2130:
2125:
2124:
2084:
2061:
2057:
2043:
2034:-coloring of an
2033:
2029:
1981:induced subgraph
1967:
1955:
1951:
1947:
1932:
1890:Other properties
1874:
1872:
1871:
1866:
1847:
1845:
1844:
1839:
1837:
1836:
1824:
1823:
1811:
1810:
1788:
1786:
1785:
1780:
1778:
1777:
1765:
1764:
1747:relatively prime
1744:
1742:
1741:
1736:
1724:
1722:
1721:
1716:
1688:
1686:
1685:
1680:
1678:
1677:
1655:
1653:
1652:
1647:
1629:
1627:
1626:
1621:
1596:
1594:
1593:
1588:
1566:
1564:
1563:
1558:
1516:
1514:
1513:
1508:
1486:
1484:
1483:
1478:
1459:
1457:
1456:
1451:
1433:
1431:
1429:
1428:
1423:
1406:
1404:
1403:
1398:
1380:
1378:
1377:
1372:
1353:Shrikhande graph
1350:
1348:
1347:
1342:
1320:
1318:
1317:
1312:
1293:Shrikhande graph
1283:
1281:
1280:
1275:
1257:
1255:
1254:
1249:
1231:
1229:
1228:
1223:
1185:
1184:
1160:with parameters
1155:
1153:
1152:
1147:
1129:
1127:
1126:
1121:
1100:
1098:
1097:
1092:
1060:
1058:
1057:
1052:
1037:
1035:
1034:
1029:
999:
997:
996:
991:
974:triangles. When
973:
971:
970:
965:
947:
945:
944:
939:
937:
935:
934:
921:
903:
901:
900:
895:
877:
875:
874:
869:
867:
865:
864:
851:
833:
831:
830:
825:
804:
802:
801:
796:
778:
776:
775:
770:
752:
750:
749:
744:
720:
718:
717:
712:
694:
692:
691:
686:
667:
665:
664:
659:
657:
656:
634:
632:
631:
626:
588:
571:convex polytopes
560:
529:
506:
485:
469:
453:
437:
421:
403:
385:
374:
363:
351:
341:
305:induced subgraph
283:
278:circulant graphs
274:relatively prime
222:undirected graph
163:
135:
121:Chromatic number
114:
102:
90:
78:
52:
37:8x8 Rook's graph
35:
23:
4335:
4334:
4330:
4329:
4328:
4326:
4325:
4324:
4290:
4289:
4271:
4270:
4267:
4262:
4261:
4241:
4236:
4235:
4231:
4198:
4197:
4193:
4179:
4178:
4174:
4168:
4151:
4150:
4146:
4117:
4116:
4112:
4095:
4091:
4089:
4088:
4084:
4077:
4055:
4054:
4050:
4032:
4030:
4026:
3989:
3988:
3984:
3953:
3952:
3948:
3910:
3908:
3904:
3852:
3838:Robertson, Neil
3832:
3831:
3827:
3819:
3815:
3792:(1–3): 93–101,
3779:
3774:
3772:
3768:
3734:
3733:
3729:
3699:
3697:
3693:
3668:
3667:
3663:
3635:
3634:
3596:
3595:
3591:
3582:
3580:
3567:
3566:
3562:
3526:
3525:
3521:
3487:
3486:
3479:
3442:
3441:
3434:
3408:
3407:
3400:
3379:
3378:
3374:
3325:
3324:
3320:
3295:
3283:
3282:
3278:
3236:
3235:
3231:
3199:
3198:
3194:
3159:
3158:
3151:
3116:
3115:
3102:
3097:
3054:
3024:
3023:
2985:
2984:
2959:
2958:
2921:
2920:
2886:
2885:
2873:of each vertex
2867:
2865:In other graphs
2835:
2827:
2826:
2807:
2806:
2787:
2786:
2755:
2754:
2729:
2728:
2703:
2702:
2683:
2682:
2663:
2662:
2640:
2639:
2636:integral graphs
2613:
2612:
2587:
2586:
2561:
2560:
2529:
2528:
2513:
2485:
2473:
2469:
2458:
2454:
2444:
2429:
2422:
2418:
2414:
2410:
2406:
2402:
2398:
2391:
2387:
2383:
2379:
2375:
2360:
2350:
2349:board. For the
2340:
2332:
2315:
2308:independent set
2288:
2284:independent set
2280:
2279:
2278:
2182:
2181:
2174:
2167:
2160:
2153:
2146:
2139:
2132:
2122:
2080:
2064:Latin rectangle
2059:
2049:
2035:
2031:
2019:
1989:vertex coloring
1973:bipartite graph
1957:
1953:
1949:
1946:
1934:
1931:
1919:
1897:
1892:
1877:circulant graph
1854:
1853:
1828:
1815:
1799:
1794:
1793:
1769:
1756:
1751:
1750:
1727:
1726:
1707:
1706:
1669:
1658:
1657:
1632:
1631:
1630:elements. When
1603:
1602:
1573:
1572:
1531:
1530:
1523:
1493:
1492:
1463:
1462:
1436:
1435:
1414:
1413:
1412:
1383:
1382:
1357:
1356:
1327:
1326:
1297:
1296:
1260:
1259:
1234:
1233:
1176:
1162:
1161:
1132:
1131:
1106:
1105:
1071:
1070:
1043:
1042:
1002:
1001:
976:
975:
950:
949:
916:
906:
905:
880:
879:
846:
836:
835:
810:
809:
781:
780:
755:
754:
723:
722:
697:
696:
674:
673:
642:
637:
636:
611:
610:
600:
595:
586:
558:
555:convex polytope
528:
519:
511:
498:
484:
477:
471:
468:
461:
455:
452:
445:
439:
436:
429:
423:
419:
412:
405:
401:
394:
387:
376:
365:
353:
343:
333:
330:
281:
250:complete graphs
199:
145:
125:
104:
100:
88:
62:
48:
38:
19:
12:
11:
5:
4333:
4331:
4323:
4322:
4317:
4315:Regular graphs
4312:
4307:
4305:Perfect graphs
4302:
4292:
4291:
4288:
4287:
4266:
4265:External links
4263:
4260:
4259:
4229:
4209:(4): 461–482,
4191:
4172:
4166:
4144:
4126:(4): 585–612,
4110:
4082:
4075:
4048:
4024:
3982:
3946:
3902:
3825:
3813:
3766:
3727:
3708:(2): 191–216,
3691:
3661:
3648:
3645:
3642:
3614:(4): 743–755,
3589:
3560:
3537:(2): 151–155,
3533:(in Russian),
3519:
3477:
3456:(2): 883–885,
3444:Hoffman, A. J.
3432:
3419:(2): 664–667,
3398:
3386:Academic Press
3372:
3336:(1): 100–131,
3318:
3308:(6): 708–717,
3276:
3247:(3): 597–614,
3229:
3210:(2): 219–236,
3192:
3149:
3099:
3098:
3096:
3093:
3092:
3091:
3086:
3080:
3078:Knight's graph
3075:
3070:
3060:
3058:Bishop's graph
3053:
3050:
3048:rook's graph.
3037:
3034:
3031:
3007:
3004:
3001:
2998:
2995:
2992:
2972:
2969:
2966:
2946:
2943:
2940:
2937:
2934:
2931:
2928:
2908:
2905:
2902:
2899:
2896:
2893:
2883:Johnson graphs
2866:
2863:
2850:
2847:
2842:
2838:
2834:
2814:
2794:
2774:
2771:
2768:
2765:
2762:
2742:
2739:
2736:
2716:
2713:
2710:
2690:
2670:
2650:
2647:
2623:
2620:
2600:
2597:
2594:
2574:
2571:
2568:
2548:
2545:
2542:
2539:
2536:
2512:
2509:
2497:knight's tours
2484:
2481:
2331:
2328:
2276:
2273:
2272:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2242:
2239:
2235:
2234:
2231:
2227:
2226:
2223:
2219:
2218:
2215:
2211:
2210:
2207:
2203:
2202:
2199:
2195:
2194:
2191:
2187:
2186:
2183:
2175:
2168:
2161:
2154:
2147:
2140:
2133:
2126:
2120:
2118:
2114:
2113:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2082:
2081:
2079:
2076:
1938:
1923:
1896:
1893:
1891:
1888:
1864:
1861:
1835:
1831:
1827:
1822:
1818:
1814:
1809:
1806:
1802:
1776:
1772:
1768:
1763:
1759:
1734:
1714:
1676:
1672:
1668:
1665:
1645:
1642:
1639:
1619:
1616:
1613:
1610:
1586:
1583:
1580:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1522:
1519:
1506:
1503:
1500:
1476:
1473:
1470:
1449:
1446:
1443:
1421:
1396:
1393:
1390:
1370:
1367:
1364:
1340:
1337:
1334:
1310:
1307:
1304:
1273:
1270:
1267:
1247:
1244:
1241:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1183:
1179:
1175:
1172:
1169:
1145:
1142:
1139:
1119:
1116:
1113:
1090:
1087:
1084:
1081:
1078:
1067:
1066:
1050:
1039:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
989:
986:
983:
963:
960:
957:
933:
928:
925:
920:
913:
893:
890:
887:
863:
858:
855:
850:
843:
823:
820:
817:
806:
794:
791:
788:
768:
765:
762:
742:
739:
736:
733:
730:
710:
707:
704:
684:
681:
655:
652:
649:
645:
624:
621:
618:
607:Hoffman (1964)
599:
596:
594:
591:
524:
515:
495:complete graph
482:
475:
466:
459:
450:
443:
434:
427:
417:
410:
399:
392:
329:
326:
293:perfect graphs
262:Hamming graphs
252:, and are the
208:
207:
201:
200:
198:
197:
192:
187:
182:
177:
171:
169:
165:
164:
143:
137:
136:
123:
117:
116:
98:
92:
91:
86:
80:
79:
60:
54:
53:
46:
40:
39:
36:
28:
27:
17:
13:
10:
9:
6:
4:
3:
2:
4332:
4321:
4318:
4316:
4313:
4311:
4308:
4306:
4303:
4301:
4298:
4297:
4295:
4284:
4283:
4278:
4274:
4269:
4268:
4264:
4255:
4251:
4247:
4240:
4233:
4230:
4226:
4222:
4217:
4212:
4208:
4204:
4203:
4195:
4192:
4187:
4183:
4176:
4173:
4169:
4167:9780691130620
4163:
4159:
4155:
4148:
4145:
4141:
4137:
4133:
4129:
4125:
4121:
4114:
4111:
4105:
4101:
4086:
4083:
4078:
4076:9780486318578
4072:
4068:
4067:
4062:
4061:Yaglom, I. M.
4058:
4057:Yaglom, A. M.
4052:
4049:
4044:
4040:
4036:
4028:
4025:
4020:
4016:
4011:
4006:
4002:
3998:
3997:
3992:
3986:
3983:
3979:
3975:
3970:
3965:
3961:
3957:
3950:
3947:
3942:
3938:
3933:
3928:
3924:
3920:
3919:
3914:
3906:
3903:
3898:
3894:
3890:
3886:
3882:
3878:
3873:
3868:
3865:(1): 51–229,
3864:
3860:
3859:
3851:
3847:
3846:Thomas, Robin
3843:
3842:Seymour, Paul
3839:
3835:
3829:
3826:
3822:
3817:
3814:
3809:
3805:
3800:
3795:
3791:
3787:
3786:
3778:
3770:
3767:
3762:
3758:
3753:
3748:
3745:(2): 97–118,
3744:
3740:
3739:
3731:
3728:
3723:
3719:
3715:
3711:
3707:
3703:
3695:
3692:
3687:
3683:
3679:
3675:
3671:
3670:Biggs, Norman
3665:
3662:
3646:
3643:
3640:
3631:
3627:
3622:
3617:
3613:
3609:
3608:
3603:
3599:
3598:Harary, Frank
3593:
3590:
3578:
3574:
3571:(Fall 2004),
3570:
3564:
3561:
3557:
3553:
3549:
3544:
3540:
3536:
3532:
3531:
3523:
3520:
3515:
3511:
3506:
3501:
3497:
3493:
3492:
3484:
3482:
3478:
3473:
3469:
3464:
3459:
3455:
3451:
3450:
3445:
3439:
3437:
3433:
3427:
3422:
3418:
3414:
3413:
3405:
3403:
3399:
3395:
3391:
3387:
3383:
3376:
3373:
3369:
3365:
3361:
3357:
3353:
3349:
3344:
3339:
3335:
3331:
3330:
3322:
3319:
3315:
3311:
3307:
3303:
3302:
3294:
3290:
3289:Murty, M. Ram
3286:
3280:
3277:
3272:
3268:
3264:
3260:
3255:
3250:
3246:
3242:
3241:
3233:
3230:
3225:
3221:
3217:
3213:
3209:
3205:
3204:
3196:
3193:
3189:
3185:
3180:
3175:
3171:
3167:
3163:
3156:
3154:
3150:
3145:
3141:
3137:
3133:
3129:
3125:
3124:
3119:
3113:
3111:
3109:
3107:
3105:
3101:
3094:
3090:
3089:Queen's graph
3087:
3084:
3083:Lattice graph
3081:
3079:
3076:
3074:
3071:
3068:
3064:
3061:
3059:
3056:
3055:
3051:
3049:
3035:
3032:
3029:
3021:
3002:
2999:
2996:
2990:
2970:
2967:
2964:
2941:
2938:
2935:
2929:
2926:
2903:
2900:
2897:
2891:
2884:
2880:
2876:
2872:
2864:
2862:
2848:
2845:
2840:
2836:
2832:
2812:
2792:
2772:
2769:
2766:
2763:
2760:
2740:
2737:
2734:
2714:
2711:
2708:
2688:
2668:
2648:
2645:
2637:
2621:
2618:
2598:
2595:
2592:
2572:
2569:
2566:
2546:
2543:
2540:
2537:
2534:
2526:
2522:
2518:
2510:
2508:
2506:
2502:
2498:
2494:
2490:
2483:Hamiltonicity
2482:
2480:
2477:
2465:
2461:
2451:
2447:
2440:
2436:
2432:
2425:
2394:
2372:
2368:
2364:
2357:
2353:
2347:
2343:
2337:
2329:
2327:
2323:
2319:
2313:
2309:
2305:
2300:
2296:
2292:
2285:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2245:
2244:
2240:
2237:
2236:
2232:
2229:
2228:
2224:
2221:
2220:
2216:
2213:
2212:
2208:
2205:
2204:
2200:
2197:
2196:
2192:
2189:
2188:
2184:
2116:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2086:
2085:
2077:
2075:
2073:
2069:
2065:
2056:
2052:
2047:
2042:
2038:
2027:
2023:
2013:
2009:
2004:
2000:
1998:
1994:
1990:
1986:
1982:
1978:
1974:
1969:
1965:
1961:
1945:
1941:
1937:
1930:
1926:
1922:
1918:
1914:
1906:
1901:
1894:
1889:
1887:
1885:
1880:
1878:
1862:
1859:
1851:
1833:
1829:
1825:
1820:
1816:
1812:
1807:
1804:
1800:
1792:
1774:
1770:
1766:
1761:
1757:
1748:
1732:
1712:
1703:
1701:
1696:
1690:
1674:
1670:
1666:
1663:
1643:
1640:
1637:
1617:
1614:
1611:
1608:
1600:
1584:
1581:
1578:
1570:
1551:
1548:
1545:
1542:
1539:
1528:
1520:
1518:
1504:
1501:
1498:
1491:numbers: the
1490:
1474:
1471:
1468:
1447:
1444:
1441:
1419:
1410:
1394:
1391:
1388:
1368:
1365:
1362:
1354:
1338:
1335:
1332:
1321:rook's graph.
1308:
1305:
1302:
1294:
1289:
1285:
1271:
1268:
1265:
1245:
1242:
1239:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1181:
1177:
1170:
1167:
1159:
1143:
1140:
1137:
1117:
1114:
1111:
1102:
1088:
1085:
1082:
1079:
1076:
1064:
1048:
1040:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
987:
984:
981:
961:
958:
955:
926:
923:
911:
891:
888:
885:
856:
853:
841:
821:
818:
815:
807:
792:
789:
786:
766:
763:
760:
740:
737:
734:
731:
728:
708:
705:
702:
682:
679:
671:
670:
669:
653:
650:
647:
643:
622:
619:
616:
608:
604:
597:
592:
590:
584:
580:
576:
572:
568:
556:
552:
547:
543:
541:
540:Sudoku graphs
537:
533:
532:Hamming graph
527:
523:
518:
514:
510:
505:
501:
496:
492:
487:
481:
474:
465:
458:
449:
442:
433:
426:
416:
409:
398:
391:
384:
380:
373:
369:
361:
357:
350:
346:
340:
336:
327:
325:
323:
318:
314:
310:
306:
302:
301:clique number
298:
294:
289:
287:
279:
275:
271:
265:
263:
259:
255:
251:
247:
242:
238:
234:
230:
227:
223:
219:
215:
206:
202:
196:
193:
191:
188:
186:
183:
181:
178:
176:
173:
172:
170:
166:
161:
157:
153:
149:
144:
142:
138:
133:
129:
124:
122:
118:
112:
108:
99:
97:
93:
87:
85:
81:
77:
73:
69:
65:
61:
59:
55:
51:
47:
45:
41:
34:
29:
24:
21:
16:
4280:
4277:"Rook Graph"
4245:
4232:
4206:
4200:
4194:
4185:
4175:
4153:
4147:
4123:
4119:
4113:
4103:
4099:
4085:
4065:
4051:
4034:
4027:
4003:(1): 25–30,
4000:
3994:
3985:
3969:10.37236/487
3959:
3955:
3949:
3932:10.37236/475
3922:
3916:
3905:
3872:math/0212070
3862:
3856:
3828:
3816:
3789:
3783:
3769:
3742:
3741:, Series B,
3736:
3730:
3705:
3701:
3694:
3677:
3673:
3664:
3611:
3605:
3592:
3581:, retrieved
3576:
3569:Elkies, Noam
3563:
3547:
3534:
3528:
3522:
3495:
3489:
3453:
3447:
3416:
3410:
3381:
3375:
3333:
3327:
3321:
3305:
3299:
3279:
3244:
3238:
3232:
3207:
3201:
3195:
3179:10.37236/487
3169:
3165:
3127:
3121:
3118:Laskar, Renu
3073:King's graph
2879:locally grid
2878:
2868:
2514:
2501:Kavyalankara
2500:
2486:
2475:
2463:
2459:
2449:
2445:
2438:
2434:
2430:
2423:
2392:
2373:
2366:
2362:
2355:
2351:
2345:
2341:
2333:
2321:
2317:
2301:
2294:
2290:
2281:
2078:Independence
2054:
2050:
2046:Latin square
2040:
2036:
2025:
2021:
2016:
2012:finite group
2008:Cayley table
1970:
1963:
1959:
1943:
1939:
1935:
1928:
1924:
1920:
1910:
1905:3-3 duoprism
1881:
1791:cyclic group
1704:
1691:
1524:
1489:clique cover
1409:neighborhood
1324:
1103:
1068:
601:
585:, and has a
579:3-3 duoprism
564:
551:3-3 duoprism
536:Latin square
525:
521:
516:
512:
503:
499:
488:
479:
472:
463:
456:
447:
440:
431:
424:
414:
407:
396:
389:
382:
378:
371:
367:
359:
355:
348:
344:
338:
334:
331:
290:
266:
218:rook's graph
217:
214:graph theory
211:
195:well-covered
159:
155:
151:
147:
131:
127:
110:
106:
75:
74:)/2 −
71:
67:
63:
49:
26:Rook's graph
20:
15:
3680:: 113–121,
2521:eigenvalues
2068:NP-complete
603:Moon (1963)
320:graphs are
254:line graphs
229:chess piece
158:− 2,
154:− 2,
4294:Categories
3583:2023-05-03
3095:References
3018:, and the
2330:Domination
2058:grid with
1913:line graph
1895:Perfection
1038:triangles.
834:, exactly
233:chessboard
168:Properties
4282:MathWorld
4106:: 187–204
3897:119151552
3644:×
3343:0908.4177
3271:199082328
3033:×
2968:×
2939:−
2930:×
2871:neighbors
2846:±
2770:−
2712:×
2646:−
2619:−
2596:−
2570:−
2544:−
2437:− 2
2395:− 1
2382:times. A
1826:×
1767:×
1582:≠
1549:−
1472:×
1445:×
1392:×
1366:×
1306:×
1243:×
1208:−
1196:−
1171:
1141:×
1023:−
1011:−
959:−
889:−
819:≠
790:−
764:−
738:−
706:×
620:×
583:triangles
567:skeletons
557:having a
4140:54220980
3889:20159988
3848:(2006),
3600:(1958),
3291:(2007),
3052:See also
2517:spectrum
2511:Spectrum
2306:: every
1977:subgraph
1521:Symmetry
1061:-vertex
364:, where
175:integral
141:Spectrum
84:Diameter
44:Vertices
4254:1072157
4225:0285432
4043:0777180
4019:0739595
3978:2661404
3941:2651735
3808:1663807
3761:2595694
3722:1068710
3686:0347684
3630:0103834
3543:2953786
3514:2273138
3472:0161328
3368:2070310
3360:2794360
3314:2327972
3263:0282872
3224:2032290
3188:2661404
3144:1673351
2523:of its
2505:Rudrata
2354:×
2344:×
2053:×
2039:×
1985:perfect
1569:regular
672:It has
303:of the
297:colored
248:of two
235:. Each
185:regular
180:perfect
4252:
4223:
4164:
4138:
4073:
4041:
4017:
3976:
3939:
3895:
3887:
3806:
3759:
3720:
3684:
3628:
3541:
3512:
3470:
3366:
3358:
3312:
3269:
3261:
3222:
3186:
3142:
3065:, the
2875:induce
2701:, the
2611:, and
2466:+ 1)/2
2448:< 2
2417:, the
1695:orbits
1432:-cycle
491:clique
454:. (If
237:vertex
220:is an
4242:(PDF)
4136:S2CID
3893:S2CID
3885:JSTOR
3867:arXiv
3853:(PDF)
3780:(PDF)
3364:S2CID
3338:arXiv
3296:(PDF)
3267:S2CID
3022:of a
2468:when
2428:when
2010:of a
1975:is a
1915:of a
1848:that
1705:When
1325:When
1104:When
1063:cycle
587:3 × 3
559:3 × 3
286:cycle
231:on a
113:) ≥ 3
96:Girth
58:Edges
4162:ISBN
4071:ISBN
2805:and
2681:and
2515:The
2443:and
2361:min(
2334:The
2316:min(
2289:min(
2020:max(
1971:Any
1850:acts
1745:are
1725:and
1291:The
605:and
549:The
404:and
377:1 ≤
375:and
366:1 ≤
315:and
241:edge
226:rook
216:, a
126:max(
105:max(
103:(if
4211:doi
4128:doi
4104:199
4005:doi
3964:doi
3927:doi
3877:doi
3863:164
3794:doi
3790:195
3747:doi
3743:100
3710:doi
3616:doi
3552:doi
3535:441
3500:doi
3496:306
3458:doi
3421:doi
3390:doi
3348:doi
3249:doi
3212:doi
3174:doi
3132:doi
2753:or
2503:of
2441:)/4
2433:≥ (
2299:.
2282:An
1168:srg
438:or
332:An
256:of
212:In
4296::
4279:,
4275:,
4250:MR
4221:MR
4219:,
4205:,
4184:,
4160:,
4158:12
4134:,
4124:26
4122:,
4102:,
4059:;
4039:MR
4015:MR
4013:,
3999:,
3974:MR
3972:,
3960:17
3958:,
3937:MR
3935:,
3923:17
3921:,
3915:,
3891:,
3883:,
3875:,
3861:,
3855:,
3844:;
3840:;
3836:;
3804:MR
3802:,
3788:,
3782:,
3757:MR
3755:,
3718:MR
3716:,
3706:13
3704:,
3682:MR
3676:,
3626:MR
3624:,
3610:,
3604:,
3575:,
3539:MR
3510:MR
3508:,
3494:,
3480:^
3468:MR
3466:,
3454:35
3452:,
3435:^
3417:34
3415:,
3401:^
3384:,
3362:,
3356:MR
3354:,
3346:,
3334:46
3332:,
3310:MR
3306:54
3304:,
3298:,
3287:;
3265:,
3259:MR
3257:,
3245:22
3243:,
3220:MR
3218:,
3208:17
3206:,
3184:MR
3182:,
3170:17
3168:,
3164:,
3152:^
3140:MR
3138:,
3128:76
3126:,
3103:^
2861:.
2585:,
2559:,
2507:.
2479:.
2426:/2
2424:nk
2371:.
2365:,
2326:.
2320:,
2293:,
2024:,
1968:.
1962:,
1879:.
1702:.
1689:.
1284:.
520:◻
502:×
478:=
462:=
446:=
430:=
413:,
395:,
381:≤
370:≤
358:,
347:×
337:×
264:.
150:+
130:,
109:,
76:nm
70:+
64:nm
50:nm
4213::
4207:3
4130::
4108:.
4096:k
4092:K
4080:.
4046:.
4022:.
4007::
4001:8
3966::
3944:.
3929::
3900:.
3879::
3869::
3823:.
3811:.
3796::
3749::
3725:.
3712::
3689:.
3678:5
3647:n
3641:n
3618::
3612:8
3587:.
3554::
3517:.
3502::
3475:.
3460::
3430:.
3423::
3392::
3350::
3340::
3274:.
3251::
3227:.
3214::
3176::
3147:.
3134::
3036:4
3030:4
3006:)
3003:3
3000:,
2997:6
2994:(
2991:J
2971:3
2965:3
2945:)
2942:k
2936:n
2933:(
2927:k
2907:)
2904:k
2901:,
2898:n
2895:(
2892:J
2849:t
2841:2
2837:t
2833:2
2813:n
2793:m
2773:1
2767:m
2764:=
2761:n
2741:2
2738:=
2735:n
2715:n
2709:m
2689:n
2669:m
2649:2
2622:2
2599:2
2593:n
2573:2
2567:m
2547:2
2541:n
2538:+
2535:m
2476:n
2474:2
2470:k
2464:k
2462:(
2460:n
2455:k
2450:n
2446:k
2439:k
2435:k
2431:n
2419:k
2415:k
2411:k
2407:k
2403:k
2399:k
2393:k
2388:k
2384:k
2380:k
2376:k
2369:)
2367:n
2363:m
2356:n
2352:m
2346:n
2342:m
2324:)
2322:n
2318:m
2297:)
2295:n
2291:m
2269:h
2266:g
2263:f
2260:e
2257:d
2254:c
2251:b
2248:a
2241:1
2238:1
2233:2
2230:2
2225:3
2222:3
2217:4
2214:4
2209:5
2206:5
2201:6
2198:6
2193:7
2190:7
2185:8
2117:8
2110:h
2107:g
2104:f
2101:e
2098:d
2095:c
2092:b
2089:a
2060:n
2055:n
2051:n
2041:n
2037:n
2032:n
2028:)
2026:n
2022:m
1966:)
1964:j
1960:i
1958:(
1954:j
1950:i
1944:m
1942:,
1940:n
1936:K
1929:m
1927:,
1925:n
1921:K
1863:n
1860:m
1834:n
1830:C
1821:m
1817:C
1813:=
1808:n
1805:m
1801:C
1775:n
1771:S
1762:m
1758:S
1733:n
1713:m
1675:2
1671:!
1667:n
1664:2
1644:n
1641:=
1638:m
1618:!
1615:n
1612:!
1609:m
1585:n
1579:m
1567:-
1555:)
1552:2
1546:n
1543:+
1540:m
1537:(
1505:4
1502:=
1499:n
1475:4
1469:4
1448:4
1442:4
1420:6
1395:4
1389:4
1369:4
1363:4
1339:4
1336:=
1333:n
1309:4
1303:4
1272:4
1269:=
1266:n
1246:n
1240:n
1220:)
1217:2
1214:,
1211:2
1205:n
1202:,
1199:2
1193:n
1190:2
1187:,
1182:2
1178:n
1174:(
1144:n
1138:n
1118:n
1115:=
1112:m
1089:4
1086:=
1083:n
1080:=
1077:m
1049:4
1026:2
1020:n
1017:=
1014:2
1008:m
988:n
985:=
982:m
962:2
956:n
932:)
927:2
924:n
919:(
912:m
892:2
886:m
862:)
857:2
854:m
849:(
842:n
822:n
816:m
793:1
787:n
767:1
761:m
741:2
735:n
732:+
729:m
709:n
703:m
683:n
680:m
654:n
651:,
648:m
644:K
623:n
617:m
526:m
522:K
517:n
513:K
504:m
500:n
483:2
480:y
476:1
473:y
467:2
464:x
460:1
457:x
451:2
448:y
444:1
441:y
435:2
432:x
428:1
425:x
420:)
418:2
415:y
411:2
408:x
406:(
402:)
400:1
397:y
393:1
390:x
388:(
383:m
379:y
372:n
368:x
362:)
360:y
356:x
354:(
349:m
345:n
339:m
335:n
284:-
282:4
160:n
156:m
152:n
148:m
146:{
134:)
132:m
128:n
115:)
111:m
107:n
101:3
89:2
72:m
68:n
66:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
