Knowledge

Turán graph

Source 📝

1358: 29: 436: 1618:
operations. Specifically, such a sequence can begin by forming each of the independent sets of the Turán graph as a disjoint union of isolated vertices. Then, the overall graph is the complement of the disjoint union of the complements of these independent sets.
234: 320: 1344:
extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the
985: 885: 333: 140: 1471:
couples go to a party, and each person shakes hands with every person except his or her partner, then this graph describes the set of handshakes that take place; for this reason, it is also called the
1338: 153: 782: 247: 1568: 1647:
develop an efficient algorithm for finding clusters of orthologous groups of genes in genome data, by representing the data as a graph and searching for large Turán subgraphs.
915: 719: 556: 505: 1514:, although some authors consider Turán graphs to be a trivial case of strong regularity and therefore exclude them from the definition of a strongly regular graph. 1109: 1590: ≤ 2; each maximal clique is formed by choosing one vertex from each partition subset. This is the largest number of maximal cliques possible among all 1205: 1135: 1057: 1031: 1179: 1159: 1077: 1005: 920: 684: 664: 644: 624: 604: 584: 464: 71: 790: 1236: + 1 vertices in the Turán graph includes two vertices in the same partition subset; therefore, the Turán graph does not contain a 606:
subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where
431:{\displaystyle \left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{otherwise}}\end{array}}\right.} 85: 1994: 1885: 2154: 1271: 511: 229:{\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.} 1244: + 1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all ( 315:{\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.} 2159: 1955: 1841: 2051: 1920: 1690: 724: 1678:, is attained for a configuration formed by embedding a Turán graph onto the vertices of a regular simplex. 1524: 2049:
Witsenhausen, H. S. (1974). "On the maximum of the sum of squared distances under a diameter constraint".
559: 1517:
The class of Turán graphs can have exponentially many maximal cliques, meaning this class does not have
1989: 1341: 1615: 1487: 1594:-vertex graphs regardless of the number of edges in the graph; these graphs are sometimes called 1518: 240: 146: 1717:
colors. The partition of the Turán graph into independent sets corresponds to the partition of
1651: 1511: 1237: 1226: 894: 49: 1216: 689: 526: 475: 2036:(1941). "Egy gráfelméleti szélsőértékfeladatról (On an extremal problem in graph theory)". 1877: 1630: 1082: 326: 980:{\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor } 8: 1437: 1184: 1114: 1036: 1010: 77: 2092: 2068: 1964: 1937: 1902: 1710: 1164: 1144: 1062: 990: 669: 649: 629: 609: 589: 569: 563: 449: 56: 1380:(6,3). Unconnected vertices are given the same color in this face-centered projection. 1357: 2127: 2111: 2108: 2089: 1855: 1836: 1906: 2060: 2007: 1999: 1974: 1941: 1929: 1894: 1865: 1850: 1460: 1404: 1346: 880:{\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}} 442: 2021: 1998:. Lecture Notes in Computer Science no. 3383, Springer-Verlag. pp. 395–402. 1507: 2130: 1633:. Nikiforov (2005) uses Turán graphs to supply a lower bound for the sum of the 2033: 1979: 1950: 1611: 1571: 1445: 1408: 1366: 1222: 42: 1898: 1388:
in a Turán graph lead to notable graphs that have been independently studied.
342: 256: 162: 2148: 1663: 1138: 1721:
into color classes. In particular, the Turán graph is the unique maximal
1495: 1969: 2072: 2012: 1933: 1638: 1464: 1362: 2024:(1969). Tutte, W.T. (ed.). "On the boxicity and cubicity of a graph". 1610:; that is, it can be formed from individual vertices by a sequence of 2135: 2116: 2097: 1915: 2064: 2003: 1425: 1607: 1225:, who used them to prove Turán's theorem, an important result in 135:{\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}} 1787: 1650:
Turán graphs also have some interesting properties related to
2087: 1670:
conjectures that the maximum sum of squared distances, among
28: 425: 309: 223: 2106: 1739: 1866:"Computing high-stringency COGs using Turán type graphs" 1333:{\displaystyle {\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}} 1864:
Falls, Craig; Powell, Bradford; Snoeyink, Jack (2003).
1811: 1775: 1527: 1274: 1187: 1167: 1147: 1117: 1085: 1065: 1039: 1013: 993: 923: 897: 793: 727: 692: 672: 652: 632: 612: 592: 572: 529: 478: 452: 336: 250: 156: 88: 59: 2125: 1763: 1863: 1793: 1644: 917:, this edge count can be more succinctly stated as 1878:"Local density in graphs with forbidden subgraphs" 1799: 1751: 1562: 1332: 1199: 1173: 1153: 1129: 1103: 1071: 1051: 1025: 999: 979: 909: 879: 776: 713: 678: 658: 638: 618: 598: 578: 550: 499: 458: 430: 314: 228: 134: 65: 871: 858: 2146: 1875: 1745: 1253: 1951:"Eigenvalue problems of Nordhaus-Gaddum type" 2048: 1817: 1667: 1554: 1540: 1340:edges, if α is sufficiently close to 1. The 1256:show that the Turán graph is also the only ( 1834: 1781: 1622: 1260: + 1)-clique-free graph of order 646:are the quotient and remainder of dividing 1662:)) on the volume of any three-dimensional 1232:By the pigeonhole principle, every set of 2011: 1978: 1968: 1948: 1913: 1854: 1769: 1287: 1281: 1995:Proc. Int. Symp. Graph Drawing (GD 2004) 1886:Combinatorics, Probability and Computing 1356: 1248: + 1)-clique-free graphs with 2020: 1987: 1876:Keevash, Peter; Sudakov, Benny (2003). 1805: 1757: 1655: 1421: 777:{\displaystyle K_{q+1,q+1,\ldots ,q,q}} 2147: 1563:{\displaystyle T(n,\lceil n/3\rceil )} 2126: 2107: 2088: 2032: 1835:Chao, C. Y.; Novacky, G. A. (1982). 16:Balanced complete multipartite graph 1794:Falls, Powell & Snoeyink (2003) 1645:Falls, Powell & Snoeyink (2003) 1601: 13: 1992:(2005). "No-three-in-line-in-3D". 1210: 862: 345: 259: 165: 14: 2171: 2081: 1384:Several choices of the parameter 2026:Recent Progress in Combinatorics 1918:(1965). "On cliques in graphs". 1629:: no other graphs have the same 1352: 27: 1837:"On maximally saturated graphs" 1641:of a graph and its complement. 1625:show that the Turán graphs are 1521:. For example, the Turán graph 1432:; it is sometimes known as the 1264:in which every subset of α 1557: 1531: 1403:) can be formed by removing a 1369:whose edges and vertices form 1317: 1302: 545: 533: 512:Table of graphs and parameters 494: 482: 386: 362: 1: 2155:Parametric families of graphs 2052:American Mathematical Monthly 1921:Israel Journal of Mathematics 1827: 1674:points with unit diameter in 1221:Turán graphs are named after 784:, and the number of edges is 2038:Matematikai és Fizikai Lapok 1949:Nikiforov, Vladimir (2007). 1856:10.1016/0012-365X(82)90200-X 1746:Keevash & Sudakov (2003) 1254:Keevash & Sudakov (2003) 721:), the graph is of the form 7: 1729:-color equitable coloring. 1463:, the graph of the regular 1436:. This graph is also the 1- 560:complete multipartite graph 10: 2176: 1980:10.1016/j.disc.2006.07.035 1448:; for instance, the graph 1214: 1899:10.1017/S0963548302005539 1782:Chao & Novacky (1982) 1658:give a lower bound of Ω(( 1623:Chao & Novacky (1982) 1079:; each vertex has degree 510: 469: 441: 325: 239: 145: 76: 48: 38: 26: 21: 1732: 1488:complete bipartite graph 1268:vertices spans at least 1770:Moon & Moser (1965) 1606:Every Turán graph is a 1424:showed, this graph has 910:{\displaystyle r\leq 7} 33:The Turán graph T(13,4) 2093:"Cocktail Party Graph" 1725:-vertex graph with an 1652:geometric graph theory 1564: 1381: 1334: 1201: 1175: 1155: 1131: 1105: 1073: 1053: 1027: 1001: 981: 911: 881: 778: 715: 714:{\displaystyle n=qr+s} 680: 660: 640: 620: 600: 580: 552: 551:{\displaystyle T(n,r)} 501: 500:{\displaystyle T(n,r)} 460: 432: 316: 230: 136: 67: 2160:Extremal graph theory 1806:Pór & Wood (2005) 1656:Pór & Wood (2005) 1631:chromatic polynomials 1565: 1506:, the Turán graph is 1360: 1335: 1227:extremal graph theory 1202: 1176: 1156: 1132: 1106: 1104:{\displaystyle n-q-1} 1074: 1054: 1028: 1002: 982: 912: 882: 779: 716: 681: 661: 641: 621: 601: 581: 553: 502: 461: 433: 317: 231: 137: 68: 1956:Discrete Mathematics 1842:Discrete Mathematics 1666:of the Turán graph. 1627:chromatically unique 1525: 1473:cocktail party graph 1272: 1185: 1165: 1145: 1115: 1083: 1063: 1037: 1011: 991: 921: 895: 791: 725: 690: 670: 650: 630: 610: 590: 570: 527: 476: 450: 334: 248: 154: 86: 57: 1818:Witsenhausen (1974) 1668:Witsenhausen (1974) 1342:Erdős–Stone theorem 1200:{\displaystyle s=0} 1130:{\displaystyle n-q} 1052:{\displaystyle r-s} 1026:{\displaystyle q+1} 2128:Weisstein, Eric W. 2112:"Octahedral Graph" 2109:Weisstein, Eric W. 2090:Weisstein, Eric W. 1934:10.1007/BF02760024 1711:equitable coloring 1560: 1452:(6,3) =  1382: 1330: 1197: 1171: 1151: 1127: 1101: 1069: 1049: 1023: 997: 977: 907: 877: 774: 711: 676: 656: 636: 616: 596: 576: 564:partitioning a set 562:; it is formed by 548: 497: 456: 428: 423: 312: 307: 226: 221: 132: 63: 2059:(10): 1100–1101. 1705:) if and only if 1693:of a Turán graph 1596:Moon–Moser graphs 1349:of the subgraph. 1300: 1174:{\displaystyle r} 1154:{\displaystyle n} 1072:{\displaystyle q} 1000:{\displaystyle s} 970: 948: 869: 850: 813: 679:{\displaystyle r} 659:{\displaystyle n} 639:{\displaystyle s} 619:{\displaystyle q} 599:{\displaystyle r} 579:{\displaystyle n} 517: 516: 459:{\displaystyle r} 419: 303: 217: 130: 108: 66:{\displaystyle n} 2167: 2141: 2140: 2122: 2121: 2103: 2102: 2076: 2045: 2029: 2017: 2015: 1984: 1982: 1972: 1945: 1910: 1882: 1872: 1870: 1860: 1858: 1821: 1815: 1809: 1803: 1797: 1791: 1785: 1779: 1773: 1767: 1761: 1755: 1749: 1743: 1602:Other properties 1569: 1567: 1566: 1561: 1550: 1512:strongly regular 1502:is a divisor of 1478:The Turán graph 1461:octahedral graph 1405:perfect matching 1391:The Turán graph 1376:, a Turán graph 1347:chromatic number 1339: 1337: 1336: 1331: 1329: 1328: 1301: 1299: 1291: 1286: 1276: 1252: vertices. 1206: 1204: 1203: 1198: 1180: 1178: 1177: 1172: 1161:is divisible by 1160: 1158: 1157: 1152: 1136: 1134: 1133: 1128: 1110: 1108: 1107: 1102: 1078: 1076: 1075: 1070: 1059:subsets of size 1058: 1056: 1055: 1050: 1032: 1030: 1029: 1024: 1007:subsets of size 1006: 1004: 1003: 998: 987:. The graph has 986: 984: 983: 978: 976: 972: 971: 966: 965: 956: 954: 950: 949: 941: 916: 914: 913: 908: 886: 884: 883: 878: 876: 875: 874: 861: 851: 846: 845: 844: 832: 831: 821: 819: 815: 814: 806: 783: 781: 780: 775: 773: 772: 720: 718: 717: 712: 685: 683: 682: 677: 665: 663: 662: 657: 645: 643: 642: 637: 625: 623: 622: 617: 605: 603: 602: 597: 585: 583: 582: 577: 557: 555: 554: 549: 506: 504: 503: 498: 465: 463: 462: 457: 443:Chromatic number 437: 435: 434: 429: 427: 424: 420: 417: 321: 319: 318: 313: 311: 308: 304: 301: 235: 233: 232: 227: 225: 222: 218: 215: 201: 141: 139: 138: 133: 131: 126: 125: 116: 114: 110: 109: 101: 72: 70: 69: 64: 31: 19: 18: 2175: 2174: 2170: 2169: 2168: 2166: 2165: 2164: 2145: 2144: 2084: 2079: 2065:10.2307/2319046 2004:10.1007/b105810 1970:math.CO/0506260 1880: 1868: 1830: 1825: 1824: 1816: 1812: 1804: 1800: 1792: 1788: 1780: 1776: 1768: 1764: 1756: 1752: 1744: 1740: 1735: 1604: 1572:maximal cliques 1546: 1526: 1523: 1522: 1458: 1419: 1375: 1355: 1324: 1320: 1292: 1282: 1277: 1275: 1273: 1270: 1269: 1219: 1217:Turán's theorem 1213: 1211:Turán's theorem 1186: 1183: 1182: 1166: 1163: 1162: 1146: 1143: 1142: 1116: 1113: 1112: 1084: 1081: 1080: 1064: 1061: 1060: 1038: 1035: 1034: 1012: 1009: 1008: 992: 989: 988: 961: 957: 955: 940: 933: 929: 928: 924: 922: 919: 918: 896: 893: 892: 870: 857: 856: 855: 840: 836: 827: 823: 822: 820: 805: 798: 794: 792: 789: 788: 732: 728: 726: 723: 722: 691: 688: 687: 671: 668: 667: 651: 648: 647: 631: 628: 627: 611: 608: 607: 591: 588: 587: 571: 568: 567: 528: 525: 524: 477: 474: 473: 451: 448: 447: 422: 421: 416: 414: 408: 407: 396: 390: 389: 348: 341: 337: 335: 332: 331: 306: 305: 300: 298: 292: 291: 280: 274: 273: 262: 255: 251: 249: 246: 245: 220: 219: 214: 212: 206: 205: 197: 186: 180: 179: 168: 161: 157: 155: 152: 151: 121: 117: 115: 100: 93: 89: 87: 84: 83: 58: 55: 54: 34: 17: 12: 11: 5: 2173: 2163: 2162: 2157: 2143: 2142: 2123: 2104: 2083: 2082:External links 2080: 2078: 2077: 2046: 2030: 2022:Roberts, F. S. 2018: 1990:Wood, David R. 1985: 1963:(6): 774–780. 1946: 1911: 1893:(2): 139–153. 1873: 1861: 1849:(2): 139–143. 1831: 1829: 1826: 1823: 1822: 1810: 1798: 1786: 1774: 1762: 1758:Roberts (1969) 1750: 1737: 1736: 1734: 1731: 1685:-vertex graph 1664:grid embedding 1612:disjoint union 1603: 1600: 1578: + 2 1559: 1556: 1553: 1549: 1545: 1542: 1539: 1536: 1533: 1530: 1456: 1446:cross-polytope 1422:Roberts (1969) 1414: 1409:complete graph 1373: 1367:cross polytope 1354: 1351: 1327: 1323: 1319: 1316: 1313: 1310: 1307: 1304: 1298: 1295: 1290: 1285: 1280: 1215:Main article: 1212: 1209: 1196: 1193: 1190: 1170: 1150: 1126: 1123: 1120: 1100: 1097: 1094: 1091: 1088: 1068: 1048: 1045: 1042: 1022: 1019: 1016: 996: 975: 969: 964: 960: 953: 947: 944: 939: 936: 932: 927: 906: 903: 900: 889: 888: 873: 868: 865: 860: 854: 849: 843: 839: 835: 830: 826: 818: 812: 809: 804: 801: 797: 771: 768: 765: 762: 759: 756: 753: 750: 747: 744: 741: 738: 735: 731: 710: 707: 704: 701: 698: 695: 675: 655: 635: 615: 595: 586:vertices into 575: 547: 544: 541: 538: 535: 532: 515: 514: 508: 507: 496: 493: 490: 487: 484: 481: 471: 467: 466: 455: 445: 439: 438: 426: 415: 413: 410: 409: 406: 403: 400: 397: 395: 392: 391: 388: 385: 382: 379: 376: 373: 370: 367: 364: 361: 358: 355: 352: 349: 347: 344: 343: 340: 329: 323: 322: 310: 299: 297: 294: 293: 290: 287: 284: 281: 279: 276: 275: 272: 269: 266: 263: 261: 258: 257: 254: 243: 237: 236: 224: 213: 211: 208: 207: 204: 200: 196: 193: 190: 187: 185: 182: 181: 178: 175: 172: 169: 167: 164: 163: 160: 149: 143: 142: 129: 124: 120: 113: 107: 104: 99: 96: 92: 80: 74: 73: 62: 52: 46: 45: 40: 36: 35: 32: 24: 23: 15: 9: 6: 4: 3: 2: 2172: 2161: 2158: 2156: 2153: 2152: 2150: 2138: 2137: 2132: 2131:"Turán Graph" 2129: 2124: 2119: 2118: 2113: 2110: 2105: 2100: 2099: 2094: 2091: 2086: 2085: 2074: 2070: 2066: 2062: 2058: 2054: 2053: 2047: 2043: 2039: 2035: 2031: 2027: 2023: 2019: 2014: 2009: 2005: 2001: 1997: 1996: 1991: 1988:Pór, Attila; 1986: 1981: 1976: 1971: 1966: 1962: 1958: 1957: 1952: 1947: 1943: 1939: 1935: 1931: 1927: 1923: 1922: 1917: 1914:Moon, J. W.; 1912: 1908: 1904: 1900: 1896: 1892: 1888: 1887: 1879: 1874: 1867: 1862: 1857: 1852: 1848: 1844: 1843: 1838: 1833: 1832: 1819: 1814: 1807: 1802: 1795: 1790: 1783: 1778: 1771: 1766: 1759: 1754: 1747: 1742: 1738: 1730: 1728: 1724: 1720: 1716: 1712: 1708: 1704: 1700: 1696: 1692: 1688: 1684: 1679: 1677: 1673: 1669: 1665: 1661: 1657: 1653: 1648: 1646: 1642: 1640: 1636: 1632: 1628: 1624: 1620: 1617: 1613: 1609: 1599: 1597: 1593: 1589: 1585: 1582: =  1581: 1577: 1573: 1551: 1547: 1543: 1537: 1534: 1528: 1520: 1515: 1513: 1509: 1505: 1501: 1497: 1493: 1489: 1485: 1481: 1476: 1474: 1470: 1466: 1462: 1455: 1451: 1447: 1444:-dimensional 1443: 1439: 1435: 1434:Roberts graph 1431: 1427: 1423: 1418: 1413: 1410: 1406: 1402: 1398: 1394: 1389: 1387: 1379: 1372: 1368: 1364: 1359: 1353:Special cases 1350: 1348: 1343: 1325: 1321: 1314: 1311: 1308: 1305: 1296: 1293: 1288: 1283: 1278: 1267: 1263: 1259: 1255: 1251: 1247: 1243: 1240:of size  1239: 1235: 1230: 1228: 1224: 1218: 1208: 1194: 1191: 1188: 1168: 1148: 1140: 1139:regular graph 1124: 1121: 1118: 1098: 1095: 1092: 1089: 1086: 1066: 1046: 1043: 1040: 1020: 1017: 1014: 994: 973: 967: 962: 958: 951: 945: 942: 937: 934: 930: 925: 904: 901: 898: 866: 863: 852: 847: 841: 837: 833: 828: 824: 816: 810: 807: 802: 799: 795: 787: 786: 785: 769: 766: 763: 760: 757: 754: 751: 748: 745: 742: 739: 736: 733: 729: 708: 705: 702: 699: 696: 693: 673: 653: 633: 613: 593: 573: 565: 561: 542: 539: 536: 530: 523:, denoted by 522: 513: 509: 491: 488: 485: 479: 472: 468: 453: 446: 444: 440: 411: 404: 401: 398: 393: 383: 380: 377: 374: 371: 368: 365: 359: 356: 353: 350: 338: 330: 328: 324: 295: 288: 285: 282: 277: 270: 267: 264: 252: 244: 242: 238: 209: 202: 198: 194: 191: 188: 183: 176: 173: 170: 158: 150: 148: 144: 127: 122: 118: 111: 105: 102: 97: 94: 90: 81: 79: 75: 60: 53: 51: 47: 44: 41: 37: 30: 25: 20: 2134: 2115: 2096: 2056: 2050: 2041: 2037: 2025: 1993: 1960: 1954: 1925: 1919: 1890: 1884: 1846: 1840: 1813: 1801: 1789: 1777: 1765: 1753: 1741: 1726: 1722: 1718: 1714: 1706: 1702: 1698: 1694: 1686: 1682: 1680: 1675: 1671: 1659: 1649: 1643: 1634: 1626: 1621: 1605: 1595: 1591: 1587: 1583: 1579: 1575: 1516: 1503: 1499: 1491: 1483: 1479: 1477: 1472: 1468: 1453: 1449: 1441: 1433: 1429: 1416: 1411: 1400: 1396: 1392: 1390: 1385: 1383: 1377: 1370: 1265: 1261: 1257: 1249: 1245: 1241: 1233: 1231: 1220: 890: 520: 518: 2013:11693/27422 1639:eigenvalues 1519:few cliques 1496:Moore graph 1494:is even, a 1181:(i.e. when 521:Turán graph 39:Named after 22:Turán graph 2149:Categories 2044:: 436–452. 2028:: 301–310. 1828:References 1709:admits an 1616:complement 1490:and, when 1465:octahedron 1363:octahedron 1137:. It is a 2136:MathWorld 2117:MathWorld 2098:MathWorld 2034:Turán, P. 1928:: 23–28. 1916:Moser, L. 1574:, where 3 1555:⌉ 1541:⌈ 1508:symmetric 1486:,2) is a 1312:− 1309:α 1284:− 1223:Pál Turán 1122:− 1096:− 1090:− 1044:− 938:− 902:≤ 834:− 803:− 758:… 418:otherwise 381:≤ 375:∧ 369:≤ 360:∨ 346:∞ 302:otherwise 260:∞ 216:otherwise 192:≤ 166:∞ 98:− 43:Pál Turán 1907:17854032 1691:subgraph 1438:skeleton 1428:exactly 1426:boxicity 974:⌋ 926:⌊ 470:Notation 241:Diameter 50:Vertices 2073:2319046 1942:9855414 1608:cograph 1570:has 32 1498:. When 1459:is the 1407:from a 558:, is a 2071:  1940:  1905:  1440:of an 1365:, a 3- 1238:clique 1033:, and 147:Radius 2069:JSTOR 1965:arXiv 1938:S2CID 1903:S2CID 1881:(PDF) 1869:(PDF) 1733:Notes 1713:with 1689:is a 1467:. If 1457:2,2,2 1420:. As 1374:2,2,2 327:Girth 78:Edges 1614:and 1586:and 1510:and 1361:The 891:For 686:(so 626:and 519:The 2061:doi 2008:hdl 2000:doi 1975:doi 1961:307 1930:doi 1895:doi 1851:doi 1681:An 1637:th 1207:). 1141:if 1111:or 666:by 566:of 2151:: 2133:. 2114:. 2095:. 2067:. 2057:81 2055:. 2042:48 2040:. 2006:. 1973:. 1959:. 1953:. 1936:. 1924:. 1901:. 1891:12 1889:. 1883:. 1847:41 1845:. 1839:. 1660:rn 1654:. 1598:. 1475:. 1395:(2 1229:. 2139:. 2120:. 2101:. 2075:. 2063:: 2016:. 2010:: 2002:: 1983:. 1977:: 1967:: 1944:. 1932:: 1926:3 1909:. 1897:: 1871:. 1859:. 1853:: 1820:. 1808:. 1796:. 1784:. 1772:. 1760:. 1748:. 1727:r 1723:n 1719:G 1715:r 1707:G 1703:r 1701:, 1699:n 1697:( 1695:T 1687:G 1683:n 1676:R 1672:n 1635:k 1592:n 1588:b 1584:n 1580:b 1576:a 1558:) 1552:3 1548:/ 1544:n 1538:, 1535:n 1532:( 1529:T 1504:n 1500:r 1492:n 1484:n 1482:( 1480:T 1469:n 1454:K 1450:T 1442:n 1430:n 1417:n 1415:2 1412:K 1401:n 1399:, 1397:n 1393:T 1386:r 1378:T 1371:K 1326:2 1322:n 1318:) 1315:1 1306:2 1303:( 1297:r 1294:3 1289:1 1279:r 1266:n 1262:n 1258:r 1250:n 1246:r 1242:r 1234:r 1195:0 1192:= 1189:s 1169:r 1149:n 1125:q 1119:n 1099:1 1093:q 1087:n 1067:q 1047:s 1041:r 1021:1 1018:+ 1015:q 995:s 968:2 963:2 959:n 952:) 946:r 943:1 935:1 931:( 905:7 899:r 887:. 872:) 867:2 864:s 859:( 853:+ 848:2 842:2 838:s 829:2 825:n 817:) 811:r 808:1 800:1 796:( 770:q 767:, 764:q 761:, 755:, 752:1 749:+ 746:q 743:, 740:1 737:+ 734:q 730:K 709:s 706:+ 703:r 700:q 697:= 694:n 674:r 654:n 634:s 614:q 594:r 574:n 546:) 543:r 540:, 537:n 534:( 531:T 495:) 492:r 489:, 486:n 483:( 480:T 454:r 412:3 405:2 402:= 399:r 394:4 387:) 384:2 378:r 372:3 366:n 363:( 357:1 354:= 351:r 339:{ 296:2 289:n 286:= 283:r 278:1 271:1 268:= 265:r 253:{ 210:1 203:2 199:/ 195:n 189:r 184:2 177:1 174:= 171:r 159:{ 128:2 123:2 119:n 112:) 106:r 103:1 95:1 91:( 82:~ 61:n

Index


Pál Turán
Vertices
Edges
Radius
Diameter
Girth
Chromatic number
Table of graphs and parameters
complete multipartite graph
partitioning a set
regular graph
Turán's theorem
Pál Turán
extremal graph theory
clique
Keevash & Sudakov (2003)
Erdős–Stone theorem
chromatic number

octahedron
cross polytope
perfect matching
complete graph
Roberts (1969)
boxicity
skeleton
cross-polytope
octahedral graph
octahedron

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.