20.500.12556/DKUM-66780 Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes Povezanost posplošenih Fibonaccjevih in Lucasovih kock If ▫$f$▫ is a binary word and ▫$d$▫ a positive integer, then the generalized Fibonacci cube ▫$Q_d(f)$▫ is the graph obtained from the ▫$d$▫-cube ▫$Q_d$▫ by removing all the vertices that contain ▫$f$▫ as a factor, while the generalized Lucas cube ▫$Q_d(\stackrel{\leftharpoondown}{f})$▫ is the graph obtained from ▫$Q_d$▫ by removing all the vertices that have a circulation containing ▫$f$▫ as a factor. The Fibonacci cube ▫$\Gamma_d$▫ and the Lucas cube ▫$\Lambda_d$▫ are the graphs ▫$Q_d({11})$▫ and ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫, respectively. It is proved that the connectivity and the edge-connectivity of ▫$\Gamma_d$▫ as well as of ▫$\Lambda_d$▫ are equal to ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all ▫$f$▫ and all ▫$d \le9$▫. Za binarni niz ▫$f$▫ in naravno število ▫$d$▫ pravimo, da je ▫$Q_d(f)$▫ posplošena Fibonaccijeva kocka, pri čemer je to graph pridobljen iz ▫$d$▫-kocke ob odstranitvi vseh vozlišč ki vsebujejo ▫$f$▫ kot podniz. Na podoben način vpeljemo posplošeno Lucasovo kocko ▫$Q_d(\stackrel{\leftharpoondown}{f})$▫ kot graf pridobljen iz ▫$Q_d$▫ z odstranitvijo vozlišč ▫$d$▫-kocke, ki vsebujejo ▫$f$▫ kot cirkularen podniz. S to notoacijo sta Fibonaccijeva kocka ▫$\Gamma_d$▫ in Lucasova kocka ▫$\Lambda_d$▫ grafa ▫$Q_d(11)$▫ in ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫. V članku je dokazano da je vozliščna in povezavna povezanost za ▫$\Gamma_d$▫ in ▫$\Lambda_d$▫ enaka ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. Postavljeno je tudi vprašanje, ali je povezanost posplošenih Fibonaccijevih in Lucasovih kock enaka minimalni stopnji. Slednje je bilo preverjeno z računalnikom za ▫$d \le 9$▫ in vse možne ▫$f$▫. Fibonacci cube Lucas cube generalized Fibonacci cube generalized Lucas cube connectivity combinatorics on words Fibonaccijeva kocka Lucasova kocka posplošena Lucasova kocka posplošena Fibonaccijeva kocka povezanost kombinatorika besed true true true Discrete Mathematics & Theoretical Computer Science Angleški jezik Slovenski jezik Znanstveno delo 2017-07-10 11:00:39 2017-07-10 11:01:43 2026-01-13 13:27:59 2019-07-11 15:58:41 2015 0 0 Str. 79-88 št. 1 Letn. 17 2015 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2014-10-01 2015-01-28 2015-02-04 1365-8050 519.17:004 8089433 17220697 1365-8050 URN:SI:UM:DK:0XCNAHN9 Discrete_Mathematics_&_Theoretical_Computer_Science_2015_Azarija_et_al._Connectivity_of_Fibonacci_cubes,_Lucas_cubes,_and_generalized_cu.pdf Discrete_Mathematics_&_Theoretical_Computer_Science_2015_Azarija_et_al._Connectivity_of_Fibonacci_cubes,_Lucas_cubes,_and_generalized_cu.pdf 1 05275ACF191765822279C45779297063 1e84f62d57fdefc726143f42df1d6680011063329ac5021eb170ffb0db6932f9 63171631-7c0e-11eb-bb7a-00155d0001ca 20.500.12556/dkum/a74b33cb-763b-4c5f-97e8-596f10d3a5dc https://dk.um.si/Dokument.php?lang=slv&id=113942 http://dmtcs.episciences.org/2115 1 https://dk.um.si/Dokument.php?lang=slv&id=113941 Fakulteta za naravoslovje in matematiko 0 0 0