Knowledge (XXG)

Oberwolfach problem

Source 📝

120: 265:
In conferences held at Oberwolfach, it is the custom for the participants to dine together in a room with circular tables, not all the same size, and with assigned seating that rearranges the participants from meal to meal. The Oberwolfach problem asks how to make a seating chart for a given set of
587:
In order for a solution to exist, the total number of conference participants (or equivalently, the total capacity of the tables, or the total number of vertices of the given cycle graphs) must be an odd number. For, at each meal, each participant sits next to two neighbors, so the total number of
460: 1172:, of grouping fifteen schoolgirls into rows of three in seven different ways so that each pair of girls appears once in each triple, is a special case of the Oberwolfach problem, 588:
neighbors of each participant must be even, and this is only possible when the total number of participants is odd. The problem has, however, also been extended to even values of
266:
tables so that all tables are full at each meal and all pairs of conference participants are seated next to each other exactly once. An instance of the problem can be denoted as
314: 352: 188: 1209: 982: 943: 904: 854: 772: 733: 391: 1927: 1014: 2003: 1489: 1382: 1158: 1120: 1082: 810: 1891: 1429: 1272: 1240: 542: 220: 148: 88: 686: 250: 1449: 1402: 1342: 1322: 1298: 1037: 658: 626: 606: 582: 562: 515: 491: 108: 61: 41: 1641: 1280:, on the decomposition of a complete graph into cycles of given sizes, is related to the Oberwolfach problem, but neither is a special case of the other. If 860:
is supported by recent non-constructive and asymptotic solutions for large complete graphs of order greater than a lower bound that is however unquantified.
640:(a different mathematical problem involving seating arrangements of diners and tables), this variant of the problem can be formulated by supposing that the 2216: 113: 1761: 354:
are the given table sizes. Alternatively, when some table sizes are repeated, they may be denoted using exponential notation; for instance,
688:
married couples, and that the seating arrangements should place each diner next to each other diner except their own spouse exactly once.
396:
Formulated as a problem in graph theory, the pairs of people sitting next to each other at a single meal can be represented as a
2170: 2081: 1832: 1697: 1169: 2211: 1931: 1521: 2079:
Bryant, Darryn; Scharaschkin, Victor (2009), "Complete solutions to the Oberwolfach problem for an infinite set of orders",
237:
that may be formulated either as a problem of scheduling seating assignments for diners, or more abstractly as a problem in
2124: 1971: 1324:
vertices, formed from a disjoint union of cycles of certain lengths, then a solution to the Oberwolfach problem for
1212: 406: 397: 2012: 1789: 1277: 269: 1618: 1451:, and on the other hand not every instance of Alspach's conjecture involves sets of cycles that have 462:
of the specified lengths, with one cycle for each of the dining tables. This union of cycles is a
319: 2133: 1706: 1650: 1608: 153: 1175: 948: 909: 870: 815: 738: 699: 357: 1896: 1757: 993: 637: 1975: 1454: 1347: 1125: 1087: 1049: 777: 2179: 2143: 2090: 2021: 1940: 1841: 1830:; Wagner, David (1989), "The Oberwolfach problem and factors of uniform odd length cycles", 1798: 1749: 1716: 1660: 1573: 1530: 629: 242: 2193: 2155: 2102: 2066: 2033: 1954: 1869: 1853: 1810: 1771: 1728: 1672: 1587: 1544: 1431:
into this many cycles of each size can be grouped into disjoint cycles that form copies of
1407: 1245: 1218: 520: 193: 126: 66: 2189: 2151: 2098: 2062: 2029: 1950: 1849: 1806: 1767: 1724: 1668: 1583: 1540: 1636: 663: 2120:"On factorisations of complete graphs into circulant graphs and the Oberwolfach problem" 2119: 1748:, North-Holland Math. Stud., vol. 115, Amsterdam: North-Holland, pp. 227–232, 1622: 1516: 1434: 1387: 1327: 1307: 1283: 1040: 1022: 643: 611: 591: 567: 547: 500: 476: 254: 246: 93: 46: 26: 2168:
Traetta, Tommaso (2013), "A complete solution to the two-table Oberwolfach problems",
1753: 2205: 2115: 1945: 1845: 1823: 1784: 1685: 1578: 1535: 1512: 465: 696:
The only instances of the Oberwolfach problem that are known not to be solvable are
2118:; Bryant, Darryn; Horsley, Daniel; Maenhaut, Barbara; Scharaschkin, Victor (2016), 1827: 1561: 238: 234: 2047: 401: 226: 2184: 2147: 2094: 1720: 1689: 857: 119: 1603:
Salassa, F.; Dragotto, G.; Traetta, T.; Buratti, M.; Della Croce, F. (2019),
1787:; Häggkvist, Roland (1985), "Some observations on the Oberwolfach problem", 1802: 1664: 856:. It is widely believed that all other instances have a solution. This 1564:; Rosa, Alexander (1979), "On a variation of the Oberwolfach problem", 15: 2025: 1605:
Merging Combinatorial Design and Optimization: the Oberwolfach Problem
257:. It is known to be true for all sufficiently-large complete graphs. 1711: 1655: 1613: 2138: 118: 1639:; Osthus, Deryk (2021), "Resolution of the Oberwolfach problem", 2055:
Journal of Combinatorial Mathematics and Combinatorial Computing
1519:(1991), "A brief review on Egmont Köhler's mathematical work", 1866:
Hoffman, D. G.; Schellenberg, P. J. (1991), "The existence of
1344:
would also provide a decomposition of the complete graph into
628:, whether all of the edges of the complete graph except for a 1744:
Häggkvist, Roland (1985), "A lemma on cycle decompositions",
2046:
Deza, A.; Franek, F.; Hua, W.; Meszka, M.; Rosa, A. (2010),
2048:"Solutions to the Oberwolfach problem for orders 18 to 40" 987:
All instances in which all of the cycles have even length.
863:
Cases for which a constructive solution is known include:
564:
can be represented as an edge-disjoint union of copies of
393:
describes an instance with three tables of size five.
1978: 1899: 1872: 1457: 1437: 1410: 1390: 1350: 1330: 1310: 1286: 1248: 1221: 1178: 1128: 1090: 1052: 1025: 996: 990:
All instances (other than the known exceptions) with
951: 912: 873: 818: 780: 741: 702: 666: 646: 614: 594: 570: 550: 523: 517:
vertices, the question is whether the complete graph
503: 479: 409: 360: 322: 272: 196: 156: 129: 96: 69: 49: 29: 1997: 1921: 1885: 1483: 1443: 1423: 1396: 1376: 1336: 1316: 1292: 1266: 1234: 1203: 1152: 1114: 1076: 1031: 1008: 976: 937: 898: 848: 804: 766: 727: 680: 652: 620: 600: 576: 556: 536: 509: 485: 454: 385: 346: 308: 214: 182: 142: 102: 82: 55: 35: 190:, solving the Oberwolfach problem for the input 251:Oberwolfach Research Institute for Mathematics 8: 1642:Journal of the European Mathematical Society 90:be decomposed into edge-disjoint copies of 1635:Glock, Stefan; Joos, Felix; Kim, Jaehoon; 2183: 2137: 1983: 1977: 1944: 1904: 1898: 1877: 1871: 1710: 1654: 1612: 1577: 1534: 1473: 1456: 1436: 1415: 1409: 1389: 1366: 1349: 1329: 1309: 1285: 1247: 1226: 1220: 1192: 1177: 1127: 1089: 1051: 1024: 995: 965: 950: 926: 911: 887: 872: 817: 779: 755: 740: 716: 701: 670: 665: 645: 613: 593: 569: 549: 528: 522: 502: 478: 455:{\displaystyle C_{x}+C_{y}+C_{z}+\cdots } 440: 427: 414: 408: 374: 359: 321: 271: 253:, where the problem was posed in 1967 by 195: 174: 161: 155: 134: 128: 95: 74: 68: 48: 28: 1970:Bryant, Darryn; Danziger, Peter (2011), 1499: 1039:, belonging to infinite subsets of the 114:(more unsolved problems in mathematics) 1746:Cycles in graphs (Burnaby, B.C., 1982) 1598: 1596: 1404:. However, not every decomposition of 632:can be covered by copies of the given 1965: 1963: 1690:"The generalised Oberwolfach problem" 1555: 1553: 1019:All instances for certain choices of 7: 1507: 1505: 1503: 123:Decomposition of the complete graph 1739: 1737: 1972:"On bipartite 2-factorizations of 14: 2217:Unsolved problems in graph theory 1384:copies of each of the cycles of 1084:other than the known exceptions 309:{\displaystyle OP(x,y,z,\dots )} 2171:Journal of Combinatorial Theory 2082:Journal of Combinatorial Theory 1833:Journal of Combinatorial Theory 1698:Journal of Combinatorial Theory 18:Unsolved problem in mathematics 1470: 1458: 1363: 1351: 1261: 1255: 1198: 1185: 1147: 1135: 1109: 1097: 1071: 1059: 971: 958: 932: 919: 893: 880: 843: 825: 799: 787: 761: 748: 722: 709: 380: 367: 303: 279: 209: 197: 1: 2125:Ars Mathematica Contemporanea 1754:10.1016/S0304-0208(08)73015-9 2005:and the Oberwolfach problem" 1946:10.1016/0012-365X(91)90440-D 1846:10.1016/0097-3165(89)90059-9 1688:; Staden, Katherine (2022), 1579:10.1016/0012-365X(79)90162-6 1536:10.1016/0012-365X(91)90416-Y 1170:Kirkman's schoolgirl problem 347:{\displaystyle x,y,z,\dots } 183:{\displaystyle C_{3}+C_{4}} 2233: 2185:10.1016/j.jcta.2013.01.003 2148:10.26493/1855-3974.770.150 2095:10.1016/j.jctb.2009.03.003 1721:10.1016/j.jctb.2021.09.007 1242:is another special case, 1213:Hamiltonian decomposition 1204:{\displaystyle OP(3^{5})} 977:{\displaystyle OP(3^{4})} 938:{\displaystyle OP(3^{2})} 899:{\displaystyle OP(x^{y})} 849:{\displaystyle OP(3,3,5)} 767:{\displaystyle OP(3^{4})} 728:{\displaystyle OP(3^{2})} 660:diners are arranged into 386:{\displaystyle OP(5^{3})} 1922:{\displaystyle K_{2n}-F} 1009:{\displaystyle n\leq 60} 473:graph has this form. If 249:. It is named after the 2013:Journal of Graph Theory 1998:{\displaystyle K_{n}-I} 1826:; Schellenberg, P. J.; 1790:Journal of Graph Theory 1484:{\displaystyle (n-1)/2} 1377:{\displaystyle (n-1)/2} 1153:{\displaystyle OP(4,5)} 1115:{\displaystyle OP(3,3)} 1077:{\displaystyle OP(x,y)} 805:{\displaystyle OP(4,5)} 63:can the complete graph 1999: 1923: 1887: 1803:10.1002/jgt.3190090114 1491:copies of each cycle. 1485: 1445: 1425: 1398: 1378: 1338: 1318: 1294: 1268: 1236: 1205: 1154: 1116: 1078: 1033: 1010: 978: 939: 900: 850: 806: 768: 729: 682: 654: 622: 602: 578: 558: 538: 511: 487: 456: 387: 348: 310: 222: 216: 184: 144: 104: 84: 57: 37: 2212:Mathematical problems 2000: 1924: 1888: 1886:{\displaystyle C_{k}} 1486: 1446: 1426: 1424:{\displaystyle K_{n}} 1399: 1379: 1339: 1319: 1295: 1269: 1267:{\displaystyle OP(n)} 1237: 1235:{\displaystyle K_{n}} 1206: 1155: 1117: 1079: 1034: 1011: 979: 940: 901: 851: 807: 769: 730: 683: 655: 623: 608:by asking, for those 603: 579: 559: 539: 537:{\displaystyle K_{n}} 512: 488: 457: 388: 349: 311: 217: 215:{\displaystyle (3,4)} 185: 150:into three copies of 145: 143:{\displaystyle K_{7}} 122: 105: 85: 83:{\displaystyle K_{n}} 58: 38: 1976: 1932:Discrete Mathematics 1897: 1870: 1566:Discrete Mathematics 1522:Discrete Mathematics 1455: 1435: 1408: 1388: 1348: 1328: 1308: 1284: 1278:Alspach's conjecture 1246: 1219: 1215:of a complete graph 1176: 1126: 1088: 1050: 1023: 994: 949: 910: 871: 816: 778: 739: 700: 664: 644: 612: 592: 568: 548: 521: 501: 477: 407: 358: 320: 270: 194: 154: 127: 94: 67: 47: 27: 23:For which 2-regular 1893:-factorizations of 1623:2019arXiv190312112S 681:{\displaystyle n/2} 231:Oberwolfach problem 1995: 1919: 1883: 1560:Huang, Charlotte; 1481: 1441: 1421: 1394: 1374: 1334: 1314: 1290: 1264: 1232: 1201: 1150: 1112: 1074: 1029: 1006: 974: 935: 896: 846: 802: 764: 725: 678: 650: 618: 598: 574: 554: 534: 507: 483: 452: 383: 344: 306: 223: 212: 180: 140: 100: 80: 53: 33: 2026:10.1002/jgt.20538 1763:978-0-444-87803-8 1665:10.4171/jems/1060 1444:{\displaystyle G} 1397:{\displaystyle G} 1337:{\displaystyle G} 1317:{\displaystyle n} 1293:{\displaystyle G} 1211:. The problem of 1032:{\displaystyle n} 653:{\displaystyle n} 621:{\displaystyle n} 601:{\displaystyle n} 577:{\displaystyle G} 557:{\displaystyle n} 510:{\displaystyle n} 486:{\displaystyle G} 469:graph, and every 243:edge cycle covers 103:{\displaystyle G} 56:{\displaystyle G} 36:{\displaystyle n} 2224: 2197: 2196: 2187: 2165: 2159: 2158: 2141: 2112: 2106: 2105: 2076: 2070: 2069: 2052: 2043: 2037: 2036: 2009: 2004: 2002: 2001: 1996: 1988: 1987: 1967: 1958: 1957: 1948: 1939:(1–3): 243–250, 1928: 1926: 1925: 1920: 1912: 1911: 1892: 1890: 1889: 1884: 1882: 1881: 1863: 1857: 1856: 1820: 1814: 1813: 1781: 1775: 1774: 1741: 1732: 1731: 1714: 1694: 1682: 1676: 1675: 1658: 1649:(8): 2511–2547, 1632: 1626: 1625: 1616: 1600: 1591: 1590: 1581: 1557: 1548: 1547: 1538: 1509: 1490: 1488: 1487: 1482: 1477: 1450: 1448: 1447: 1442: 1430: 1428: 1427: 1422: 1420: 1419: 1403: 1401: 1400: 1395: 1383: 1381: 1380: 1375: 1370: 1343: 1341: 1340: 1335: 1323: 1321: 1320: 1315: 1303: 1299: 1297: 1296: 1291: 1273: 1271: 1270: 1265: 1241: 1239: 1238: 1233: 1231: 1230: 1210: 1208: 1207: 1202: 1197: 1196: 1165:Related problems 1159: 1157: 1156: 1151: 1121: 1119: 1118: 1113: 1083: 1081: 1080: 1075: 1038: 1036: 1035: 1030: 1015: 1013: 1012: 1007: 983: 981: 980: 975: 970: 969: 944: 942: 941: 936: 931: 930: 905: 903: 902: 897: 892: 891: 855: 853: 852: 847: 811: 809: 808: 803: 773: 771: 770: 765: 760: 759: 734: 732: 731: 726: 721: 720: 687: 685: 684: 679: 674: 659: 657: 656: 651: 636:graph. Like the 635: 630:perfect matching 627: 625: 624: 619: 607: 605: 604: 599: 583: 581: 580: 575: 563: 561: 560: 555: 543: 541: 540: 535: 533: 532: 516: 514: 513: 508: 496: 492: 490: 489: 484: 472: 468: 461: 459: 458: 453: 445: 444: 432: 431: 419: 418: 392: 390: 389: 384: 379: 378: 353: 351: 350: 345: 315: 313: 312: 307: 221: 219: 218: 213: 189: 187: 186: 181: 179: 178: 166: 165: 149: 147: 146: 141: 139: 138: 109: 107: 106: 101: 89: 87: 86: 81: 79: 78: 62: 60: 59: 54: 42: 40: 39: 34: 19: 2232: 2231: 2227: 2226: 2225: 2223: 2222: 2221: 2202: 2201: 2200: 2167: 2166: 2162: 2114: 2113: 2109: 2078: 2077: 2073: 2050: 2045: 2044: 2040: 2007: 1979: 1974: 1973: 1969: 1968: 1961: 1900: 1895: 1894: 1873: 1868: 1867: 1865: 1864: 1860: 1822: 1821: 1817: 1783: 1782: 1778: 1764: 1743: 1742: 1735: 1692: 1684: 1683: 1679: 1634: 1633: 1629: 1602: 1601: 1594: 1559: 1558: 1551: 1517:Ringel, Gerhard 1511: 1510: 1501: 1497: 1453: 1452: 1433: 1432: 1411: 1406: 1405: 1386: 1385: 1346: 1345: 1326: 1325: 1306: 1305: 1301: 1282: 1281: 1244: 1243: 1222: 1217: 1216: 1188: 1174: 1173: 1167: 1124: 1123: 1086: 1085: 1048: 1047: 1041:natural numbers 1021: 1020: 992: 991: 961: 947: 946: 922: 908: 907: 883: 869: 868: 814: 813: 776: 775: 751: 737: 736: 712: 698: 697: 694: 662: 661: 642: 641: 633: 610: 609: 590: 589: 566: 565: 546: 545: 524: 519: 518: 499: 498: 494: 475: 474: 470: 463: 436: 423: 410: 405: 404: 370: 356: 355: 318: 317: 268: 267: 263: 247:complete graphs 192: 191: 170: 157: 152: 151: 130: 125: 124: 117: 116: 111: 92: 91: 70: 65: 64: 45: 44: 43:-vertex graphs 25: 24: 21: 17: 12: 11: 5: 2230: 2228: 2220: 2219: 2214: 2204: 2203: 2199: 2198: 2178:(5): 984–997, 2160: 2132:(1): 157–173, 2116:Alspach, Brian 2107: 2089:(6): 904–918, 2071: 2038: 1994: 1991: 1986: 1982: 1959: 1918: 1915: 1910: 1907: 1903: 1880: 1876: 1858: 1828:Stinson, D. R. 1824:Alspach, Brian 1815: 1797:(1): 177–187, 1785:Alspach, Brian 1776: 1762: 1733: 1686:Keevash, Peter 1677: 1627: 1592: 1572:(3): 261–277, 1549: 1513:Lenz, Hanfried 1498: 1496: 1493: 1480: 1476: 1472: 1469: 1466: 1463: 1460: 1440: 1418: 1414: 1393: 1373: 1369: 1365: 1362: 1359: 1356: 1353: 1333: 1313: 1289: 1263: 1260: 1257: 1254: 1251: 1229: 1225: 1200: 1195: 1191: 1187: 1184: 1181: 1166: 1163: 1162: 1161: 1149: 1146: 1143: 1140: 1137: 1134: 1131: 1111: 1108: 1105: 1102: 1099: 1096: 1093: 1073: 1070: 1067: 1064: 1061: 1058: 1055: 1046:All instances 1044: 1028: 1017: 1005: 1002: 999: 988: 985: 973: 968: 964: 960: 957: 954: 934: 929: 925: 921: 918: 915: 895: 890: 886: 882: 879: 876: 867:All instances 845: 842: 839: 836: 833: 830: 827: 824: 821: 801: 798: 795: 792: 789: 786: 783: 763: 758: 754: 750: 747: 744: 724: 719: 715: 711: 708: 705: 693: 690: 677: 673: 669: 649: 638:ménage problem 617: 597: 573: 553: 531: 527: 506: 497:graph and has 482: 451: 448: 443: 439: 435: 430: 426: 422: 417: 413: 398:disjoint union 382: 377: 373: 369: 366: 363: 343: 340: 337: 334: 331: 328: 325: 305: 302: 299: 296: 293: 290: 287: 284: 281: 278: 275: 262: 259: 255:Gerhard Ringel 211: 208: 205: 202: 199: 177: 173: 169: 164: 160: 137: 133: 112: 99: 77: 73: 52: 32: 22: 16: 13: 10: 9: 6: 4: 3: 2: 2229: 2218: 2215: 2213: 2210: 2209: 2207: 2195: 2191: 2186: 2181: 2177: 2173: 2172: 2164: 2161: 2157: 2153: 2149: 2145: 2140: 2135: 2131: 2127: 2126: 2121: 2117: 2111: 2108: 2104: 2100: 2096: 2092: 2088: 2084: 2083: 2075: 2072: 2068: 2064: 2060: 2056: 2049: 2042: 2039: 2035: 2031: 2027: 2023: 2019: 2015: 2014: 2006: 1992: 1989: 1984: 1980: 1966: 1964: 1960: 1956: 1952: 1947: 1942: 1938: 1934: 1933: 1916: 1913: 1908: 1905: 1901: 1878: 1874: 1862: 1859: 1855: 1851: 1847: 1843: 1839: 1835: 1834: 1829: 1825: 1819: 1816: 1812: 1808: 1804: 1800: 1796: 1792: 1791: 1786: 1780: 1777: 1773: 1769: 1765: 1759: 1755: 1751: 1747: 1740: 1738: 1734: 1730: 1726: 1722: 1718: 1713: 1708: 1704: 1700: 1699: 1691: 1687: 1681: 1678: 1674: 1670: 1666: 1662: 1657: 1652: 1648: 1644: 1643: 1638: 1637:Kühn, Daniela 1631: 1628: 1624: 1620: 1615: 1610: 1606: 1599: 1597: 1593: 1589: 1585: 1580: 1575: 1571: 1567: 1563: 1562:Kotzig, Anton 1556: 1554: 1550: 1546: 1542: 1537: 1532: 1529:(1–3): 3–16, 1528: 1524: 1523: 1518: 1514: 1508: 1506: 1504: 1500: 1494: 1492: 1478: 1474: 1467: 1464: 1461: 1438: 1416: 1412: 1391: 1371: 1367: 1360: 1357: 1354: 1331: 1311: 1287: 1279: 1275: 1258: 1252: 1249: 1227: 1223: 1214: 1193: 1189: 1182: 1179: 1171: 1164: 1144: 1141: 1138: 1132: 1129: 1106: 1103: 1100: 1094: 1091: 1068: 1065: 1062: 1056: 1053: 1045: 1042: 1026: 1018: 1003: 1000: 997: 989: 986: 966: 962: 955: 952: 927: 923: 916: 913: 888: 884: 877: 874: 866: 865: 864: 861: 859: 840: 837: 834: 831: 828: 822: 819: 796: 793: 790: 784: 781: 756: 752: 745: 742: 717: 713: 706: 703: 692:Known results 691: 689: 675: 671: 667: 647: 639: 631: 615: 595: 585: 571: 551: 529: 525: 504: 480: 467: 449: 446: 441: 437: 433: 428: 424: 420: 415: 411: 403: 399: 394: 375: 371: 364: 361: 341: 338: 335: 332: 329: 326: 323: 300: 297: 294: 291: 288: 285: 282: 276: 273: 260: 258: 256: 252: 248: 244: 240: 236: 232: 228: 206: 203: 200: 175: 171: 167: 162: 158: 135: 131: 121: 115: 97: 75: 71: 50: 30: 2175: 2174:, Series A, 2169: 2163: 2129: 2123: 2110: 2086: 2085:, Series B, 2080: 2074: 2058: 2054: 2041: 2020:(1): 22–37, 2017: 2011: 1936: 1930: 1861: 1840:(1): 20–43, 1837: 1836:, Series A, 1831: 1818: 1794: 1788: 1779: 1745: 1702: 1701:, Series B, 1696: 1680: 1646: 1640: 1630: 1604: 1569: 1565: 1526: 1520: 1276: 1168: 862: 695: 586: 402:cycle graphs 395: 264: 239:graph theory 235:open problem 230: 224: 1705:: 281–318, 1304:graph with 261:Formulation 227:mathematics 2206:Categories 2061:: 95–102, 1712:2004.09937 1656:1806.04644 1614:1903.12112 1495:References 858:conjecture 2139:1411.6047 1990:− 1914:− 1465:− 1358:− 1302:2-regular 1001:≤ 634:2-regular 544:of order 495:2-regular 471:2-regular 450:⋯ 342:… 301:… 241:, on the 493:is this 2194:3033656 2156:3546656 2103:2558441 2067:2675892 2034:2833961 1955:1140806 1854:1008157 1811:0785659 1772:0821524 1729:4332743 1673:4269420 1619:Bibcode 1588:0541472 1545:1140782 906:except 466:regular 2192:  2154:  2101:  2065:  2032:  1953:  1852:  1809:  1770:  1760:  1727:  1671:  1586:  1543:  812:, and 316:where 233:is an 229:, the 2134:arXiv 2051:(PDF) 2008:(PDF) 1707:arXiv 1693:(PDF) 1651:arXiv 1609:arXiv 1300:is a 1758:ISBN 1122:and 945:and 2180:doi 2176:120 2144:doi 2091:doi 2022:doi 1941:doi 1929:", 1842:doi 1799:doi 1750:doi 1717:doi 1703:152 1661:doi 1574:doi 1531:doi 400:of 245:of 225:In 2208:: 2190:MR 2188:, 2152:MR 2150:, 2142:, 2130:11 2128:, 2122:, 2099:MR 2097:, 2087:99 2063:MR 2059:74 2057:, 2053:, 2030:MR 2028:, 2018:68 2016:, 2010:, 1962:^ 1951:MR 1949:, 1937:97 1935:, 1850:MR 1848:, 1838:52 1807:MR 1805:, 1793:, 1768:MR 1766:, 1756:, 1736:^ 1725:MR 1723:, 1715:, 1695:, 1669:MR 1667:, 1659:, 1647:23 1645:, 1617:, 1607:, 1595:^ 1584:MR 1582:, 1570:27 1568:, 1552:^ 1541:MR 1539:, 1527:97 1525:, 1515:; 1502:^ 1274:. 1004:60 774:, 735:, 584:. 464:2- 2182:: 2146:: 2136:: 2093:: 2024:: 1993:I 1985:n 1981:K 1943:: 1917:F 1909:n 1906:2 1902:K 1879:k 1875:C 1844:: 1801:: 1795:9 1752:: 1719:: 1709:: 1663:: 1653:: 1621:: 1611:: 1576:: 1533:: 1479:2 1475:/ 1471:) 1468:1 1462:n 1459:( 1439:G 1417:n 1413:K 1392:G 1372:2 1368:/ 1364:) 1361:1 1355:n 1352:( 1332:G 1312:n 1288:G 1262:) 1259:n 1256:( 1253:P 1250:O 1228:n 1224:K 1199:) 1194:5 1190:3 1186:( 1183:P 1180:O 1160:. 1148:) 1145:5 1142:, 1139:4 1136:( 1133:P 1130:O 1110:) 1107:3 1104:, 1101:3 1098:( 1095:P 1092:O 1072:) 1069:y 1066:, 1063:x 1060:( 1057:P 1054:O 1043:. 1027:n 1016:. 998:n 984:. 972:) 967:4 963:3 959:( 956:P 953:O 933:) 928:2 924:3 920:( 917:P 914:O 894:) 889:y 885:x 881:( 878:P 875:O 844:) 841:5 838:, 835:3 832:, 829:3 826:( 823:P 820:O 800:) 797:5 794:, 791:4 788:( 785:P 782:O 762:) 757:4 753:3 749:( 746:P 743:O 723:) 718:2 714:3 710:( 707:P 704:O 676:2 672:/ 668:n 648:n 616:n 596:n 572:G 552:n 530:n 526:K 505:n 481:G 447:+ 442:z 438:C 434:+ 429:y 425:C 421:+ 416:x 412:C 381:) 376:3 372:5 368:( 365:P 362:O 339:, 336:z 333:, 330:y 327:, 324:x 304:) 298:, 295:z 292:, 289:y 286:, 283:x 280:( 277:P 274:O 210:) 207:4 204:, 201:3 198:( 176:4 172:C 168:+ 163:3 159:C 136:7 132:K 110:? 98:G 76:n 72:K 51:G 31:n 20::

Index

(more unsolved problems in mathematics)

mathematics
open problem
graph theory
edge cycle covers
complete graphs
Oberwolfach Research Institute for Mathematics
Gerhard Ringel
disjoint union
cycle graphs
regular
perfect matching
ménage problem
conjecture
natural numbers
Kirkman's schoolgirl problem
Hamiltonian decomposition
Alspach's conjecture



Lenz, Hanfried
Ringel, Gerhard
Discrete Mathematics
doi
10.1016/0012-365X(91)90416-Y
MR
1140782

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