633:
29:
710:-vertex crown graph may be embedded into four-dimensional Euclidean space in such a way that all of its edges have unit length. However, this embedding may also place some non-adjacent vertices a unit distance apart. An embedding in which edges are at unit distance and non-edges are not at unit distance requires at least
909:
of a crown graph. For instance, the arrangements of vertices shown in the figure can be interpreted as seating charts of this type in which each husband and wife are seated as far apart as possible. The problem of counting the number of possible seating arrangements, or almost equivalently the number
289:
203:
135:
833:
357:
901:, a traditional rule for arranging guests at a dinner table is that men and women should alternate positions, and that no married couple should sit next to each other. The arrangements satisfying this rule, for a party consisting of
216:
1124:
In the ménage problem, the starting position of the cycle is considered significant, so the number of
Hamiltonian cycles and the solution to the ménage problem differ by a factor of 2
148:
80:
405:
738:
302:
1408:
624:, a configuration of 12 lines and 30 points in three-dimensional space, the twelve lines intersect each other in the pattern of a 12-vertex crown graph.
925:
1550:
1442:
1027:; they use this example to show that representing visibility graphs as unions of complete bipartite graphs may not always be space-efficient.
1425:
1365:
411:
1171:
1486:
1110:
1211:
1447:
936:
algorithms behave badly in the worst case: if the vertices of a crown graph are presented to the algorithm in the order
839:
857:
284:{\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\6&n=3\\4&{\text{otherwise}}\end{array}}\right.}
1327:
1034:
vertices, with its edges oriented from one side of the bipartition to the other, forms the standard example of a
693:
366:
725:
539:
523:
1555:
141:
73:
1249:
1011:
621:
531:
717:
dimensions. This example shows that a graph may require very different dimensions to be represented as a
198:{\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}
130:{\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}
1035:
434:
39:
1240:
Chaudhary, Amitabh; Vishwanathan, Sundar (2001), "Approximation algorithms for the achromatic number",
632:
1315:
209:
989:
uses crown graphs as part of a construction showing hardness of approximation of coloring problems.
1000:
729:
718:
54:
1254:
1472:
1388:
Proc. 5th
Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae
1371:
1275:
828:{\displaystyle \sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\},}
378:
352:{\displaystyle \left\{{\begin{array}{ll}1&n=1\\2&{\text{otherwise}}\end{array}}\right.}
1523:
1421:
1402:
1361:
1291:
1287:
1154:
1106:
1100:
914:; for crown graphs with 6, 8, 10, ... vertices the number of (oriented) Hamiltonian cycles is
911:
906:
663:
655:
613:
1495:
1456:
1445:(1996), "On the distortion required for embedding finite metric spaces into normed spaces",
1383:
1353:
1259:
1220:
1180:
1024:
1010:
show, crown graphs are one of a small number of different types of graphs that can occur as
846:
527:
438:
295:
1507:
1468:
1435:
1395:
1340:
1303:
1271:
1232:
1194:
1503:
1464:
1431:
1391:
1348:
FĂĽrer, Martin (1995), "Improved hardness results for approximating the chromatic number",
1336:
1299:
1267:
1228:
1190:
1039:
1014:
933:
689:
1209:; Gavlas, H. (2004), "Cycle systems in the complete bipartite graph minus a one-factor",
886:
968:
colors, whereas the optimal number of colors is two. This construction is attributed to
1202:
861:
535:
1499:
1544:
1476:
1375:
1311:
641:
600:-item set, with an edge between two subsets whenever one is contained in the other.
1279:
1166:
1162:
996:
574:
420:
1526:
1206:
609:
1294:(1981), "The Boolean rank of zero-one matrices", in Cadogan, Charles C. (ed.),
1224:
1298:, Department of Mathematics, University of the West Indies, pp. 169–173,
311:
225:
157:
89:
1357:
1531:
1319:
1158:
898:
700:
describe partitions of the edges of a crown graph into equal-length cycles.
1263:
1484:
MiklaviÄŤ, Ĺ tefko; PotoÄŤnik, PrimoĹľ (2003), "Distance-regular circulants",
28:
910:
of
Hamiltonian cycles in a crown graph, is known in combinatorics as the
1460:
1185:
631:
617:
1350:
Proceedings of IEEE 36th Annual
Foundations of Computer Science
918:
2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (sequence
697:
1296:
Proc. 3rd
Caribbean Conference on Combinatorics and Computing
1386:(1974), "Worst-case behavior of graph coloring algorithms",
1169:(1994), "Can visibility graphs be represented compactly?",
920:
346:
278:
192:
124:
557:, as the complement of the Cartesian direct product of
1086:
1062:
1020:
741:
381:
305:
219:
151:
83:
1105:(2nd ed.), John Wiley & Sons, p. 244,
372:
362:
294:
208:
140:
72:
53:
38:
21:
1023:describe polygons that have crown graphs as their
995:uses distances in crown graphs as an example of a
827:
399:
351:
283:
197:
129:
810:
781:
1007:
757:
728:needed to cover the edges of a crown graph (its
1074:
16:Family of graphs with 2n nodes and n(n-1) edges
732:, or the size of a minimum biclique cover) is
688:as one of the color classes. Crown graphs are
636:A biclique cover of the ten-vertex crown graph
33:Crown graphs with six, eight, and ten vertices
1320:"On the chromatic number of geometric graphs"
8:
804:
790:
640:The number of edges in a crown graph is the
1407:: CS1 maint: location missing publisher (
1253:
1184:
905:married couples, can be described as the
816:
809:
796:
780:
778:
765:
740:
391:
386:
380:
337:
310:
304:
269:
224:
218:
183:
156:
150:
115:
88:
82:
992:
1055:
969:
932:Crown graphs can be used to show that
1400:
1137:
18:
1087:de Caen, Gregory & Pullman (1981)
986:
972:; crown graphs are sometimes called
721:and as a strict unit distance graph.
7:
964:, etc., then a greedy coloring uses
1172:Discrete and Computational Geometry
1063:Chaudhary & Vishwanathan (2001)
522:The crown graph can be viewed as a
999:that is difficult to embed into a
785:
612:, and the 8-vertex crown graph is
228:
160:
92:
14:
1487:European Journal of Combinatorics
1420:, American Mathematical Society,
608:The 6-vertex crown graph forms a
27:
1390:, Winnipeg, pp. 513–527,
1008:MiklaviÄŤ & PotoÄŤnik (2003)
751:
745:
412:Table of graphs and parameters
1:
1551:Parametric families of graphs
1500:10.1016/S0195-6698(03)00117-3
1448:Israel Journal of Mathematics
1075:Erdős & Simonovits (1980)
423:, a branch of mathematics, a
840:central binomial coefficient
838:the inverse function of the
726:complete bipartite subgraphs
588:representing the 1-item and
856:-vertex crown graph is the
1572:
1225:10.1016/j.disc.2003.11.021
530:have been removed, as the
526:from which the edges of a
441:with two sets of vertices
410:
400:{\displaystyle S_{n}^{0}}
26:
1358:10.1109/SFCS.1995.492572
698:Archdeacon et al. (2004)
524:complete bipartite graph
1264:10.1006/jagm.2001.1192
879:, or equivalently the
829:
724:The minimum number of
666:by choosing each pair
637:
575:bipartite Kneser graph
532:bipartite double cover
495:and with an edge from
401:
353:
285:
199:
131:
1290:; Gregory, David A.;
1242:Journal of Algorithms
1102:Etiquette For Dummies
1036:partially ordered set
1021:Agarwal et al. (1994)
830:
635:
402:
354:
286:
200:
132:
1352:, pp. 414–421,
1212:Discrete Mathematics
1030:A crown graph with 2
739:
596:-item subsets of an
379:
303:
217:
149:
81:
1416:Kubale, M. (2004),
1001:normed vector space
730:bipartite dimension
719:unit distance graph
694:distance-transitive
622:Schläfli double six
396:
367:Distance-transitive
1524:Weisstein, Eric W.
1461:10.1007/BF02761110
1316:Simonovits, MiklĂłs
1292:Pullman, Norman J.
1288:de Caen, Dominique
1186:10.1007/BF02574385
1155:Agarwal, Pankaj K.
907:Hamiltonian cycles
825:
638:
616:to the graph of a
397:
382:
349:
344:
281:
276:
195:
190:
127:
122:
1427:978-0-8218-3458-9
1367:978-0-8186-7183-8
1099:Fox, Sue (2011),
1025:visibility graphs
858:Cartesian product
808:
664:complete coloring
662:: one can find a
656:achromatic number
417:
416:
340:
272:
186:
118:
1563:
1537:
1536:
1510:
1479:
1438:
1412:
1406:
1398:
1378:
1343:
1328:Ars Combinatoria
1324:
1306:
1282:
1257:
1235:
1205:; Debowsky, M.;
1197:
1188:
1141:
1135:
1129:
1122:
1116:
1115:
1096:
1090:
1084:
1078:
1072:
1066:
1060:
1015:circulant graphs
1012:distance-regular
974:Johnson’s graphs
923:
885:
878:
855:
847:complement graph
834:
832:
831:
826:
821:
817:
815:
814:
813:
807:
800:
784:
716:
709:
687:
661:
653:
599:
595:
587:
572:
563:
556:
528:perfect matching
518:
508:
501:
494:
467:
439:undirected graph
433:
406:
404:
403:
398:
395:
390:
358:
356:
355:
350:
348:
345:
341:
338:
296:Chromatic number
290:
288:
287:
282:
280:
277:
273:
270:
204:
202:
201:
196:
194:
191:
187:
184:
136:
134:
133:
128:
126:
123:
119:
116:
68:
49:
31:
19:
1571:
1570:
1566:
1565:
1564:
1562:
1561:
1560:
1541:
1540:
1522:
1521:
1518:
1483:
1441:
1428:
1418:Graph Colorings
1415:
1399:
1382:
1368:
1347:
1322:
1310:
1286:
1239:
1201:
1153:
1150:
1145:
1144:
1136:
1132:
1123:
1119:
1113:
1098:
1097:
1093:
1085:
1081:
1073:
1069:
1061:
1057:
1052:
1040:order dimension
993:Matoušek (1996)
984:
963:
956:
949:
942:
934:greedy coloring
919:
895:
880:
876:
870:
864:
862:complete graphs
850:
789:
779:
764:
760:
737:
736:
711:
704:
685:
676:
667:
659:
644:
630:
606:
597:
589:
586:
577:
571:
565:
562:
558:
554:
547:
542:
510:
507:
503:
500:
496:
492:
483:
476:
469:
465:
456:
449:
442:
428:
377:
376:
343:
342:
335:
329:
328:
317:
306:
301:
300:
275:
274:
267:
261:
260:
249:
243:
242:
231:
220:
215:
214:
189:
188:
181:
175:
174:
163:
152:
147:
146:
121:
120:
113:
107:
106:
95:
84:
79:
78:
59:
44:
34:
17:
12:
11:
5:
1569:
1567:
1559:
1558:
1556:Regular graphs
1553:
1543:
1542:
1539:
1538:
1517:
1516:External links
1514:
1513:
1512:
1494:(7): 777–784,
1481:
1455:(1): 333–344,
1443:Matoušek, JiĹ™Ă
1439:
1426:
1413:
1384:Johnson, D. S.
1380:
1366:
1345:
1308:
1284:
1248:(2): 404–416,
1237:
1219:(1–3): 37–43,
1203:Archdeacon, D.
1199:
1179:(1): 347–365,
1149:
1146:
1143:
1142:
1130:
1117:
1111:
1091:
1079:
1067:
1054:
1053:
1051:
1048:
980:
976:with notation
970:Johnson (1974)
961:
954:
947:
940:
930:
929:
912:ménage problem
894:
891:
874:
868:
836:
835:
824:
820:
812:
806:
803:
799:
795:
792:
788:
783:
777:
774:
771:
768:
763:
759:
756:
753:
750:
747:
744:
681:
672:
629:
626:
605:
602:
581:
569:
560:
552:
545:
540:tensor product
536:complete graph
505:
498:
488:
481:
474:
461:
454:
447:
415:
414:
408:
407:
394:
389:
385:
374:
370:
369:
364:
360:
359:
347:
336:
334:
331:
330:
327:
324:
321:
318:
316:
313:
312:
309:
298:
292:
291:
279:
268:
266:
263:
262:
259:
256:
253:
250:
248:
245:
244:
241:
238:
235:
232:
230:
227:
226:
223:
212:
206:
205:
193:
182:
180:
177:
176:
173:
170:
167:
164:
162:
159:
158:
155:
144:
138:
137:
125:
114:
112:
109:
108:
105:
102:
99:
96:
94:
91:
90:
87:
76:
70:
69:
57:
51:
50:
42:
36:
35:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1568:
1557:
1554:
1552:
1549:
1548:
1546:
1534:
1533:
1528:
1527:"Crown Graph"
1525:
1520:
1519:
1515:
1509:
1505:
1501:
1497:
1493:
1489:
1488:
1482:
1478:
1474:
1470:
1466:
1462:
1458:
1454:
1450:
1449:
1444:
1440:
1437:
1433:
1429:
1423:
1419:
1414:
1410:
1404:
1397:
1393:
1389:
1385:
1381:
1377:
1373:
1369:
1363:
1359:
1355:
1351:
1346:
1342:
1338:
1334:
1330:
1329:
1321:
1317:
1313:
1309:
1305:
1301:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1265:
1261:
1256:
1255:10.1.1.1.5562
1251:
1247:
1243:
1238:
1234:
1230:
1226:
1222:
1218:
1214:
1213:
1208:
1204:
1200:
1196:
1192:
1187:
1182:
1178:
1174:
1173:
1168:
1167:Suri, Subhash
1164:
1163:Aronov, Boris
1160:
1156:
1152:
1151:
1147:
1139:
1138:Kubale (2004)
1134:
1131:
1127:
1121:
1118:
1114:
1112:9781118051375
1108:
1104:
1103:
1095:
1092:
1088:
1083:
1080:
1076:
1071:
1068:
1064:
1059:
1056:
1049:
1047:
1045:
1041:
1037:
1033:
1028:
1026:
1022:
1018:
1016:
1013:
1009:
1004:
1002:
998:
994:
990:
988:
983:
979:
975:
971:
967:
960:
953:
946:
939:
935:
927:
922:
917:
916:
915:
913:
908:
904:
900:
892:
890:
888:
884:
877:
867:
863:
859:
854:
848:
843:
841:
822:
818:
801:
797:
793:
786:
775:
772:
769:
766:
761:
754:
748:
742:
735:
734:
733:
731:
727:
722:
720:
714:
708:
701:
699:
695:
691:
684:
680:
675:
671:
665:
657:
651:
647:
643:
642:pronic number
634:
627:
625:
623:
619:
615:
611:
603:
601:
593:
584:
580:
576:
568:
555:
548:
541:
537:
533:
529:
525:
520:
517:
513:
491:
487:
480:
473:
464:
460:
453:
446:
440:
436:
432:
426:
422:
413:
409:
392:
387:
383:
375:
371:
368:
365:
361:
332:
325:
322:
319:
314:
307:
299:
297:
293:
264:
257:
254:
251:
246:
239:
236:
233:
221:
213:
211:
207:
178:
171:
168:
165:
153:
145:
143:
139:
110:
103:
100:
97:
85:
77:
75:
71:
66:
62:
58:
56:
52:
48:
43:
41:
37:
30:
25:
20:
1530:
1491:
1485:
1452:
1446:
1417:
1387:
1349:
1332:
1326:
1295:
1245:
1241:
1216:
1210:
1176:
1170:
1133:
1125:
1120:
1101:
1094:
1082:
1070:
1058:
1043:
1031:
1029:
1019:
1005:
997:metric space
991:
987:FĂĽrer (1995)
981:
977:
973:
965:
958:
951:
944:
937:
931:
902:
896:
893:Applications
887:rook's graph
882:
872:
865:
852:
844:
837:
723:
712:
706:
702:
682:
678:
673:
669:
649:
645:
639:
607:
591:
582:
578:
566:
550:
543:
521:
515:
511:
489:
485:
478:
471:
462:
458:
451:
444:
430:
424:
421:graph theory
418:
64:
60:
46:
1335:: 229–246,
1312:Erdős, Paul
425:crown graph
22:Crown graph
1545:Categories
1207:Dinitz, J.
1159:Alon, Noga
1148:References
628:Properties
614:isomorphic
573:, or as a
363:Properties
1532:MathWorld
1477:121050316
1376:195870010
1250:CiteSeerX
899:etiquette
805:⌋
791:⌊
776:≤
770:∣
743:σ
690:symmetric
620:. In the
538:, as the
509:whenever
339:otherwise
271:otherwise
237:≤
229:∞
185:otherwise
169:≤
161:∞
117:otherwise
101:≤
93:∞
1403:citation
1318:(1980),
604:Examples
435:vertices
373:Notation
142:Diameter
40:Vertices
1508:2009391
1469:1380650
1436:2074481
1396:0389644
1341:0582295
1304:0657202
1280:9817850
1272:1869259
1233:2071894
1195:1298916
924:in the
921:A094047
1506:
1475:
1467:
1434:
1424:
1394:
1374:
1364:
1339:
1302:
1278:
1270:
1252:
1231:
1193:
1109:
1042:
654:. Its
437:is an
74:Radius
1473:S2CID
1372:S2CID
1323:(PDF)
1276:S2CID
1050:Notes
1038:with
849:of a
610:cycle
534:of a
484:, …,
457:, …,
210:Girth
55:Edges
1422:ISBN
1409:link
1362:ISBN
1107:ISBN
926:OEIS
881:2 Ă—
845:The
703:The
692:and
652:– 1)
618:cube
594:– 1)
564:and
468:and
67:– 1)
1496:doi
1457:doi
1354:doi
1260:doi
1221:doi
1217:284
1181:doi
1006:As
897:In
860:of
758:min
715:– 2
658:is
502:to
427:on
419:In
1547::
1529:.
1504:MR
1502:,
1492:24
1490:,
1471:,
1465:MR
1463:,
1453:93
1451:,
1432:MR
1430:,
1405:}}
1401:{{
1392:MR
1370:,
1360:,
1337:MR
1331:,
1325:,
1314:;
1300:MR
1274:,
1268:MR
1266:,
1258:,
1246:41
1244:,
1229:MR
1227:,
1215:,
1191:MR
1189:,
1177:12
1175:,
1165:;
1161:;
1157:;
1046:.
1017:.
1003:.
985:.
957:,
950:,
943:,
889:.
871:â–˘
842:.
696:.
686:}
677:,
585:,1
549:Ă—
519:.
514:â‰
493:}
477:,
466:}
450:,
1535:.
1511:.
1498::
1480:.
1459::
1411:)
1379:.
1356::
1344:.
1333:9
1307:.
1283:.
1262::
1236:.
1223::
1198:.
1183::
1140:.
1128:.
1126:n
1089:.
1077:.
1065:.
1044:n
1032:n
982:n
978:J
966:n
962:1
959:v
955:1
952:u
948:0
945:v
941:0
938:u
928:)
903:n
883:n
875:n
873:K
869:2
866:K
853:n
851:2
823:,
819:}
811:)
802:2
798:/
794:k
787:k
782:(
773:n
767:k
762:{
755:=
752:)
749:n
746:(
713:n
707:n
705:2
683:i
679:v
674:i
670:u
668:{
660:n
650:n
648:(
646:n
598:n
592:n
590:(
583:n
579:H
570:2
567:K
561:n
559:K
553:2
551:K
546:n
544:K
516:j
512:i
506:j
504:v
499:i
497:u
490:n
486:v
482:2
479:v
475:1
472:v
470:{
463:n
459:u
455:2
452:u
448:1
445:u
443:{
431:n
429:2
393:0
388:n
384:S
333:2
326:1
323:=
320:n
315:1
308:{
265:4
258:3
255:=
252:n
247:6
240:2
234:n
222:{
179:3
172:2
166:n
154:{
111:3
104:2
98:n
86:{
65:n
63:(
61:n
47:n
45:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
