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.