Omega indices of strong and lexicographic products of graphs

Abstract

Background The degree sequence of a graph is the list of its vertex degrees arranged in usually increasing order. Many properties of the graphs realized from a degree sequence can be deduced by means of a recently introduced graph invariant called omega invariant.Methods We used the definitions of the considered graph products together with the list of degree sequences of these graph products for some well-know graph classes. Naturally, the vertex degree and edge degree partitions are used. As the main theme of the paper is the omega invariant, we frequently used the definition and fundamental properties of this very new invariant for our calculations. Also, some algebraic properties of these products are deduced in line with some recent publications following the same fashion.Results In this paper, we determine the degree sequences of strong and lexicographic products of two graphs and obtain the general form of the degree sequences of both products. We obtain a general formula for the omega invariant of strong and lexicographic products of two graphs. The algebraic structures of strong and lexicographic products are obtained. Moreover, we prove that strong and lexicographic products are not distributive over each other.Conclusion We have obtained the general expression for degree sequences of two important products of graphs and a general expression for omega invariants of strong and lexicographic products. Furthermore, we have obtained algebraic structures of strong and lexicographic products in terms of their degree sequences. Also, it has been found that the disruptive property does not hold for strong and lexicographic products.