Star Polynomial of Special Graphs, Their Sums, and Compositions

Abstract

Introduction

The idea of graph polynomials is a growing field of research in graph theory and has proved successful in its application particularly in dynamic research in the graph. In Algebraic Graph Theory, graph polynomials give information about graphs and their properties. They are studied extensively because of their wide range of applications in chemistry. Several graph polynomials are defined to represent a graph. This paper focused on star polynomials, which are defined using star graphs. Stars are described as the only connected graphs in which at most one vertex has degree greater than one. In the field of mathematics “star” is used in numerous ways. A star denoted by Sk is the complete bipartite graph K1, k: a tree with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1). This study will present the association of some special graphs, their sums, and compositions to their star polynomial representations.

Methods

This study used a theoretical research design. Specifically, the mathematical investigation was used to obtain results or information concerning the updates and status of the phenomena in describing the presented special graphs. It focused on the star polynomial of joins and compositions of special graphs, such as paths, cycles, complete graphs, wheels, the sum of paths, and composition of paths.

Results

The following are the salient findings of the study:1. Let m and n be an integer of order m≥1 and n≥2. Then S(Pm+Pn, x)=[n(m+1)+(m-2)]x^2+∑(i=2)^n[(m-2)(n+2Ci))+2((n+1Ci))+(n-2)((m+2Ci))+2((m+1Ci))] x^(i+1)2. Let m and n be an integer of order m≥2 and n≥2. Then S(Pm [Pn ], x)=[(m-1) n^2+m(n-1)]x^2+∑(i=2)^n[(m-2)(n-2)((2(n+1)Ci))+2(m-2)((2n+1Ci))+2(n-2)((n+2Ci))+4((n+1Ci))] x^(i+1)

Discussions

In formulating star polynomial of special graphs, the researcher used concepts of algebra, combinatorial mathematics and graph theory to obtain star polynomial of G, denoted by S(G,x) and the order of maximum induced star denoted by ζ(G). The order of the maximum induced star subgraphs denoted by ζ(Pm+Pn ) is equal to the number of vertices incident to the vertex-center plus one. The order of the maximum induced star subgraph is ζ(P2 [Pn])=2n when n=2 and n+ when n≥ . The ζ(P3 [Pn ]) is 3n when n=2 and 2n+ when n≥ . The ζ(P4 [Pn ]), ζ(P5 [Pn ]) and ζ(P6 [Pn ]) are also 3n when n=2 and 2n+ when n≥ .