A study on complement degree and vertex cut polynomials of graphs

Abstract

Graph theory is one of the flourished branches of mathematics that studies the properties of graphs, which are mathematical objects that represent pairwise relationships between objects. The beauty of graph theory lies in its wide scope of applications in fields ranging from network theory, chemistry and operational research to architecture and linguistics. Among various branches of graph theory, graph polynomials are one of the well-studied concepts, as they are used to unveil the structural properties of graphs. Also, the graph polynomials are used for the characterization of graphs. Generally speaking, a graph polynomial is a polynomial assigned to a graph whose coefficients are indicators of some graph-theoretic parameters. In this thesis, we introduce two new graph polynomials named the comple- ment degree polynomial and the vertex cut polynomial of graphs. We derive these two polynomials of some well-known graphs and graph operations.Then we investigate stability, real roots, and the location of roots of complement degree polynomial. Moreover, we define equivalent classes of graphs of these two poly- nomials. Finally, we discuss the complement degree polynomial of some chemical graphs