In this paper, we introduce a new kind of generalized Fibonacci polynomials in the distance sense. We give a direct formula, a generating function and matrix generators for these polynomials. Moreover, we present a graph interpretation of these polynomials, their connections with Pascal’s triangle and we prove some identities for them.

We give a total graph interpretation of the numbers of the Fibonacci type. This graph interpretation relates to an edge colouring by monochromatic paths in graphs. We will show that it works for almost all numbers of the Fibonacci type. Moreover, we give the lower bound and the upper bound for the number of all(A1,2A1)-edge colourings in trees.

In this paper we use a graph interpretation of distance Fibonacci polynomials to get a new generalization of Lucas polynomials in the distance sense. We give a direct formula, a generating function and we prove some identities for generalized Lucas polynomials. We present Pascal-like triangles with left-justified rows filled with coefficients of these polynomials, in which one can observe some symmetric patterns. Using a general Q-matrix and a symmetric matrix of initial conditions we also define matrix generators for generalized Lucas polynomials.

In this paper, we introduce new kinds of generalized Padovan sequences and study their properties using number decomposition techniques. In particular, we consider three types of generalized Padovan sequences defined by the same recurrence equation with distinct initial conditions which follows from special number decomposition. Using the number decomposition method, we give their mutual relations and direct binomial formulas for considered sequences. Moreover, we give some combinatorial properties of these sequences and also define their matrix generators.