In this paper, we introduce two new types of labelings of graphs using Fibonacci numbers, namely, Fibonacci graceful labelings and Super Fibonacci graceful labelings. We discuss the existence and non-existence of Fibonacci and Super Fibonacci graceful labelings for certain classes of graphs. Also, we discuss the Fibonacci gracefulness of disjoint union of Super Fibonacci graceful graphs, pendant edge extension of Super Fibonacci graceful graphs, and amalgamation of Super Fibonacci graceful graphs. Finally, we compare the graceful graphs with Fibonacci graceful graphs.

Let the columns of a \(p \times q\) matrix \(M\) over any ring be partitioned into \(n\) blocks, \(M = [M_1, \ldots, M_n]\). If no \(p \times p\) submatrix of \(M\) with columns from distinct blocks \(M_{i}\) is invertible, then there is an invertible \(p \times p\) matrix \(Q\) and a positive integer \(m \leq p\) such that \([QM_1, \ldots, QM_n]\) is in reduced echelon form and in all but at most \(m – 1\) blocks \(QM_i\) the last \(m\) entries of each column are either all zero or they include a non-zero non-unit.

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) \(G\) with vertex set \(V(G)\) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex \(x \in V(G)\) such that \(G – x\) is a tree (respectively, forest). In this paper, we determine the largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs. We also characterize those extremal graphs achieving these values.

In \(2004\), Fischermann et al. \([2]\) generalized bound polysemy to competition polysemy by using digraphs instead of posets. They provided a characterization of competition polysemic pairs and a characterization of the connected graphs \(G\) for which there exists a tree \(T\) such that \((G,T)\) is competition polysemic. In this paper, we continue to study the competition polysemy and characterize the connected graphs \(G\) for which there exists a triangle-free unicyclic graph \(G’\) such that \((G,G’)\) is competition polysemic. Furthermore,we generalize competition polysemy to \(m\)-competition polysemy and
prove a characterization of \(m\)-competition polysemic pairs.

A diagonally switchable \(\lambda\)-fold \(4\)-cycle system of order \(n\), briefly DS4CS\((n, \lambda)\), is a \(\lambda\)-fold \(4\)-cycle system in which by replacing each \(4\)-cycle \((a,b,c,d)\) covering pairs \(ab, bc, cd, da\) by either of the \(4\)-cycles \((a,c,b,d)\) or \((a,d,c,b)\) another \(\lambda\)-fold \(4\)-cycle system is obtained. In \([3]\) Adams, Bryant, Grannell, and Griggs proved that a DS4CS\((n, 1)\) exists if and only if \(n \equiv 1 \pmod{8}\), \(n \geq 17\) with the possible exception of \(n = 17\). In this paper we prove that for \(\lambda \geq 2\) the necessary conditions for the existence of a \(A\)-fold \(4\)-cycle system of order \(7\) are also sufficient for the existence of a DS4CS\((n, \lambda)\) except for \((n, \lambda) = (5, 2)\).

In this paper, we consider the relationships between the sums of the generalized order-\(k\) Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.