The Fibonacci cube Γn is the subgraph of the hypercube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube Λn is obtained from Γn by removing vertices that start and end ...with 1. We characterize maximal induced hypercubes in Γn and Λn and deduce for any p≤n the number of maximal p-dimensional hypercubes in these graphs.
The Fibonacci cube
Γ
n
is the subgraph of the hypercube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube
Λ
n
is obtained from
Γ
n
by removing vertices that start and ...end with 1. The eccentricity of a vertex
u
, denoted
e
G
(
u
)
is the greatest distance between
u
and any other vertex
v
in the graph
G
. For a given vertex
u
of
Γ
n
we characterize the vertices
v
such that
d
Γ
n
(
u
,
v
)
=
e
Γ
n
(
u
)
. We then obtain the generating functions of the eccentricity sequences of
Γ
n
and
Λ
n
. As a corollary, we deduce the number of vertices of a given eccentricity.
Let
Γ
n
and
Λ
n
be the
n
-dimensional Fibonacci cube and Lucas cube, respectively. The domination number
γ
of Fibonacci cubes and Lucas cubes is studied. In particular it is proved that
γ
(
Λ
n
)
is ...bounded below by
⌈
L
n
−
2
n
n
−
3
⌉
, where
L
n
is the
n
th Lucas number. The 2-packing number
ρ
of these cubes is also studied. It is proved that
ρ
(
Γ
n
)
is bounded below by
2
2
⌊
lg
n
⌋
2
−
1
and the exact values of
ρ
(
Γ
n
)
and
ρ
(
Λ
n
)
are obtained for
n
≤
10
. It is also shown that
Aut
(
Γ
n
)
≃
Z
2
.
The cube polynomial of a graph is the counting polynomial for the number of induced
k
-dimensional hypercubes (
k
≥0). We determine the cube polynomial of Fibonacci cubes and Lucas cubes, as well as ...the generating functions for the sequences of these cubes. Several explicit formulas for the coefficients of these polynomials are obtained, in particular they can be expressed with convolved Fibonacci numbers. Zeros of the studied cube polynomials are explicitly determined. Consequently, the coefficients sequences of cube polynomials of Fibonacci and Lucas cubes are unimodal.
Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in ...chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube. This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.
Fibonacci and Lucas p-cubes Wei, Jianxin; Yang, Yujun
Discrete Applied Mathematics,
12/2022, Letnik:
322
Journal Article
Recenzirano
The Fibonacci cube Γn is the subgraph of hypercube Qn induced by the binary strings that contain no two consecutive 1s, and the Lucas cube Λn is obtained from Γn by removing vertices that start and ...end with 1. For p≥1, the subgraph of hypercube Qn induced by the strings that contain no 10s1 for all s<p is called the Fibonacci p-cube and denoted by Γnp, and the subgraph of hypercube Qn induced by the strings in which 10s1(s<p) is forbidden in a circular manner is called the Lucas p-cube and denoted by Λnp. Clearly, the Fibonacci cube Γn is Γn1, and the Lucas cube Λn is Λn1. In this paper, first of all, some general properties of Γnp and Λnp, such as the recursive structures, the number of vertices and edges, the diameter, the radius and centers, and the medianicity, are investigated. Furthermore, based on these properties, the Wiener index and cube polynomials of Γnp and Λnp are studied. Finally, some problems and questions are proposed.
The generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all vertices that contain a given binary word f as a factor; the generalized Lucas cube Qd(f↽) is obtained ...from Qd by removing all the vertices that have a circulation containing f as a factor. In this paper the Wiener index of Qd(1s) and the Wiener index of Qd(1s↽) are expressed as functions of the order of the generalized Fibonacci cubes. For the case Qd(111) a closed expression is given in terms of Tribonacci numbers. On the negative side, it is proved that if for some d, the graph Qd(f) (or Qd(f↽)) is not isometric in Qd, then for any positive integer k, for almost all dimensions d′ the distance in Qd′(f) (resp. Qd′(f↽)) can exceed the Hamming distance by k.
Circular embeddability of isometric words Wei, Jianxin; Yang, Yujun; Wang, Guangfu
Discrete mathematics,
October 2020, 2020-10-00, Letnik:
343, Številka:
10
Journal Article
Recenzirano
Let f be a binary word and n≥1. Then the generalized Lucas cube Qn(f↽) is the graph obtained from the n-cube Qn by removing all vertices that have a circulation containing f as a factor. Ilić, ...Klavžar and Rho solved the question for which f and n, Qn(f↽) is an isometric subgraph of Qn for all binary words of length at most five. This question is further studied in this paper. For an isometric word f, sufficient and necessary conditions of Qn(f↽) being an isometric subgraph of Qn are found, and two problems on generalized Lucas cubes are also listed.
PDF
