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.

Let \(G\) be a graph. Let \(g(x)\) and \(f(x)\) be two nonnegative integer-valued functions defined on \(V(G)\) with \(g(x) \leq f(x)\) for any \(x \in V(G)\). A spanning subgraph \(F\) of \(G\) is called a fractional \((g, f)\)-factor if \(g(x) \leq d_G^h(x) \leq f(x)\) for all \(x \in V(G)\), where \(d_G^h(x) = \sum_{e \in E_x} h(e)\) is the fractional degree of \(x \in V(F)\) with \(E_x = \{e : e = xy \in E(G)\}\). A graph \(G\) is said to be fractional \((g, f, n)\)-critical if \(G – N\) has a fractional \((g, f)\)-factor for each \(N \subseteq V(G)\) with \(|N| = n\). In this paper, several sufficient conditions in terms of stability number and degree for graphs to be fractional \((g, f, n)\)-critical are given. Moreover, we show that the results in this paper are best possible in some sense.

The modified Zagreb indices are important topological indices in mathematical chemistry. In this paper, we study the modified Zagreb indices of disjunctions and symmetric differences.

Given a graph \(G\) and a non-negative integer \(g\), the \(g\)-extra-connectivity of \(G\) (written \(\kappa_g(G)\)) is the minimum cardinality of a set of vertices of \(G\), if any, whose deletion disconnects \(G\), and every remaining component has more than \(g\) vertices. The usual connectivity and superconnectivity of \(G\) correspond to \(\kappa_0(G)\) and \(\kappa_1(G)\), respectively. In this paper, we determine \(\kappa_g(P_{n_1} \times P_{n_2} \times \cdots \times P_{n_s})\) for \(0 \leq g \leq s\), where \(\times\) denotes the Cartesian product of graphs. We generalize \(\kappa_g(Q_n)\) for \(0 \leq g \leq n\), \(n \geq 4\), where \(Q_n\) denotes the \(n\)-cube.

A graph labeling is an assignment of integers (labels) to the vertices and/or edges of a graph. Within vertex labelings, two main branches can be distinguished: difference vertex labelings that associate each edge of the graph with the difference of the labels of its endpoints. Graceful and edge-antimagic vertex labelings correspond to these branches, respectively. In this paper, we study some connections between them. Indeed, we study the conditions that allow us to transform any \(a\)-labeling (a special case of graceful labeling) of a tree into an \((a, 1)\)- and \((a, 2)\)-edge antimagic vertex labeling.