The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of ...the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
Graph Theory
If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a ...factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γd and the Lucas cube Λd are the graphs Qd(11) and Qd(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γd as well as of Λd are equal to ⌊ d+2 / 3⌋. 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≤9.
A digraph D is oriented if it does not contain 2-cycles. If an oriented digraph D has a directed eulerian path, it is an oriented eulerian digraph. In this paper, when an oriented eulerian digraph D ...has minimum out-degree 2 and a diameter d, we find the minimum order of D. In addition, when D is 2-regular with diameter 4rn （m≥2）, we classify the extremal cases.
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.
Generalized Fibonacci cube Qd(f) is introduced as the graph obtained from the d-cube Qd by removing all vertices that contain a given binary string f as a substring. In this notation, the Fibonacci ...cube Γd is Qd(11). The question whether Qd(f) is an isometric subgraph of Qd is studied. Embeddable and non-embeddable infinite series are given. The question is completely solved for strings f of length at most five and for strings consisting of at most three blocks. Several properties of the generalized Fibonacci cubes are deduced. Fibonacci cubes are, besides the trivial cases Qd(10) and Qd(01), the only generalized Fibonacci cubes that are median closed subgraphs of the corresponding hypercubes. For admissible strings f, the f-dimension of a graph is introduced. Several problems and conjectures are also listed.
In 1977, Ganter and Teirlinck proved that any
2
t
×
2
t
matrix with
2
t
nonzero elements can be partitioned into four submatrices of order
t
of which at most two contain nonzero elements. In 1978, ...Kramer and Mesner conjectured that any
m
t
×
n
t
matrix with
k
t
nonzero elements can be partitioned into
m
n
submatrices of order
t
of which at most
k
contain nonzero elements. In 1995, Brualdi et al. showed that this conjecture is true if
m
=
2
,
k
≤
3
or
k
≥
m
n
−
2
. They also found a counterexample of this conjecture for
m
=
4
,
n
=
4
,
k
=
6
and
t
=
2
. When
t
=
2
, Rho showed that this conjecture is true if
k
≤
5
. When
t
=
2
and
m
=
3
, we show that this conjecture is true if
k
=
6
or
n
≤
3
. As a result, we show that when
t
=
2
, this conjecture is true if
k
=
m
n
−
3
also.
The generalized Fibonacci cube Qh(f) is the graph obtained from the h-cube Qh by removing all vertices that contain a given binary string f as a substring. In particular, the vertex set of the 3rd ...order generalized Fibonacci cube Qh(111) is the set of all binary strings b1b2 ...bh containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
The channel assignment problem (CAP) which finds an efficient assignment of channels to the transmitters of a wireless network is applicable to cellular mobile system (CMS). There are lots of results ...on CAP for CMS where the channel separation constraint is represented by a symmetric matrix or a graph. In particular, the Philadelphia instances and the 49-cell system are benchmark CAP for CMS and are treated in many papers. The distance multi-labelling (DM) problem on a graph with weighted vertices is an effective mathematical model of CAP for CMS in which a CMS is represented by a graph with weighted vertices, where a vertex corresponds to a cell with the number of calls on it as its weight. A DM on a graph with weighted vertices is an assignment of a set of non-negative numbers to each vertex. These numbers, which are called labels, represent the channels assigned to the demand calls in each cell. DM is a generalisation of both distance labelling and graph multi-colouring. In this study, the author introduce a new method called the layering method to find a DM on a graph with weighted vertices. Using this method, we obtain optimal DM for two Philadelphia instances. For each of them, the authors obtain a DM according to the range of separation conditions, and it includes known optimal results which are individually obtained under one separation condition.
PDF
