Monochromatic Fibonacci Numbers of Graphs

Abstract

We call the graph $G$ an edge $m$-coloured if its edges are coloured with $m$ colours. A path (or a cycle) is called monochromatic if all its edges are coloured alike. A subset $S\subseteq V(G)$ is independent by monochromatic paths if for every pair of different vertices from $S$ there is no monochromatic path between them. In $[5]$ it was defined the Fibonacci number of a graph to be the number of all independent sets of $G$; recall that $S$ is independent if no two of its vertices are adjacent. In this paper we define the concept of a monochromatic Fibonacci number of a graph which gives the total number of monochromatic independent sets of $G$. Moreover we give the number of all independent by monochromatic paths sets of generalized lexicographic product of graphs using the concept of a monochromatic Fibonacci polynomial of a graph. These results generalize the Fibonacci number of a graph and the Fibonacci polynomial of a graph.