308:. More specifically, there exists a path that obeys the partition described above: it visits the nodes with first bit 0 and the nodes with first bit 1 in two contiguous subsequences. Within these two subsequences, the path can be constructed recursively by the same rule, linking the two subsequences at the ends of the subsequences at which the second bit is 0. Thus, e.g., in the Fibonacci cube of order 4, the sequence constructed in this way is (0100-0101-0001-0000-0010)-(1010-1000-1001), where the parentheses demark the subsequences within the two subgraphs of the partition. Fibonacci cubes with an even number of nodes greater than two have a
184:
159:
280:
may be given a partial order in which one independent set is less than another if they differ by removing elements from one side of the bipartition and adding elements to the other side of the bipartition; with this order, the independent sets form a distributive lattice, and applying this
322:
of
Fibonacci cubes. Because these graphs are bipartite and have Hamiltonian paths, their maximum independent sets have a number of vertices that is equal to half of the number of vertices in the whole graph, rounded up to the nearest integer. The diameter of a Fibonacci cube of order
372:, both proportional to the logarithm of the number of vertices, and the ability of the network to be partitioned into smaller networks of the same type allows it to be split among multiple parallel computation tasks. Fibonacci cubes also support efficient protocols for
110:, in such a way that two vertices are adjacent whenever their labels differ in a single bit. However, in a Fibonacci cube, the only labels that are allowed are bitstrings with no two consecutive 1 bits. If the labels of the hypercube are interpreted as
220:
in the path itself; two
Fibonacci cube vertices are adjacent if the cliques or independent sets that they represent differ by the addition or removal of a single element. Therefore, like other simplex graphs, Fibonacci cubes are
852:
433:
show, hydrocarbons formed by chains of hexagons, linked edge-to-edge with no three adjacent hexagons in a line, have resonance graphs that are exactly the
Fibonacci graphs. More generally
664:
364:. As a communications network, the Fibonacci cube has beneficial properties similar to those of the hypercube: the number of incident edges per vertex is at most
429:
may be described as subgraphs of a hexagonal tiling of the plane, and the resonance graph describes possible double-bond structures of these molecules. As
918:
449:
based on the k-th order
Fibonacci numbers, which were later further extended to a larger class of networks called the Linear Recursive Networks by
458:
1040:
1162:
662:
Cong, B.; Zheng, S. Q.; Sharma, S. (1993), "On simulations of linear arrays, rings and 2D meshes on
Fibonacci cube networks",
63:
in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in
241:
465:
of vertices defined from the
Fibonacci cube by forbidding a 1 bit in both the first and last positions of each bitstring;
699:
Dedó, Ernesto; Torri, Damiano; Salvi, Norma
Zagaglia (2002), "The observability of the Fibonacci and the Lucas cubes",
850:
Hsu, W.-J.; Chung, M. J.; Das, A. (1997), "Linear recursive networks and their applications in distributed systems",
816:
681:
233:
of the three labels; if each of the three labels has no two consecutive 1 bits, the same is true of their majority.
276:> ... There is also an alternative graph-theoretic description of the same lattice: the independent sets of any
941:
Munarini, Emanuele; Salvi, Norma
Zagaglia (2002), "Structural and enumerative properties of the Fibonacci cubes",
426:
701:
457:
modified the second order
Fibonacci cubes based on different initial conditions. Another related graph is the
217:
79:
932:
341:
showed that it is possible to test whether a graph is a
Fibonacci cube in time near-linear in its size.
1167:
1005:
1172:
377:
177:
437:
described the class of planar bipartite graphs that have Fibonacci cubes as their resonance graphs.
1003:
Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers",
297: − 1 (the nodes with labels beginning with a 0 bit) and a Fibonacci cube of order
834:
Hsu, W.-J.; Page, C. V.; Liu, J.-S. (1993), "Fibonacci cubes: a class of self-similar graphs",
530:
calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while
873:
Klavžar, Sandi (2005), "On median nature and enumerative properties of Fibonacci-like cubes",
402:
387:
249:
229:. The median of any three vertices in a Fibonacci cube may be found by computing the bitwise
213:
64:
56:
1144:
1018:
770:
747:
654:
418:
237:
87:
8:
1055:
923:
836:
757:
641:
319:
281:
construction to a path graph results in the lattice associated with the Fibonacci cube.
1084:
1026:
991:
973:
822:
687:
361:
176: − 1; the bitstrings corresponding to these numbers are given by their
955:
755:
Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices",
715:
812:
738:
677:
309:
230:
995:
826:
1130:
1105:
1076:
983:
964:
Propp, James (1997), "Generating random elements of finite distributive lattices",
950:
882:
861:
804:
787:
733:
710:
669:
391:
357:
305:
205:
115:
75:
52:
36:
1088:
691:
1140:
1014:
766:
743:
650:
277:
48:
724:
Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset",
1135:
887:
71:
1080:
469:
investigated the coloring properties of both Fibonacci cubes and Lucas cubes.
1156:
897:
673:
201:
111:
44:
911:(1150), Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics
212:-vertex path graph. That is, each vertex in the Fibonacci cube represents a
1041:"Optimal deadlock-free routing and broadcasting on Fibonacci cube networks"
462:
395:
245:
226:
222:
166:
The nodes of such a network may be assigned consecutive integers from 0 to
24:
20:
1117:
Zhang, Heping; Ou, Lifeng; Yao, Haiyuan (2009), "Fibonacci-like cubes as
808:
1067:
Taranenko, A.; Vesel, A. (2007), "Fast recognition of Fibonacci cubes",
978:
83:
1109:
865:
791:
778:
Hsu, W.-J. (1993), "Fibonacci cubes: a new interconnection topology",
394:
of certain molecular graphs. For a molecular structure described by a
98:
Like the hypercube graph, the vertices of the Fibonacci cube of order
301: − 2 (the nodes with labels beginning with a 1 bit).
103:
40:
987:
639:
Beck, István (1990), "Partial orders and the Fibonacci numbers",
373:
183:
799:
Hsu, W.-J.; Chung, M. J. (1993), "Generalized Fibonacci cubes",
801:
1993 International Conference on Parallel Processing - ICPP'93
158:
919:"Fibonacci cubes are the resonance graphs of Fibonaccenes"
417:
and whose edges connect pairs of perfect matchings whose
162:
Fibonacci cubes (drawn in red) as subgraphs of hypercubes
413:
is a graph whose vertices describe perfect matchings of
534:
asks for a description of it in an exercise. See also
252:
defined by an alternating sequence of order relations
1098:
IEEE Transactions on Parallel and Distributed Systems
853:
IEEE Transactions on Parallel and Distributed Systems
780:
IEEE Transactions on Parallel and Distributed Systems
114:, the labels in the Fibonacci cube are a subset, the
59:. Fibonacci cubes were first explicitly defined in
453:based on more general forms of linear recursions.
293:may be partitioned into a Fibonacci cube of order
216:in the path complement graph, or equivalently an
1154:
16:Family of graphs based on the Fibonacci sequence
661:
582:
335:/2 (again, rounded up to the nearest integer).
1066:
698:
466:
445:Generalized Fibonacci cubes were presented by
368:/2 and the diameter of the network is at most
338:
70:The Fibonacci cube may be defined in terms of
940:
916:
430:
383:
315:
141:th Fibonacci number, and therefore there are
1096:Wu, Jie (1997), "Extended Fibonacci cubes",
665:Proc. 7th Int. Parallel Processing Symposium
284:
1038:
849:
622:
450:
1116:
1002:
833:
543:
434:
353:
236:The Fibonacci cube is also the graph of a
1134:
977:
954:
886:
737:
714:
47:. Mathematically they are similar to the
898:"Structure of Fibonacci cubes: a survey"
798:
754:
535:
446:
182:
157:
151:vertices in the Fibonacci cube of order
1025:
895:
872:
723:
606:
594:
567:
531:
527:
515:
511:
499:
495:
493:
484:
1155:
917:Klavžar, Sandi; Žigert, Petra (2005),
191:
43:properties derived from its origin in
963:
578:
576:
555:
356:suggested using Fibonacci cubes as a
638:
539:
490:
966:Electronic Journal of Combinatorics
777:
618:
349:
60:
13:
1095:
573:
454:
390:as a description of the family of
14:
1184:
803:, vol. 1, pp. 299–302,
440:
242:Birkhoff's representation theorem
427:Polycyclic aromatic hydrocarbons
612:
583:Cong, Zheng & Sharma (1993)
344:
600:
588:
561:
549:
521:
505:
478:
467:Dedó, Torri & Salvi (2002)
1:
1163:Parametric families of graphs
956:10.1016/S0012-365X(01)00407-1
716:10.1016/S0012-365X(01)00387-9
631:
380:in distributed computations.
187:The Fibonacci cube of order 6
93:
931:(3): 269–276, archived from
739:10.1016/0012-365X(82)90134-0
339:Taranenko & Vesel (2007)
289:The Fibonacci cube of order
196:The Fibonacci cube of order
7:
451:Hsu, Chung & Das (1997)
431:Klavžar & Žigert (2005)
384:Klavžar & Žigert (2005)
318:investigate the radius and
316:Munarini & Salvi (2002)
304:Every Fibonacci cube has a
10:
1189:
1136:10.1016/j.disc.2008.01.053
1039:Stojmenovic, Ivan (1998),
888:10.1016/j.disc.2004.02.023
435:Zhang, Ou & Yao (2009)
409:-transformation graph) of
354:Hsu, Page & Liu (1993)
178:Zeckendorf representations
1121:-transformation graphs",
1081:10.1007/s00453-007-9026-5
1054:: 159–166, archived from
1035:Exercise 3.23a, page 157.
1031:Enumerative Combinatorics
386:apply Fibonacci cubes in
285:Properties and algorithms
240:that may be obtained via
674:10.1109/IPPS.1993.262788
544:Salvi & Salvi (2008)
472:
896:Klavžar, Sandi (2011),
421:is an interior face of
128:labels possible, where
536:Höft & Höft (1985)
447:Hsu & Chung (1993)
188:
163:
388:chemical graph theory
250:partially ordered set
186:
161:
88:distributive lattices
65:chemical graph theory
1123:Discrete Mathematics
1048:Utilitas Mathematica
943:Discrete Mathematics
905:IMFM Preprint Series
875:Discrete Mathematics
809:10.1109/ICPP.1993.95
726:Discrete Mathematics
702:Discrete Mathematics
668:, pp. 748–751,
518:, Theorem 5.1, p.10.
419:symmetric difference
331:, and its radius is
238:distributive lattice
102:may be labeled with
1027:Stanley, Richard P.
924:Fibonacci Quarterly
837:Fibonacci Quarterly
758:Fibonacci Quarterly
642:Fibonacci Quarterly
320:independence number
225:and more generally
192:Algebraic structure
362:parallel computing
189:
164:
33:Fibonacci networks
1168:Fibonacci numbers
1110:10.1109/71.640012
1104:(12): 1203–1210,
1033:, Wadsworth, Inc.
866:10.1109/71.598343
792:10.1109/71.205649
461:, a graph with a
392:perfect matchings
310:Hamiltonian cycle
231:majority function
116:fibbinary numbers
37:undirected graphs
1180:
1173:Network topology
1147:
1138:
1129:(6): 1284–1293,
1112:
1091:
1062:
1060:
1045:
1034:
1021:
1006:Ars Combinatoria
998:
981:
959:
958:
949:(1–3): 317–324,
936:
912:
902:
891:
890:
881:(1–3): 145–153,
868:
845:
829:
794:
773:
750:
741:
719:
718:
694:
657:
626:
623:Stojmenovic 1998
616:
610:
604:
598:
592:
586:
580:
571:
565:
559:
553:
547:
525:
519:
509:
503:
497:
488:
482:
358:network topology
306:Hamiltonian path
206:complement graph
80:independent sets
76:Hamming distance
53:Fibonacci number
49:hypercube graphs
35:are a family of
1188:
1187:
1183:
1182:
1181:
1179:
1178:
1177:
1153:
1152:
1151:
1058:
1043:
979:math.CO/9801066
900:
819:
684:
634:
629:
617:
613:
605:
601:
593:
589:
581:
574:
570:, pp. 4–5.
566:
562:
554:
550:
526:
522:
510:
506:
498:
491:
487:, pp. 3–4.
483:
479:
475:
443:
403:resonance graph
347:
287:
278:bipartite graph
218:independent set
194:
175:
150:
136:
127:
96:
82:of vertices in
72:Fibonacci codes
29:Fibonacci cubes
17:
12:
11:
5:
1186:
1176:
1175:
1170:
1165:
1150:
1149:
1114:
1093:
1064:
1036:
1023:
1000:
961:
938:
914:
893:
870:
860:(7): 673–680,
847:
831:
817:
796:
775:
765:(3): 232–237,
752:
732:(2): 113–122,
721:
709:(1–3): 55–63,
696:
682:
659:
649:(2): 172–174,
635:
633:
630:
628:
627:
611:
607:Klavžar (2011)
599:
595:Klavžar (2011)
587:
572:
568:Klavžar (2011)
560:
548:
532:Stanley (1986)
528:Gansner (1982)
520:
516:Klavžar (2011)
512:Klavžar (2005)
504:
500:Klavžar (2011)
489:
485:Klavžar (2011)
476:
474:
471:
442:
441:Related graphs
439:
346:
343:
286:
283:
193:
190:
174: + 2
170:
149: + 2
145:
132:
126: + 2
122:
112:binary numbers
95:
92:
15:
9:
6:
4:
3:
2:
1185:
1174:
1171:
1169:
1166:
1164:
1161:
1160:
1158:
1146:
1142:
1137:
1132:
1128:
1124:
1120:
1115:
1111:
1107:
1103:
1099:
1094:
1090:
1086:
1082:
1078:
1074:
1070:
1065:
1061:on 2011-07-25
1057:
1053:
1049:
1042:
1037:
1032:
1028:
1024:
1020:
1016:
1012:
1008:
1007:
1001:
997:
993:
989:
988:10.37236/1330
985:
980:
975:
971:
967:
962:
957:
952:
948:
944:
939:
935:on 2007-02-08
934:
930:
926:
925:
920:
915:
910:
906:
899:
894:
889:
884:
880:
876:
871:
867:
863:
859:
855:
854:
848:
843:
839:
838:
832:
828:
824:
820:
818:0-8493-8983-6
814:
810:
806:
802:
797:
793:
789:
785:
781:
776:
772:
768:
764:
760:
759:
753:
749:
745:
740:
735:
731:
727:
722:
717:
712:
708:
704:
703:
697:
693:
689:
685:
683:0-8186-3442-1
679:
675:
671:
667:
666:
660:
656:
652:
648:
644:
643:
637:
636:
624:
620:
615:
608:
603:
596:
591:
584:
579:
577:
569:
564:
557:
552:
545:
541:
537:
533:
529:
524:
517:
513:
508:
501:
496:
494:
486:
481:
477:
470:
468:
464:
460:
456:
452:
448:
438:
436:
432:
428:
424:
420:
416:
412:
408:
404:
400:
397:
393:
389:
385:
381:
379:
375:
371:
367:
363:
359:
355:
351:
342:
340:
336:
334:
330:
326:
321:
317:
313:
311:
307:
302:
300:
296:
292:
282:
279:
275:
271:
267:
263:
259:
255:
251:
247:
243:
239:
234:
232:
228:
227:partial cubes
224:
223:median graphs
219:
215:
211:
207:
203:
202:simplex graph
199:
185:
181:
179:
173:
169:
160:
156:
154:
148:
144:
140:
135:
131:
125:
121:
117:
113:
109:
105:
101:
91:
89:
85:
81:
77:
73:
68:
66:
62:
58:
54:
51:, but with a
50:
46:
45:number theory
42:
38:
34:
30:
26:
22:
1126:
1122:
1118:
1101:
1097:
1075:(2): 81–93,
1072:
1069:Algorithmica
1068:
1056:the original
1051:
1047:
1030:
1010:
1004:
969:
965:
946:
942:
933:the original
928:
922:
908:
904:
878:
874:
857:
851:
841:
835:
800:
783:
779:
762:
756:
729:
725:
706:
700:
663:
646:
640:
614:
602:
590:
563:
556:Propp (1997)
551:
523:
507:
480:
463:Lucas number
444:
422:
414:
410:
406:
398:
396:planar graph
382:
378:broadcasting
369:
365:
348:
345:Applications
337:
332:
328:
324:
314:
303:
298:
294:
290:
288:
273:
269:
265:
261:
257:
253:
246:zigzag poset
235:
209:
197:
195:
171:
167:
165:
152:
146:
142:
138:
137:denotes the
133:
129:
123:
119:
118:. There are
107:
99:
97:
69:
32:
28:
25:graph theory
21:mathematical
18:
1013:: 105–117,
786:(1): 3–12,
540:Beck (1990)
84:path graphs
1157:Categories
972:(2): R15,
844:(1): 65–72
632:References
619:Hsu (1993)
459:Lucas cube
350:Hsu (1993)
106:of length
104:bitstrings
94:Definition
61:Hsu (1993)
39:with rich
455:Wu (1997)
86:, or via
41:recursive
23:field of
1029:(1986),
996:13313188
827:15982621
57:vertices
1145:2510538
1019:2414008
771:0806293
748:0675856
655:1051291
374:routing
244:from a
204:of the
200:is the
19:In the
1143:
1089:993779
1087:
1017:
994:
825:
815:
769:
746:
692:621063
690:
680:
653:
609:, p.9.
597:, p.6.
542:, and
502:, p.3.
401:, the
214:clique
208:of an
27:, the
1085:S2CID
1059:(PDF)
1044:(PDF)
992:S2CID
974:arXiv
901:(PDF)
823:S2CID
688:S2CID
473:Notes
272:<
268:>
264:<
260:>
256:<
813:ISBN
678:ISBN
405:or (
376:and
352:and
248:, a
74:and
1131:doi
1127:309
1106:doi
1077:doi
984:doi
951:doi
947:255
883:doi
879:299
862:doi
805:doi
788:doi
734:doi
711:doi
707:255
670:doi
360:in
327:is
67:.
55:of
31:or
1159::
1141:MR
1139:,
1125:,
1100:,
1083:,
1073:49
1071:,
1052:53
1050:,
1046:,
1015:MR
1011:87
1009:,
990:,
982:,
968:,
945:,
929:43
927:,
921:,
909:49
907:,
903:,
877:,
856:,
842:31
840:,
821:,
811:,
782:,
767:MR
763:23
761:,
744:MR
742:,
730:39
728:,
705:,
686:,
676:,
651:MR
647:28
645:,
621:;
575:^
538:,
514:;
492:^
425:.
312:.
180:.
155:.
90:.
78:,
1148:.
1133::
1119:Z
1113:.
1108::
1102:8
1092:.
1079::
1063:.
1022:.
999:.
986::
976::
970:4
960:.
953::
937:.
913:.
892:.
885::
869:.
864::
858:8
846:.
830:.
807::
795:.
790::
784:4
774:.
751:.
736::
720:.
713::
695:.
672::
658:.
625:.
585:.
558:.
546:.
423:G
415:G
411:G
407:Z
399:G
370:n
366:n
333:n
329:n
325:n
299:n
295:n
291:n
274:f
270:e
266:d
262:c
258:b
254:a
210:n
198:n
172:n
168:F
153:n
147:n
143:F
139:n
134:n
130:F
124:n
120:F
108:n
100:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
