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