The vertex degree polynomial of some graph operations

Abstract

Graph polynomials have been developed for measuring structural information of networks using combinatorial graph invariants and for characterizing graphs. Various problems in graph theory and discrete mathematics can be treated and solved in a rather efficient manner by making use of polynomials. Various graph polynomials have been proven useful in discrete mathematics, engineering, information sciences, mathematical chemistry, and related disciplines. The vertex degree polynomial of a graph G is defined as VD(G, x) = Σuv∈E(G) d(u)xd(v)Graph operations are important tools for constructing new graphs, and they play key roles in the design and analysis of networks. In this study, we give exact values of the vertex degree polynomials of graph operations, including the cartesian product, join, corona product and composition of graphs.