Journal Details
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English

# Degree Sequence of Graph Operator for some Standard Graphs

###### Accepted: 05 Jun 2019
Journal Details
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English

Topological indices play a very important role in the mathematical chemistry. The topological indices are numerical parameters of a graph. The degree sequence is obtained by considering the set of vertex degree of a graph. Graph operators are the ones which are used to obtain another broader graphs. This paper attempts to find degree sequence of vertex–F join operation of graphs for some standard graphs.

#### Keywords

Introduction

The chemical graph theory is one of the emerging fields of discrete mathematics. In chemical graph theory, molecular topology and mathematical chemistry are source of objectives. A Topological index (connectivity index) is calculated based on the molecular graph of a chemical compound.

Topological indices are numerical parameters of a graph which characterize its topology and are usually graph invariant. Topological indices are used in the development of quantitative structure-activity relationships (QSARs) in which the biological activity or other properties of molecules are correlated with their chemical structures [2], [5].

There are many topological indices which are defined based on vertex degree of a graph such as examples harmonic index, first and second Zagreb indices, first and second multiplicative Zagreb indices, ABC index, Banhatti index, GA index, SDD index, inverse sum index, etc.. Therefore the knowledge of the degree sequence of the graph will give information about chemical properties of the graph. Many researchers have explored degrees of topological indices in their research articles [3].

Let G be a simple connected graph with vertex set V (G) and edge set E(G). A network is simply connected graph having no multiple edges and loops. In a chemical graph, the number of vertices of G adjacent to a given vertex u is the degree of this vertex and will be denoted by du. The concept of degree in graph theory is closely related (but not identical) to the concept of valence in chemistry. For further details on the basics of graph theory article [1] can be of great help.

Many researchers have explored topological indices due to their chemical importance. These indices are actually score functions that capture a variety of physico-chemical properties of chemical compounds such as boiling point, heat formation, heat vaporization, chromatographic retention times, surface tension, vapor pressure etc..

Graph Operators and Degree Sequence

This section emphasizes on the definitions of subdivision of graph, semi-total point graph, semi-total edge graph, total graph and degree sequence. All these are distances based d(u,v) represents the length of the shortest paths between any two vertices connected with each other.

Let G1 and G2 be two graphs having n1, n2 vertices and m1, m2 edges respectively.

A join G1G2 of two graphs G1 and G2 with disjoint vertex sets V (G1) and V (G2) is the graph on the vertex set V (G1) ∪ V (G2) and the edge set E(G1) ∪ E(G2) ∪ {xy | xV (G1), yV (G2)}. Hence, the sum of two graphs is obtained by connecting each vertex of one graph to each vertex of the other graph, while keeping all edges of both graphs [9].

For a connected graph G, define four related graphs S(G), R(G), Q(G) and T (G) as follows:

S(G), [10], is the graph obtained by inserting an additional vertex into each edge of G, i.e., replacing each edge of G by a path of length 2. The graph S(G) is also known as the subdivision graph of G.

R(G), [12], is the graph obtained by adding a new vertex corresponding to each edge of G, and then joining each new vertex to the end vertices of the corresponding edge.

Q(G), [12], is the graph obtained by inserting a new vertex into each edge of G, then joining with edges those pairs of new vertices on adjacent edges of G.

T (G), [4], has the edges and vertices of G as its vertices. Adjacency in T (G) is defined as adjacency or incidency for the corresponding elements of G. The graph T (G) is called the total graph of G.

Let F = {S,R,Q,T }. Let I(G) denote the set of vertices of F(G) which are inserted into each edge of H, so that V (F(G)) = V (G) ∪ I(G). Here we define vertex F–join and edge F–join of graph operations based on the join of two connected graphs G1 and G2, as follows:

VertexF-join of Graphs: [11] Let G1 and G2 be two simple graph the vertex F-join graph of G1 and G2 is denoted by $G1∨˙FG2${G_1}{\dot \vee _F}{G_2} and the graph is obtained from F(G1) and G2 by joining each vertex of G1 to all vertex of G2. The vertex and edge set of $G1∨˙FG2${G_1}{\dot \vee _F}{G_2} is V (F(G1)) ∪ V (G2) and E(G1) ∪ E(G2) ∪ [xy : xV (G1), yV (G2)].

VertexSjoin of graph: Let G1 and G2 be two simple graph the vertex S-join graph of G1 and G2 is denoted by $G1∨˙SG2${G_1}{\dot \vee _S}{G_2} and the graph is obtained from S(G1) and G2 by joining each vertex of V (G1) to all vertex of G2.

VertexRjoin of graph: Let G1 and G2 be two simple graph the vertex S-join graph of G1 and G2 is denoted by $G1∨˙RG2${G_1}{\dot \vee _R}{G_2} and the graph is obtained from R(G1) and G2 by joining each vertex of V (G1) to all vertex of G2.

VertexQjoin of graph: Let G1 and G2 be two simple graph the vertex S-join graph of G1 and G2 is denoted by $G1∨˙QG2${G_1}{\dot \vee _Q}{G_2} and the graph is obtained from Q(G1) and G2 by joining each vertex of V (G1) to all vertex of G2.

VertexTjoin of graph: Let G1 and G2 be two simple graph the vertex S-join graph of G1 and G2 is denoted by $G1∨˙TG2${G_1}{\dot \vee _T}{G_2} and the graph is obtained from T (G1) and G2 by joining each vertex of V (G1) to all vertex of G2.

The degree sequence (DS) of a graph is the sequence of the degrees of the vertices, with these numbers putting in ascending order, with repetitions as needed.

Bollobas introduced the degree sequence in [1]. Tyshkevich et. al. established a relation between degree sequence of a graph and some structural properties of a graph [14], [15].

Equivalently, given an undirected graph, a degree sequence is a monotonic non-increasing sequence of the vertex degrees (valencies) of its graph vertices. The number of degree sequences for a graph of a given order is closely related to graphical partitions.

The notion of degree of a graph is used to study various physical and chemical properties of a graph. It will help us enhance the interest in the research fields for both scientists and chemists.

If di, 1 < i < n are the degrees of the vertices ui of a graph G then the degree sequence(DS) of G is represented as the sequence {d1,d2,···dn}. Also, in many papers, the degree sequence (DS) is taken to be a non-decreasing sequence, whenever possible.

Conversely, a non-negative sequence {d1,d2,···dn} is known as realizable if it is the DS of any graph. It is clear from the definition of DS that different graphs may have the same DS. For example in figure 1 the DS remains the same for both of the graph.

For convenience, if the degree di of the vertex ui appears αi times in the DS of a graph G, then we consider ${d1α1,d2α2,⋯dkαk}$\left\{ {d_1^{{\alpha _1}},d_2^{{\alpha _2}}, \cdots d_k^{{\alpha _k}}} \right\} instead of {d1,d2,···dn} where k ≤ n. Here the members αi are known as the frequencies of the degrees when k = n. That is, when all degrees are different, the degree sequence is called perfect [16].

Let Pn, Kn, Cn, Sn, K(m,n) and rregular be path, complete, cycle, star, complete bipartite, rregular respectively and they are commonly used graph examples in literature survey which can be seen figure 2.

The numbers of vertices, edges and degree sequence of these well known graph classes are given in below table 1.

GVerticesEdgesDegree Sequence
Pnn(n − 1){12, 2n−2}
Knnn(n − 1)/2{(n − 1)n}
Cnnn{2n}
Snn(n − 1){1n−1, (n − 1)1}
K(m,n)m + nmn{mn, nm}
r – regularn(n − 1){rn}

In [12] the authors gave a new version of the Erdos-gallal theorem on realizability of a given degree sequence. In 2008, a new criterion on the same problem was given by Triphati and Tyagi [13]. The same year, H. Kim et. al. gave a necessary and sufficient condition for the same problem [7]. Ivanyi et. al. [6], gave an enumeration of degree sequences of simple graphs. Miller [8] also gave a criterion for the realizability of degree sequence[DS].

Many graph operators can be used to find chemical properties of a graph. In these, subdivision, semi-total point, semi-total edge and total graph operations plays a vital role in the study of physical-chemical properties of a graph. This paper aims to apply the above graph operations for some standard graphs like path, complete, cycle, star, complete bipartite and r–regular graphs.

Results
Theorem 3.1

The degree sequence of all possible$G1∨˙SG2${G_1}{\dot \vee _S}{G_2}of the path, complete, cycle, star, complete bipartite and r–regular graphs are given in the Table.2

Degree sequence of subdivision for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 $G1∨˙SG2${G_1}{\dot \vee _S}{G_2} Px Py {(1 + y)2, (2 + y)x−2, 2x−1, (1 + x)2, (2 + x)y−2} Px Ky {(1 + y)2, (2 + y)x−2, 2x−1, (y − 1 + x)y} Px Cy {(1 + y)2, (2 + y)x−2, 2x−1, (2 + x)y} Px Sy {(1 + y)2, (2 + y)x−2, 2x−1, (1 + x)y−1, (y − 1 + x)} Px K(y, z) {(1 + y + z)2, (2 + y + z)x−2, 2x−1, (y + x)z, (z + x)y} Px r – regular {(1 + y)2, (2 + y)x−2, 2x−1, (r + x)y} Kx Py {(x − 1 + y)x, 2x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(x − 1 + y)(2x), 2x(x−1)/2} Kx Cy {(x − 1 + y)x, 2x(x−1)/2, (2 + x)y} Kx Sy {(x − 1 + y)x, 2x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(x − 1 + y + z)x, 2x(x−1)/2, (x + y)z, (x + z)y} KxCx r – regularPy {(x − 1 + y)x, 2x(x−1)/2, (r + x)y}{(2 + y)x, 2x, (1 + x)2, (2 + x)y−2} Cx Ky {(2 + y)x, 2x, (y − 1 + x)y} Cx Cy {(2 + y)x, 2x, (2 + x)y} Cx Sy {(2 + y)x, 2x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(2 + y)x, 2x, (y + x)z, (z + x)y} Cx r – regular {(2 + y)x, 2x, (r + x)y} Sx Py {(1 + y)x−1, (x − 1 + y), 2x−1, (2 + x)y−2} Sx Ky {(1 + y)x−1, (x − 1 + y), 2x−1, (y − 1 + x)y} Sx Cy {(1 + y)x−1, (x − 1 + y), 2x−1, (2 + x)y} Sx Sy {(1 + y)x−1, (x − 1 + y), 2x−1, (1 + x)y−1, (y − 1 + x)} G1 G2 $G1∨˙SG2${G_1}{\dot \vee _S}{G_2} Sx K(y, z) {(1 + y + z)x−1, (x − 1 + y + z), 2x−1, (z + x)y, (y + x)z} Sx r – regular {(1 + y)x−1, (x − 1 + y), 2x−1, (r + x)y} Kx,y Pz {(x + z)y, (y + z)x, 2xy, (1 + x + y)2(2 + x + y)z−2} Kx,y Kz {(x + z)y, (y + z)x, 2xy, (1 + x + y) (z − 1 + x + y)z} Kx,y Cz {(x + z)y, (y + z)x, 2xy, (2 + x + y)z} Kx,y Sz {(x + z)y, (y + z)x, 2xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(x + z + t)y, (y + z + t)x, 2xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(x + z)y, (y + z)x, 2xy, (r + x + y)z} r – regular Py {(r + y)x, 2rx/2, (1 + x)2, (2 + x)x−2} r – regular Ky {(r + y)x, 2rx/2, (y − 1 + x)y} r – regular Cy {(r + y)x, 2rx/2, (2 + x)y} r – regular Sy {(r + y)x, 2rx/2, (y − 1 + x), (1 + x)y−1} r – regular K(y,z) {(r + y + z)x, 2rx/2, (y + x)z, (z + x)y} r1 – regular r2 – regular {(r1 + y)x, 2r1x/2, (r2 + x)y}
Proof

We prove here only two types of Degree Sequences

$Cx∨˙SPy${C_x}{\dot \vee _S}{P_y}

$Kx∨˙SKy${K_x}{\dot \vee _S}{K_y}

Let DS(Cx) = {2x} and DS(Py) = {12,2y−2}.

There are one set of vertex in cycle and two set of vertices in path. So, after applying subdivision for cycle, we get another set of vertex (one vertex insert in cycle) and joining path.

Therefore, the total number of vertices will be 1 + 2 + 1 = 4 vertices.

The first set of vertex is the vertices in cycle which are connected to every vertex in path, each of which adds (2 + y) to the DS of $Cx∨˙SPy${C_x}{\dot \vee _S}{P_y} .

The second set of vertex are vertices obtained by adding one vertex in every edge in cycle with degree 2, to the DS of $Cx∨˙SPy${C_x}{\dot \vee _S}{P_y} .

The third set of vertices are the two end vertices of degree one in Py which are connected to every vertex in Cx and x vertices in Cx.

The fourth set of vertices are the middle (y − 2) vertices having two degree in Py ; each of them is connected to every vertex in Cx and x vertices in Cx.

Hence, the required degree sequence of $DS(Cx∨˙SPy)={(2+y)x,2x,(1+x)2,(2+x)y−2}.$DS({C_x}{\dot \vee _S}{P_y}) = \left\{ {{{(2 + y)}^x}{{,2}^x},(1 + x{)^2},(2 + x{)^{y - 2}}} \right\}.

Now, Let DS(Kx) = {(x − 1)x} and DS(Ky) = {(y − 1)y}.

The complete graph has only one set of vertices having degree x − 1. So, after applying subdivision for Kx, 2 + 1 = 3 vertices is obtained.

The first two set of vertices are the vertices in Kx. which are connected to every vertex in Ky, each of which adds (x + y − 1) to the DS of $Kx∨˙SKy${K_x}{\dot \vee _S}{K_y} are (x + y − 1)x and (x + y − 1)y.

The third set of vertex is obtained by inserting vertex to each edge in Kx with two degree, since there are x(x − 1)/2 vertices.

Therefore DS of $Kx∨˙SKy${K_x}{\dot \vee _S}{K_y} is 2x(x−1)/2.

Hence, the required degree sequence of $DS(Kx∨˙SKy)={(x+y−1)y,2x(x−1)/2,(x+y−1)x}.$DS({K_x}{\dot \vee _S}{K_y}) = \left\{ {{{(x + y - 1)}^y}{{,2}^{x(x - 1)/2}},(x + y - {{1)}^x}} \right\}.

Theorem 3.2

The degree sequence of all possible$G1∨˙RG2${G_1}{\dot \vee _R}{G_2}of the path, complete, cycle, star, complete bipartite and r–regular graphs are given in the Table.3

Degree Sequence of vertex-R join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 $DS(G1∨˙RG2)$DS({G_1}{\dot \vee _R}{G_2}) Px Py {(2 + y)2, (4 + y)x−2, 2x−1, (1 + x)2, (2 + x)y−2} Px Ky {(2 + y)2, (4 + y)x−2, 2x−1, (x + y − 1)y} Px Cy {(2 + y)2, (4 + y)x−2, 2x−1, (2 + x)y} Px Sy {(2 + y)2, (4 + y)x−2, 2x−1, (1 + x)y−1, (x + y − 1)} Px K(y, z) {(2 + y + z)2, (4 + y + z)x−2, 2x−1, (y + x)z, (z + x)y} Px r – regular {(2 + y)2, (4 + y)x−2, 2x−1, (r + x)y} Kx Py {(2x − 2 + y)x, 2x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(2x − 2 + y)x, 2x(x−1)/2, (x + y − 1)y} Kx Cy {(2x − 2 + y)x, 2x(x−1)/2, (2 + x)y} Kx Sy {(2x − 2 + y)x, 2x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(2x − 2 + y + z)x, 2x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(2x − 2 + y)x, 2x(x−1)/2, (r + x)y} Cx Py {(4 + y)x, 2x, (1 + x)2, (2 + x)y−2} Cx Ky {(4 + y)x, 2x, (y − 1 + x)} Cx Cy {(4 + y)x, 2x, (2 + x)y} Cx Sy {(4 + y)x, 2x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(4 + y + z)x, 2x, (y + x)z, (z + x)y} Cx r – regular {(4 + y)x, 2x, (r + x)y} G1 G2 $DS(G1∨˙RG2)$DS({G_1}{\dot \vee _R}{G_2}) Sx Py {(2 + y)x−1, (2x − 2 + y), 2x−1, (1 + x)2, (2 + x)y−2} Sx Ky {(2 + y)x−1, (2x − 2 + y), 2x−1, (y − 1 + x)y} Sx Cy {(2 + y)x−1, (2x − 2 + y), 2x−1, (2 + x)y} Sx Sy {(2 + y)x−1, (2x − 2 + y), 2x−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(2 + y + z)x−1, (2x − 2 + y + z), 2x−1, (z + x)y, (y + x)z} Sx r – regular {(2 + y)x−1, (2x − 2 + y), 2x−1, (r + x)y} Kx,y Pz {(2x + z)y, (2y + z)x, 2xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(2x + z)y, (2y + z)x, 2xy, (z − 1 + x + y)z} Kx,y Cz {(2x + z)y, (2y + z)x, 2xy, (2 + x + y)z} Kx,y Sz {(2x + z)y, (2y + z)x, 2xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(2x + z + t)y, (2y + z + t)x, 2xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(2x + z)y, (2y + z)x, 2xy, (r + x + y)z} r – regular Py {(2r + y)x, 2rx/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(2r + y)x, 2rx/2, (y − 1 + x)y} r – regular Cy {(2r + y)x, 2rx/2, (2 + x)y} r – regular Sy {(2r + y)x, 2rx/2, (y − 1 + x), (1 + x)y} r – regular K(y, z) {(2r + y + z)x, 2rx/2, (y + x)z, (z + x)y} r1 – regular r2 – regular {(2r1 + y)x, 2r1x/2, (r2 + x)y}
Theorem 3.3

The degree sequence of all possible$G1∨˙QG2${G_1}{\dot \vee _Q}{G_2}of the path, complete, cycle, star, complete bipartite and r-regular graphs are given in the Table.4

Degree Sequence of vertex-Q join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 $DS(G1∨˙QG2)$DS({G_1}{\dot \vee _Q}{G_2}) Px Py {(1 + y)2, (2 + y)x−2, 32, 4(x − 3)2, (1 + x)2, (2 + x)y−2} Px Ky {(1 + y)2, (2 + y)x−2, 32, 4(x − 3), (y − 1 + x)y} Px Cy {(1 + y)2, (2 + y)x−2, 32, 4x−3, (2 + x)y} Px Sy {(1 + y)2, (2 + y)x−2, 32, 4x−3, (1 + x)y−1, (x + y − 1)} G1 G2 $DS(G1∨˙QG2)$DS({G_1}{\dot \vee _Q}{G_2}) Px K(y, z) {(1 + y + z)2, (2 + y + z)x−2, 32, 4x−3, (y + x)z, (z + x)y} Px r – regular {(1 + y)2, (2 + y)x−2, 32, 4x−3, (r + x)y} Kx Py {(x − 1 + y)x, (2x − 2)x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(x − 1 + y)x, (2x − 2)x(x−1)/2, (x + y − 1)y} Kx Cy {(x − 1 + y)x, (2x − 2)x(x−1)/2, (2 + x)y} Kx Sy {(x − 1 + y)x, (2x − 2)x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(x − 1 + y + z)x, (2x − 2)x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(x − 1 + y)x, (2x − 2)x(x−1)/2, (r + x)y} Cx Py {(2 + y)x, 4x, (1 + x)2, (2 + x)y−2} Cx Ky {(2 + y)x, 4x, (y − 1 + x)y} Cx Cy {(2 + y)x, 4x, (2 + x)y} Cx Sy {(2 + y)x, 4x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(2 + y + z)x, 4x, (y + x)z, (z + x)y} Cx r – regular {(2 + y)x, 4x, (r + x)y} Sx Py {(1 + y)x−1, (x − 1 + y), xx−1, (1 + x)2, (2 + x)y−2} Sx Ky {(1 + y)x−1, (x − 1 + y), xx−1, (y − 1 + x)y} Sx Cy {(1 + y)x−1, (x − 1 + y), xx−1, (2 + x)y} Sx Sy {(1 + y)x−1, (x − 1 + y), xx−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(1 + y + z)x−1, (x − 1 + y + z), xx−1, (z + x)y, (y + x)z} Sx r – regular {(1 + y)x−1, (x − 1 + y), xx−1, (r + x)y} Kx,y Pz {(x + z)y, (y + z)x, (x + y)xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(x + z)y, (y + z)x, (x + y)xy, (z − 1 + x + y)z} Kx,y Cz {(x + z)y, (y + z)x, (x + y)xy, (2 + x + y)z} Kx,y Sz {(x + z)y, (y + z)x, (x + y)xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(x + z + t)y, (y + z + t)x, (x + y)xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(x + z)y, (y + z)x, (x + y)xy, (r + x + y)z} r – regular Pz {(r + y)x, (2r)xr/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(r + y)x, (2r)xr/2, (x + y − 1)y} r – regular Cy {(r + y)x, (2r)xr/2, (2 + x)y} r – regular Sy {(r + y)x, (2r)xr/2, (1 + x)y−1, (x + y − 1)} r – regular Ky,z {(r + y + z)x, (2r)xr/2, (x + y)z, (x + z)y} r1 – regular r2 – regular {(r1 + y)x, (2r1)xr1/2, (r − 2 + x)y}
Theorem 3.4

The degree sequence of all possible$G1∨˙TG2${G_1}{\dot \vee _T}{G_2}of the path, complete, cycle, star, complete bipartite and r–regular graphs are given in table 5.

Degree sequence of vertex-T join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs.

 G1 G2 $DS(G1∨˙TG2)$DS({G_1}{\dot \vee _T}{G_2}) Px Py {(2 + y)2, (4 + y)x−2, 32, 4(x − 3), (1 + x)2, (2 + x)y−2} Px Ky {(2 + y)2, (4 + y)x−2, 32, 4(x − 3), (y − 1 + x)y} Px Cy {(2 + y)2, (4 + y)x−2, 32, 4x−3, (2 + x)y} Px Sy {(2 + y)2, (4 + y)x−2, 32, 4x−3, (1 + x)y−1, (x + y − 1)} Px K(y, z) {(2 + y + z)2, (4 + y + z)x−2, 32, 4x−3, (y + x)z, (z + x)y} Px r – regular {(2 + y)2, (4 + y)x−2, 32, 4x−3, (r + x)y} Kx Py {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (x + y − 1)y} Kx Cy {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (2 + x)y} Kx Sy {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(2x − 2 + y + z)x, (2x − 2)x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (r + x)y} Cx Py {(4 + y)x, 4x, (1 + x)2, (2 + x)y−2} Cx Ky {(4 + y)x, 4x, (y − 1 + x)y} Cx Cy {(4 + y)x, 4x, (2 + x)y} Cx Sy {(4 + y)x, 4x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(4 + y + z)x, 4x, (y + x)z, (z + x)y} Cx r – regular {(4 + y)x, 4x, (r + x)y} Sx Py {(2 + y)x−1, (2x − 2 + y), xx−1, (1 + x)2, (2 + x)y−2} Sx Ky {(2 + y)x−1, (2x − 2 + y), xx−1, (y − 1 + x)y} Sx Cy {(2 + y)x−1, (2x − 2 + y), xx−1, (2 + x)y} Sx Sy {(2 + y)x−1, (2x − 2 + y), xx−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(2 + y + z)x−1, (2x − 2 + y + z), xx−1, (z + x)y, (y + x)z} Sx r – regular {(2 + y)x−1, (2x − 2 + y), xx−1, (r + x)y} G1 G2 $DS(G1∨˙TG2)$DS({G_1}{\dot \vee _T}{G_2}) Kx,y Pz {(2x + z)y, (2y + z)x, (x + y)xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(2x + z)y, (2y + z)x, (x + y)xy, (z − 1 + x + y)z} Kx,y Cz {2x + z)y, (2y + z)x, (x + y)xy, (2 + x + y)z} Kx,y Sz {(2x + z)y, (2y + z)x, (x + y)xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(2x + z + t)y, (2y + z + t)x, (x + y)xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular (2x + z)y, (2y + z)x, (x + y)xy, (r + x + y)z r – regular Pz {(2r + y)x, (2r)xr/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(2r + y)x, (2r)xr/2, (x + y − 1)y} r – regular Cy {(2r + y)x, (2r)xr/2, (2 + x)y} r – regular Sy {(2r + y)x, (2r)xr/2, (1 + x)y−1, (x + y − 1)} r – regular Ky,z {(2r + y + z)x, (2r)xr/2, (x + y)z, (x + z)y} r1 – regular r2 – regular {(2r1 + y)x, (2r1)xr1/2, (r − 2 + x)y}
Conclusions

This article concludes with general formulae for degree sequence of a vertex-F join operation for path, complete, cycle, star, complete bipartite and r–regular graphs.

#### Degree Sequence of vertex-R join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 DS(G1∨˙RG2)DS({G_1}{\dot \vee _R}{G_2}) Px Py {(2 + y)2, (4 + y)x−2, 2x−1, (1 + x)2, (2 + x)y−2} Px Ky {(2 + y)2, (4 + y)x−2, 2x−1, (x + y − 1)y} Px Cy {(2 + y)2, (4 + y)x−2, 2x−1, (2 + x)y} Px Sy {(2 + y)2, (4 + y)x−2, 2x−1, (1 + x)y−1, (x + y − 1)} Px K(y, z) {(2 + y + z)2, (4 + y + z)x−2, 2x−1, (y + x)z, (z + x)y} Px r – regular {(2 + y)2, (4 + y)x−2, 2x−1, (r + x)y} Kx Py {(2x − 2 + y)x, 2x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(2x − 2 + y)x, 2x(x−1)/2, (x + y − 1)y} Kx Cy {(2x − 2 + y)x, 2x(x−1)/2, (2 + x)y} Kx Sy {(2x − 2 + y)x, 2x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(2x − 2 + y + z)x, 2x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(2x − 2 + y)x, 2x(x−1)/2, (r + x)y} Cx Py {(4 + y)x, 2x, (1 + x)2, (2 + x)y−2} Cx Ky {(4 + y)x, 2x, (y − 1 + x)} Cx Cy {(4 + y)x, 2x, (2 + x)y} Cx Sy {(4 + y)x, 2x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(4 + y + z)x, 2x, (y + x)z, (z + x)y} Cx r – regular {(4 + y)x, 2x, (r + x)y} G1 G2 DS(G1∨˙RG2)DS({G_1}{\dot \vee _R}{G_2}) Sx Py {(2 + y)x−1, (2x − 2 + y), 2x−1, (1 + x)2, (2 + x)y−2} Sx Ky {(2 + y)x−1, (2x − 2 + y), 2x−1, (y − 1 + x)y} Sx Cy {(2 + y)x−1, (2x − 2 + y), 2x−1, (2 + x)y} Sx Sy {(2 + y)x−1, (2x − 2 + y), 2x−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(2 + y + z)x−1, (2x − 2 + y + z), 2x−1, (z + x)y, (y + x)z} Sx r – regular {(2 + y)x−1, (2x − 2 + y), 2x−1, (r + x)y} Kx,y Pz {(2x + z)y, (2y + z)x, 2xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(2x + z)y, (2y + z)x, 2xy, (z − 1 + x + y)z} Kx,y Cz {(2x + z)y, (2y + z)x, 2xy, (2 + x + y)z} Kx,y Sz {(2x + z)y, (2y + z)x, 2xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(2x + z + t)y, (2y + z + t)x, 2xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(2x + z)y, (2y + z)x, 2xy, (r + x + y)z} r – regular Py {(2r + y)x, 2rx/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(2r + y)x, 2rx/2, (y − 1 + x)y} r – regular Cy {(2r + y)x, 2rx/2, (2 + x)y} r – regular Sy {(2r + y)x, 2rx/2, (y − 1 + x), (1 + x)y} r – regular K(y, z) {(2r + y + z)x, 2rx/2, (y + x)z, (z + x)y} r1 – regular r2 – regular {(2r1 + y)x, 2r1x/2, (r2 + x)y}

#### Degree sequence of subdivision for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 G1∨˙SG2{G_1}{\dot \vee _S}{G_2} Px Py {(1 + y)2, (2 + y)x−2, 2x−1, (1 + x)2, (2 + x)y−2} Px Ky {(1 + y)2, (2 + y)x−2, 2x−1, (y − 1 + x)y} Px Cy {(1 + y)2, (2 + y)x−2, 2x−1, (2 + x)y} Px Sy {(1 + y)2, (2 + y)x−2, 2x−1, (1 + x)y−1, (y − 1 + x)} Px K(y, z) {(1 + y + z)2, (2 + y + z)x−2, 2x−1, (y + x)z, (z + x)y} Px r – regular {(1 + y)2, (2 + y)x−2, 2x−1, (r + x)y} Kx Py {(x − 1 + y)x, 2x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(x − 1 + y)(2x), 2x(x−1)/2} Kx Cy {(x − 1 + y)x, 2x(x−1)/2, (2 + x)y} Kx Sy {(x − 1 + y)x, 2x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(x − 1 + y + z)x, 2x(x−1)/2, (x + y)z, (x + z)y} KxCx r – regularPy {(x − 1 + y)x, 2x(x−1)/2, (r + x)y}{(2 + y)x, 2x, (1 + x)2, (2 + x)y−2} Cx Ky {(2 + y)x, 2x, (y − 1 + x)y} Cx Cy {(2 + y)x, 2x, (2 + x)y} Cx Sy {(2 + y)x, 2x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(2 + y)x, 2x, (y + x)z, (z + x)y} Cx r – regular {(2 + y)x, 2x, (r + x)y} Sx Py {(1 + y)x−1, (x − 1 + y), 2x−1, (2 + x)y−2} Sx Ky {(1 + y)x−1, (x − 1 + y), 2x−1, (y − 1 + x)y} Sx Cy {(1 + y)x−1, (x − 1 + y), 2x−1, (2 + x)y} Sx Sy {(1 + y)x−1, (x − 1 + y), 2x−1, (1 + x)y−1, (y − 1 + x)} G1 G2 G1∨˙SG2{G_1}{\dot \vee _S}{G_2} Sx K(y, z) {(1 + y + z)x−1, (x − 1 + y + z), 2x−1, (z + x)y, (y + x)z} Sx r – regular {(1 + y)x−1, (x − 1 + y), 2x−1, (r + x)y} Kx,y Pz {(x + z)y, (y + z)x, 2xy, (1 + x + y)2(2 + x + y)z−2} Kx,y Kz {(x + z)y, (y + z)x, 2xy, (1 + x + y) (z − 1 + x + y)z} Kx,y Cz {(x + z)y, (y + z)x, 2xy, (2 + x + y)z} Kx,y Sz {(x + z)y, (y + z)x, 2xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(x + z + t)y, (y + z + t)x, 2xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(x + z)y, (y + z)x, 2xy, (r + x + y)z} r – regular Py {(r + y)x, 2rx/2, (1 + x)2, (2 + x)x−2} r – regular Ky {(r + y)x, 2rx/2, (y − 1 + x)y} r – regular Cy {(r + y)x, 2rx/2, (2 + x)y} r – regular Sy {(r + y)x, 2rx/2, (y − 1 + x), (1 + x)y−1} r – regular K(y,z) {(r + y + z)x, 2rx/2, (y + x)z, (z + x)y} r1 – regular r2 – regular {(r1 + y)x, 2r1x/2, (r2 + x)y}

#### Degree sequence of vertex-T join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs.

 G1 G2 DS(G1∨˙TG2)DS({G_1}{\dot \vee _T}{G_2}) Px Py {(2 + y)2, (4 + y)x−2, 32, 4(x − 3), (1 + x)2, (2 + x)y−2} Px Ky {(2 + y)2, (4 + y)x−2, 32, 4(x − 3), (y − 1 + x)y} Px Cy {(2 + y)2, (4 + y)x−2, 32, 4x−3, (2 + x)y} Px Sy {(2 + y)2, (4 + y)x−2, 32, 4x−3, (1 + x)y−1, (x + y − 1)} Px K(y, z) {(2 + y + z)2, (4 + y + z)x−2, 32, 4x−3, (y + x)z, (z + x)y} Px r – regular {(2 + y)2, (4 + y)x−2, 32, 4x−3, (r + x)y} Kx Py {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (x + y − 1)y} Kx Cy {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (2 + x)y} Kx Sy {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(2x − 2 + y + z)x, (2x − 2)x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(2x − 2 + y)x, (2x − 2)x(x−1)/2, (r + x)y} Cx Py {(4 + y)x, 4x, (1 + x)2, (2 + x)y−2} Cx Ky {(4 + y)x, 4x, (y − 1 + x)y} Cx Cy {(4 + y)x, 4x, (2 + x)y} Cx Sy {(4 + y)x, 4x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(4 + y + z)x, 4x, (y + x)z, (z + x)y} Cx r – regular {(4 + y)x, 4x, (r + x)y} Sx Py {(2 + y)x−1, (2x − 2 + y), xx−1, (1 + x)2, (2 + x)y−2} Sx Ky {(2 + y)x−1, (2x − 2 + y), xx−1, (y − 1 + x)y} Sx Cy {(2 + y)x−1, (2x − 2 + y), xx−1, (2 + x)y} Sx Sy {(2 + y)x−1, (2x − 2 + y), xx−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(2 + y + z)x−1, (2x − 2 + y + z), xx−1, (z + x)y, (y + x)z} Sx r – regular {(2 + y)x−1, (2x − 2 + y), xx−1, (r + x)y} G1 G2 DS(G1∨˙TG2)DS({G_1}{\dot \vee _T}{G_2}) Kx,y Pz {(2x + z)y, (2y + z)x, (x + y)xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(2x + z)y, (2y + z)x, (x + y)xy, (z − 1 + x + y)z} Kx,y Cz {2x + z)y, (2y + z)x, (x + y)xy, (2 + x + y)z} Kx,y Sz {(2x + z)y, (2y + z)x, (x + y)xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(2x + z + t)y, (2y + z + t)x, (x + y)xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular (2x + z)y, (2y + z)x, (x + y)xy, (r + x + y)z r – regular Pz {(2r + y)x, (2r)xr/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(2r + y)x, (2r)xr/2, (x + y − 1)y} r – regular Cy {(2r + y)x, (2r)xr/2, (2 + x)y} r – regular Sy {(2r + y)x, (2r)xr/2, (1 + x)y−1, (x + y − 1)} r – regular Ky,z {(2r + y + z)x, (2r)xr/2, (x + y)z, (x + z)y} r1 – regular r2 – regular {(2r1 + y)x, (2r1)xr1/2, (r − 2 + x)y}

#### j.amns.2020.2.00018.tab.001.w2aab3b7d849b1b6b1ab1b1c23Aa

GVerticesEdgesDegree Sequence
Pnn(n − 1){12, 2n−2}
Knnn(n − 1)/2{(n − 1)n}
Cnnn{2n}
Snn(n − 1){1n−1, (n − 1)1}
K(m,n)m + nmn{mn, nm}
r – regularn(n − 1){rn}

#### Degree Sequence of vertex-Q join graph for path, complete graph, cycle, star, complete bipartite and r–regular graphs

 G1 G2 DS(G1∨˙QG2)DS({G_1}{\dot \vee _Q}{G_2}) Px Py {(1 + y)2, (2 + y)x−2, 32, 4(x − 3)2, (1 + x)2, (2 + x)y−2} Px Ky {(1 + y)2, (2 + y)x−2, 32, 4(x − 3), (y − 1 + x)y} Px Cy {(1 + y)2, (2 + y)x−2, 32, 4x−3, (2 + x)y} Px Sy {(1 + y)2, (2 + y)x−2, 32, 4x−3, (1 + x)y−1, (x + y − 1)} G1 G2 DS(G1∨˙QG2)DS({G_1}{\dot \vee _Q}{G_2}) Px K(y, z) {(1 + y + z)2, (2 + y + z)x−2, 32, 4x−3, (y + x)z, (z + x)y} Px r – regular {(1 + y)2, (2 + y)x−2, 32, 4x−3, (r + x)y} Kx Py {(x − 1 + y)x, (2x − 2)x(x−1)/2, (1 + x)2, (2 + x)y−2} Kx Ky {(x − 1 + y)x, (2x − 2)x(x−1)/2, (x + y − 1)y} Kx Cy {(x − 1 + y)x, (2x − 2)x(x−1)/2, (2 + x)y} Kx Sy {(x − 1 + y)x, (2x − 2)x(x−1)/2, (1 + x)y−1, (y − 1 + x)} Kx K(y, z) {(x − 1 + y + z)x, (2x − 2)x(x−1)/2, (x + y)z, (x + z)y} Kx r – regular {(x − 1 + y)x, (2x − 2)x(x−1)/2, (r + x)y} Cx Py {(2 + y)x, 4x, (1 + x)2, (2 + x)y−2} Cx Ky {(2 + y)x, 4x, (y − 1 + x)y} Cx Cy {(2 + y)x, 4x, (2 + x)y} Cx Sy {(2 + y)x, 4x, (1 + x)y−1, (y − 1 + x)} Cx K(y, z) {(2 + y + z)x, 4x, (y + x)z, (z + x)y} Cx r – regular {(2 + y)x, 4x, (r + x)y} Sx Py {(1 + y)x−1, (x − 1 + y), xx−1, (1 + x)2, (2 + x)y−2} Sx Ky {(1 + y)x−1, (x − 1 + y), xx−1, (y − 1 + x)y} Sx Cy {(1 + y)x−1, (x − 1 + y), xx−1, (2 + x)y} Sx Sy {(1 + y)x−1, (x − 1 + y), xx−1, (1 + x)y−1, (y − 1 + x)} Sx K(y, z) {(1 + y + z)x−1, (x − 1 + y + z), xx−1, (z + x)y, (y + x)z} Sx r – regular {(1 + y)x−1, (x − 1 + y), xx−1, (r + x)y} Kx,y Pz {(x + z)y, (y + z)x, (x + y)xy, (1 + x + y)2, (2 + x + y)z−2} Kx,y Kz {(x + z)y, (y + z)x, (x + y)xy, (z − 1 + x + y)z} Kx,y Cz {(x + z)y, (y + z)x, (x + y)xy, (2 + x + y)z} Kx,y Sz {(x + z)y, (y + z)x, (x + y)xy, (1 + x + y)z−1, (z − 1 + x + y)} Kx,y Kz,t {(x + z + t)y, (y + z + t)x, (x + y)xy, (x + y + z)t, (x + y + t)z} Kx,y r – regular {(x + z)y, (y + z)x, (x + y)xy, (r + x + y)z} r – regular Pz {(r + y)x, (2r)xr/2, (1 + x)2, (2 + x)y−2} r – regular Ky {(r + y)x, (2r)xr/2, (x + y − 1)y} r – regular Cy {(r + y)x, (2r)xr/2, (2 + x)y} r – regular Sy {(r + y)x, (2r)xr/2, (1 + x)y−1, (x + y − 1)} r – regular Ky,z {(r + y + z)x, (2r)xr/2, (x + y)z, (x + z)y} r1 – regular r2 – regular {(r1 + y)x, (2r1)xr1/2, (r − 2 + x)y}

B. Bollobas, (1981), Degree sequences of random graphs, Discrete Math. 33, 1–19.BollobasB.1981Degree sequences of random graphsDiscrete Math.33119Search in Google Scholar

Vishnu Narayan Mishra, Sadik Delen and Ismail Naci Cangul, (2018), Algebraic structure of graph operations in terms of degree sequences, International Journal of analysis and applications, 10.28924/2291-8639-16-2018-809.MishraVishnu NarayanDelenSadikCangulIsmail Naci2018Algebraic structure of graph operations in terms of degree sequencesInternational Journal of analysis and applications10.28924/2291-8639-16-2018-809

K. C. Das, A. Yurttas, M. Togan, I. N. Cangul, A. S. Cevik, (2013), The multiplicative Zagreb indices of graph operations, J. Inequal. Appl. 90, 1–14.DasK. C.YurttasA.ToganM.CangulI. N.CevikA. S.2013The multiplicative Zagreb indices of graph operationsJ. Inequal. Appl.90114Search in Google Scholar

M. Eliasi, B. Taeri, (2009), Four new sums of graphs and their Wiener indices, Discrete Appl. Math., 157, 794–803.EliasiM.TaeriB.2009Four new sums of graphs and their Wiener indicesDiscrete Appl. Math.157794803Search in Google Scholar

B. Furtula, I. Gutman, M. Dehmer, (2013), On structure-sensitivity of degree-based topological indices, Appl Math Comp, 219, 8973–8978.FurtulaB.GutmanI.DehmerM.2013On structure-sensitivity of degree-based topological indicesAppl Math Comp21989738978Search in Google Scholar

A. Ivanyi, L. Lucz, G. Gombos, T. Matuszka, (2013), Parallel enumeration of degree sequences of simple graphs II, Acta Univ. Sapientiae, Informatica 5 (2), 245–270.IvanyiA.LuczL.GombosG.MatuszkaT.2013Parallel enumeration of degree sequences of simple graphs IIActa Univ. Sapientiae, Informatica52245270Search in Google Scholar

H. Kim, Z. Toroczkai, I. Miklos, P. L. Erdos, L. A. Szekely, (2009), On realizing all simple graphs with a given degree sequence, J. Phys. A: Math. Theor. 42, 1–6.KimH.ToroczkaiZ.MiklosI.ErdosP. L.SzekelyL. A.2009On realizing all simple graphs with a given degree sequenceJ. Phys. A: Math. Theor.4216Search in Google Scholar

J. W. Miller, (2013), Reduced criteria for degree sequences, Discrete Math. 313, 550–562.MillerJ. W.2013Reduced criteria for degree sequencesDiscrete Math.313550562Search in Google Scholar

K. Pattabiraman and M. Vijayaragavan, (2013), Reciprocal degree distance of some graph operations, Transactions on Combinatorics, 2(4), 13–24.PattabiramanK.VijayaragavanM.2013Reciprocal degree distance of some graph operationsTransactions on Combinatorics241324Search in Google Scholar

P. S. Ranjini, V. Lokesha and M. A. Raja, (2010), On Zagreb indices of the p- subdivision graphs, J. Orissa Math. Sco. 29 (1–2), .RanjiniP. S.LokeshaV.RajaM. A.2010On Zagreb indices of the p- subdivision graphsJ. Orissa Math. Sco.291–2Search in Google Scholar

P. Sarkar, N. De and A. Pal, (2017), The Zagreb indices of graphs based on new operations related to the join of graphs, J. Int. Math. Virtual Inst., 7, 181–209.SarkarP.DeN.PalA.2017The Zagreb indices of graphs based on new operations related to the join of graphsJ. Int. Math. Virtual Inst.7181209Search in Google Scholar

B. Shwetha Shetty, V. Lokesha and P. S. Ranjini, (2015), On the harmonic index of graph operatios, Transactions on combinatorics, 4(4), 5–14.Shwetha ShettyB.LokeshaV.RanjiniP. S.2015On the harmonic index of graph operatiosTransactions on combinatorics44514Search in Google Scholar

A. Triphati, H. Tyagi, (2008), A simple criterion on degree sequences of graphs, Discrete Appl. Math. 156 (2008), 3513–3517.TriphatiA.TyagiH.2008A simple criterion on degree sequences of graphsDiscrete Appl. Math.156200835133517Search in Google Scholar

R. I. Tyshkevich, A. A. Chernyak, Zh. A. Chernyak, (1987), Graphs and degree sequences I, Cybernetics 23 (6), 734–745.TyshkevichR. I.ChernyakA. A.ChernyakZh. A.1987Graphs and degree sequences ICybernetics236734745Search in Google Scholar

R. I. Tyshkevich, O. I. Mel’nikov, V. M. Kotov, (1981), On graphs and degree sequences: Canonical Decomposition, Kibernetika 6, 5–8.TyshkevichR. I.Mel’nikovO. I.KotovV. M.1981On graphs and degree sequences: Canonical DecompositionKibernetika658Search in Google Scholar

I. E. Zverovich, V. E. Zverovich, (1992), Contributions to the theory of graphic sequences, Discrete Math. 105, 293–303.ZverovichI. E.ZverovichV. E.1992Contributions to the theory of graphic sequencesDiscrete Math.105293303Search in Google Scholar