Degree Sequence of Graph Operator for some Standard Graphs

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 d_u. 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 G₁ and G₂ be two graphs having n₁, n₂ vertices and m₁, m₂ edges respectively.

A join G₁ ∨ G₂ of two graphs G₁ and G₂ with disjoint vertex sets V (G₁) and V (G₂) is the graph on the vertex set V (G₁) ∪ V (G₂) and the edge set E(G₁) ∪ E(G₂) ∪ {xy | x ∈ V (G₁), y ∈ V (G₂)}. 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 G₁ and G₂, as follows:

VertexF-join of Graphs: [11] Let G₁ and G₂ be two simple graph the vertex F-join graph of G₁ and G₂ is denoted by $G_{1} {\dot{\lor}}_{F} G_{2}$ {G_1}{\dot \vee _F}{G_2} and the graph is obtained from F(G₁) and G₂ by joining each vertex of G₁ to all vertex of G₂. The vertex and edge set of $G_{1} {\dot{\lor}}_{F} G_{2}$ {G_1}{\dot \vee _F}{G_2} is V (F(G₁)) ∪ V (G₂) and E(G₁) ∪ E(G₂) ∪ [xy : x ∈ V (G₁), y ∈ V (G₂)].

VertexSjoin of graph: Let G₁ and G₂ be two simple graph the vertex S-join graph of G₁ and G₂ is denoted by $G_{1} {\dot{\lor}}_{S} G_{2}$ {G_1}{\dot \vee _S}{G_2} and the graph is obtained from S(G₁) and G₂ by joining each vertex of V (G₁) to all vertex of G₂.

VertexRjoin of graph: Let G₁ and G₂ be two simple graph the vertex S-join graph of G₁ and G₂ is denoted by $G_{1} {\dot{\lor}}_{R} G_{2}$ {G_1}{\dot \vee _R}{G_2} and the graph is obtained from R(G₁) and G₂ by joining each vertex of V (G₁) to all vertex of G₂.

VertexQjoin of graph: Let G₁ and G₂ be two simple graph the vertex S-join graph of G₁ and G₂ is denoted by $G_{1} {\dot{\lor}}_{Q} G_{2}$ {G_1}{\dot \vee _Q}{G_2} and the graph is obtained from Q(G₁) and G₂ by joining each vertex of V (G₁) to all vertex of G₂.

VertexTjoin of graph: Let G₁ and G₂ be two simple graph the vertex S-join graph of G₁ and G₂ is denoted by $G_{1} {\dot{\lor}}_{T} G_{2}$ {G_1}{\dot \vee _T}{G_2} and the graph is obtained from T (G₁) and G₂ by joining each vertex of V (G₁) to all vertex of G₂.

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 d_i, 1 < i < n are the degrees of the vertices u_i of a graph G then the degree sequence(DS) of G is represented as the sequence {d₁,d₂,···d_n}. Also, in many papers, the degree sequence (DS) is taken to be a non-decreasing sequence, whenever possible.

Conversely, a non-negative sequence {d₁,d₂,···d_n} 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 d_i of the vertex u_i appears α_i times in the DS of a graph G, then we consider ${d_{1}^{α_{1}}, d_{2}^{α_{2}}, \dots d_{k}^{α_{k}}}$ \left\{ {d_1^{{\alpha _1}},d_2^{{\alpha _2}}, \cdots d_k^{{\alpha _k}}} \right\} instead of {d₁,d₂,···d_n} 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 P_n, K_n, C_n, S_n, K_(m,n) and r – regular be path, complete, cycle, star, complete bipartite, r – regular respectively and they are commonly used graph examples in literature survey which can be seen figure 2.

Titania nanotube T_iO₂[m,n] with degree assigned to the vertices

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

Table 1

G	Vertices	Edges	Degree Sequence
P_n	n	(n − 1)	{1², 2ⁿ⁻²}
K_n	n	n(n − 1)/2	{(n − 1)ⁿ}
C_n	n	n	{2ⁿ}
S_n	n	(n − 1)	{1ⁿ⁻¹, (n − 1)¹}
K_(m,n)	m + n	mn	{mⁿ, n^m}
r – regular	n	(n − 1)	{rⁿ}

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 $G_{1} {\dot{\lor}}_{S} G_{2}$ {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

Table 2

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

G₁	G₂	$G_{1} {\dot{\lor}}_{S} G_{2}$ {G_1}{\dot \vee _S}{G_2}
P_x	P_y	{(1 + y)², (2 + y)^x−2, 2^x−1, (1 + x)², (2 + x)^y−2}
P_x	K_y	{(1 + y)², (2 + y)^x−2, 2^x−1, (y − 1 + x)^y}
P_x	C_y	{(1 + y)², (2 + y)^x−2, 2^x−1, (2 + x)^y}
P_x	S_y	{(1 + y)², (2 + y)^x−2, 2^x−1, (1 + x)^y−1, (y − 1 + x)}
P_x	K(y, z)	{(1 + y + z)², (2 + y + z)^x−2, 2^x−1, (y + x)^z, (z + x)^y}
P_x	r – regular	{(1 + y)², (2 + y)^x−2, 2^x−1, (r + x)^y}
K_x	P_y	{(x − 1 + y)^x, 2^x(x−1)/2, (1 + x)², (2 + x)^y−2}
K_x	K_y	{(x − 1 + y)^(2x), 2^x(x−1)/2}
K_x	C_y	{(x − 1 + y)^x, 2^x(x−1)/2, (2 + x)^y}
K_x	S_y	{(x − 1 + y)^x, 2^x(x−1)/2, (1 + x)^y−1, (y − 1 + x)}
K_x	K(y, z)	{(x − 1 + y + z)^x, 2^x(x−1)/2, (x + y)^z, (x + z)^y}
K_xC_x	r – regularP_y	{(x − 1 + y)^x, 2^x(x−1)/2, (r + x)^y}{(2 + y)^x, 2^x, (1 + x)², (2 + x)^y−2}
C_x	K_y	{(2 + y)^x, 2^x, (y − 1 + x)^y}
C_x	C_y	{(2 + y)^x, 2^x, (2 + x)^y}
C_x	S_y	{(2 + y)^x, 2^x, (1 + x)^y−1, (y − 1 + x)}
C_x	K(y, z)	{(2 + y)^x, 2^x, (y + x)^z, (z + x)^y}
C_x	r – regular	{(2 + y)^x, 2^x, (r + x)^y}
S_x	P_y	{(1 + y)^x−1, (x − 1 + y), 2^x−1, (2 + x)^y−2}
S_x	K_y	{(1 + y)^x−1, (x − 1 + y), 2^x−1, (y − 1 + x)^y}
S_x	C_y	{(1 + y)^x−1, (x − 1 + y), 2^x−1, (2 + x)^y}
S_x	S_y	{(1 + y)^x−1, (x − 1 + y), 2^x−1, (1 + x)^y−1, (y − 1 + x)}
G₁	G₂	$G_{1} {\dot{\lor}}_{S} G_{2}$ {G_1}{\dot \vee _S}{G_2}
S_x	K(y, z)	{(1 + y + z)^x−1, (x − 1 + y + z), 2^x−1, (z + x)^y, (y + x)^z}
S_x	r – regular	{(1 + y)^x−1, (x − 1 + y), 2^x−1, (r + x)^y}
K_x,y	P_z	{(x + z)^y, (y + z)^x, 2^xy, (1 + x + y)²(2 + x + y)^z−2}
K_x,y	K_z	{(x + z)^y, (y + z)^x, 2^xy, (1 + x + y) (z − 1 + x + y)^z}
K_x,y	C_z	{(x + z)^y, (y + z)^x, 2^xy, (2 + x + y)^z}
K_x,y	S_z	{(x + z)^y, (y + z)^x, 2^xy, (1 + x + y)^z−1, (z − 1 + x + y)}
K_x,y	K_z,t	{(x + z + t)^y, (y + z + t)^x, 2^xy, (x + y + z)^t, (x + y + t)^z}
K_x,y	r – regular	{(x + z)^y, (y + z)^x, 2^xy, (r + x + y)^z}
r – regular	P_y	{(r + y)^x, 2^rx/2, (1 + x)², (2 + x)^x−2}
r – regular	K_y	{(r + y)^x, 2^rx/2, (y − 1 + x)^y}
r – regular	C_y	{(r + y)^x, 2^rx/2, (2 + x)^y}
r – regular	S_y	{(r + y)^x, 2^rx/2, (y − 1 + x), (1 + x)^y−1}
r – regular	K_(y,z)	{(r + y + z)^x, 2^rx/2, (y + x)^z, (z + x)^y}
r₁ – regular	r₂ – regular	{(r₁ + y)^x, 2^r₁^x/2, (r₂ + x)^y}

Proof

We prove here only two types of Degree Sequences

$C_{x} {\dot{\lor}}_{S} P_{y}$ {C_x}{\dot \vee _S}{P_y}

$K_{x} {\dot{\lor}}_{S} K_{y}$ {K_x}{\dot \vee _S}{K_y}

Let DS(C_x) = {2^x} and DS(P_y) = {1²,2^y−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 $C_{x} {\dot{\lor}}_{S} P_{y}$ {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 $C_{x} {\dot{\lor}}_{S} P_{y}$ {C_x}{\dot \vee _S}{P_y} .

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

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

Hence, the required degree sequence of $D S (C_{x} {\dot{\lor}}_{S} P_{y}) = {{(2 + y)}^{x} {, 2}^{x}, (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(K_x) = {(x − 1)^x} and DS(K_y) = {(y − 1)^y}.

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

The first two set of vertices are the vertices in K_x. which are connected to every vertex in K_y, each of which adds (x + y − 1) to the DS of $K_{x} {\dot{\lor}}_{S} K_{y}$ {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 K_x with two degree, since there are x(x − 1)/2 vertices.

Therefore DS of $K_{x} {\dot{\lor}}_{S} K_{y}$ {K_x}{\dot \vee _S}{K_y} is 2^x(x−1)/2.

Hence, the required degree sequence of $D S (K_{x} {\dot{\lor}}_{S} K_{y}) = {{(x + y - 1)}^{y} {, 2}^{x (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 $G_{1} {\dot{\lor}}_{R} G_{2}$ {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

Table 3

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

G₁	G₂	$D S (G_{1} {\dot{\lor}}_{R} G_{2})$ DS({G_1}{\dot \vee _R}{G_2})
P_x	P_y	{(2 + y)², (4 + y)^x−2, 2^x−1, (1 + x)², (2 + x)^y−2}
P_x	K_y	{(2 + y)², (4 + y)^x−2, 2^x−1, (x + y − 1)^y}
P_x	C_y	{(2 + y)², (4 + y)^x−2, 2^x−1, (2 + x)^y}
P_x	S_y	{(2 + y)², (4 + y)^x−2, 2^x−1, (1 + x)^y−1, (x + y − 1)}
P_x	K(y, z)	{(2 + y + z)², (4 + y + z)^x−2, 2^x−1, (y + x)^z, (z + x)^y}
P_x	r – regular	{(2 + y)², (4 + y)^x−2, 2^x−1, (r + x)^y}
K_x	P_y	{(2x − 2 + y)^x, 2^x(x−1)/2, (1 + x)², (2 + x)^y−2}
K_x	K_y	{(2x − 2 + y)^x, 2^x(x−1)/2, (x + y − 1)^y}
K_x	C_y	{(2x − 2 + y)^x, 2^x(x−1)/2, (2 + x)^y}
K_x	S_y	{(2x − 2 + y)^x, 2^x(x−1)/2, (1 + x)^y−1, (y − 1 + x)}
K_x	K(y, z)	{(2x − 2 + y + z)^x, 2^x(x−1)/2, (x + y)^z, (x + z)^y}
K_x	r – regular	{(2x − 2 + y)^x, 2^x(x−1)/2, (r + x)^y}
C_x	P_y	{(4 + y)^x, 2^x, (1 + x)², (2 + x)^y−2}
C_x	K_y	{(4 + y)^x, 2^x, (y − 1 + x)}
C_x	C_y	{(4 + y)^x, 2^x, (2 + x)^y}
C_x	S_y	{(4 + y)^x, 2^x, (1 + x)^y−1, (y − 1 + x)}
C_x	K(y, z)	{(4 + y + z)^x, 2^x, (y + x)^z, (z + x)^y}
C_x	r – regular	{(4 + y)^x, 2^x, (r + x)^y}
G₁	G₂	$D S (G_{1} {\dot{\lor}}_{R} G_{2})$ DS({G_1}{\dot \vee _R}{G_2})
S_x	P_y	{(2 + y)^x−1, (2x − 2 + y), 2^x−1, (1 + x)², (2 + x)^y−2}
S_x	K_y	{(2 + y)^x−1, (2x − 2 + y), 2^x−1, (y − 1 + x)^y}
S_x	C_y	{(2 + y)^x−1, (2x − 2 + y), 2^x−1, (2 + x)^y}
S_x	S_y	{(2 + y)^x−1, (2x − 2 + y), 2^x−1, (1 + x)^y−1, (y − 1 + x)}
S_x	K(y, z)	{(2 + y + z)^x−1, (2x − 2 + y + z), 2^x−1, (z + x)^y, (y + x)^z}
S_x	r – regular	{(2 + y)^x−1, (2x − 2 + y), 2^x−1, (r + x)^y}
K_x,y	P_z	{(2x + z)^y, (2y + z)^x, 2^xy, (1 + x + y)², (2 + x + y)^z−2}
K_x,y	K_z	{(2x + z)^y, (2y + z)^x, 2^xy, (z − 1 + x + y)^z}
K_x,y	C_z	{(2x + z)^y, (2y + z)^x, 2^xy, (2 + x + y)^z}
K_x,y	S_z	{(2x + z)^y, (2y + z)^x, 2^xy, (1 + x + y)^z−1, (z − 1 + x + y)}
K_x,y	K_z,t	{(2x + z + t)^y, (2y + z + t)^x, 2^xy, (x + y + z)^t, (x + y + t)^z}
K_x,y	r – regular	{(2x + z)^y, (2y + z)^x, 2^xy, (r + x + y)^z}
r – regular	P_y	{(2r + y)^x, 2^rx/2, (1 + x)², (2 + x)^y−2}
r – regular	K_y	{(2r + y)^x, 2^rx/2, (y − 1 + x)^y}
r – regular	C_y	{(2r + y)^x, 2^rx/2, (2 + x)^y}
r – regular	S_y	{(2r + y)^x, 2^rx/2, (y − 1 + x), (1 + x)^y}
r – regular	K(y, z)	{(2r + y + z)^x, 2^rx/2, (y + x)^z, (z + x)^y}
r₁ – regular	r₂ – regular	{(2r₁ + y)^x, 2^r₁x/2, (r₂ + x)^y}

Theorem 3.3

The degree sequence of all possible $G_{1} {\dot{\lor}}_{Q} G_{2}$ {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

Table 4

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

G₁	G₂	$D S (G_{1} {\dot{\lor}}_{Q} G_{2})$ DS({G_1}{\dot \vee _Q}{G_2})
P_x	P_y	{(1 + y)², (2 + y)^x−2, 3², 4(x − 3)², (1 + x)², (2 + x)^y−2}
P_x	K_y	{(1 + y)², (2 + y)^x−2, 3², 4(x − 3), (y − 1 + x)^y}
P_x	C_y	{(1 + y)², (2 + y)^x−2, 3², 4^x−3, (2 + x)^y}
P_x	S_y	{(1 + y)², (2 + y)^x−2, 3², 4^x−3, (1 + x)^y−1, (x + y − 1)}
G₁	G₂	$D S (G_{1} {\dot{\lor}}_{Q} G_{2})$ DS({G_1}{\dot \vee _Q}{G_2})
P_x	K(y, z)	{(1 + y + z)², (2 + y + z)^x−2, 3², 4^x−3, (y + x)^z, (z + x)^y}
P_x	r – regular	{(1 + y)², (2 + y)^x−2, 3², 4^x−3, (r + x)^y}
K_x	P_y	{(x − 1 + y)^x, (2x − 2)^x(x−1)/2, (1 + x)², (2 + x)^y−2}
K_x	K_y	{(x − 1 + y)^x, (2x − 2)^x(x−1)/2, (x + y − 1)^y}
K_x	C_y	{(x − 1 + y)^x, (2x − 2)^x(x−1)/2, (2 + x)^y}
K_x	S_y	{(x − 1 + y)^x, (2x − 2)^x(x−1)/2, (1 + x)^y−1, (y − 1 + x)}
K_x	K(y, z)	{(x − 1 + y + z)^x, (2x − 2)^x(x−1)/2, (x + y)^z, (x + z)^y}
K_x	r – regular	{(x − 1 + y)^x, (2x − 2)^x(x−1)/2, (r + x)^y}
C_x	P_y	{(2 + y)^x, 4^x, (1 + x)², (2 + x)^y−2}
C_x	K_y	{(2 + y)^x, 4^x, (y − 1 + x)^y}
C_x	C_y	{(2 + y)^x, 4^x, (2 + x)^y}
C_x	S_y	{(2 + y)^x, 4^x, (1 + x)^y−1, (y − 1 + x)}
C_x	K(y, z)	{(2 + y + z)^x, 4^x, (y + x)^z, (z + x)^y}
C_x	r – regular	{(2 + y)^x, 4^x, (r + x)^y}
S_x	P_y	{(1 + y)^x−1, (x − 1 + y), x^x⁻¹, (1 + x)², (2 + x)^y−2}
S_x	K_y	{(1 + y)^x−1, (x − 1 + y), x^x⁻¹, (y − 1 + x)^y}
S_x	C_y	{(1 + y)^x−1, (x − 1 + y), x^x⁻¹, (2 + x)^y}
S_x	S_y	{(1 + y)^x−1, (x − 1 + y), x^x⁻¹, (1 + x)^y−1, (y − 1 + x)}
S_x	K(y, z)	{(1 + y + z)^x−1, (x − 1 + y + z), x^x⁻¹, (z + x)^y, (y + x)^z}
S_x	r – regular	{(1 + y)^x−1, (x − 1 + y), x^x⁻¹, (r + x)^y}
K_x,y	P_z	{(x + z)^y, (y + z)^x, (x + y)^xy, (1 + x + y)², (2 + x + y)^z−2}
K_x,y	K_z	{(x + z)^y, (y + z)^x, (x + y)^xy, (z − 1 + x + y)^z}
K_x,y	C_z	{(x + z)^y, (y + z)^x, (x + y)^xy, (2 + x + y)^z}
K_x,y	S_z	{(x + z)^y, (y + z)^x, (x + y)^xy, (1 + x + y)^z−1, (z − 1 + x + y)}
K_x,y	K_z,t	{(x + z + t)^y, (y + z + t)^x, (x + y)^xy, (x + y + z)^t, (x + y + t)^z}
K_x,y	r – regular	{(x + z)^y, (y + z)^x, (x + y)^xy, (r + x + y)^z}
r – regular	P_z	{(r + y)^x, (2r)^xr/2, (1 + x)², (2 + x)^y−2}
r – regular	K_y	{(r + y)^x, (2r)^xr/2, (x + y − 1)^y}
r – regular	C_y	{(r + y)^x, (2r)^xr/2, (2 + x)^y}
r – regular	S_y	{(r + y)^x, (2r)^xr/2, (1 + x)^y−1, (x + y − 1)}
r – regular	K_y,z	{(r + y + z)^x, (2r)^xr/2, (x + y)^z, (x + z)^y}
r₁ – regular	r₂ – regular	{(r₁ + y)^x, (2r₁)^xr₁/2, (r − 2 + x)^y}

Theorem 3.4

The degree sequence of all possible $G_{1} {\dot{\lor}}_{T} G_{2}$ {G_1}{\dot \vee _T}{G_2}of the path, complete, cycle, star, complete bipartite and r–regular graphs are given in table 5.

Table 5

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

G₁	G₂	$D S (G_{1} {\dot{\lor}}_{T} G_{2})$ DS({G_1}{\dot \vee _T}{G_2})
P_x	P_y	{(2 + y)², (4 + y)^x−2, 3², 4(x − 3), (1 + x)², (2 + x)^y−2}
P_x	K_y	{(2 + y)², (4 + y)^x−2, 3², 4(x − 3), (y − 1 + x)^y}
P_x	C_y	{(2 + y)², (4 + y)^x−2, 3², 4^x−3, (2 + x)^y}
P_x	S_y	{(2 + y)², (4 + y)^x−2, 3², 4^x−3, (1 + x)^y−1, (x + y − 1)}
P_x	K(y, z)	{(2 + y + z)², (4 + y + z)^x−2, 3², 4^x−3, (y + x)^z, (z + x)^y}
P_x	r – regular	{(2 + y)², (4 + y)^x−2, 3², 4^x−3, (r + x)^y}
K_x	P_y	{(2x − 2 + y)^x, (2x − 2)^x(x−1)/2, (1 + x)², (2 + x)^y−2}
K_x	K_y	{(2x − 2 + y)^x, (2x − 2)^x(x−1)/2, (x + y − 1)^y}
K_x	C_y	{(2x − 2 + y)^x, (2x − 2)^x(x−1)/2, (2 + x)^y}
K_x	S_y	{(2x − 2 + y)^x, (2x − 2)^x(x−1)/2, (1 + x)^y−1, (y − 1 + x)}
K_x	K(y, z)	{(2x − 2 + y + z)^x, (2x − 2)^x(x−1)/2, (x + y)^z, (x + z)^y}
K_x	r – regular	{(2x − 2 + y)^x, (2x − 2)^x(x−1)/2, (r + x)^y}
C_x	P_y	{(4 + y)^x, 4^x, (1 + x)², (2 + x)^y−2}
C_x	K_y	{(4 + y)^x, 4^x, (y − 1 + x)^y}
C_x	C_y	{(4 + y)^x, 4^x, (2 + x)^y}
C_x	S_y	{(4 + y)^x, 4^x, (1 + x)^y−1, (y − 1 + x)}
C_x	K(y, z)	{(4 + y + z)^x, 4^x, (y + x)^z, (z + x)^y}
C_x	r – regular	{(4 + y)^x, 4^x, (r + x)^y}
S_x	P_y	{(2 + y)^x−1, (2x − 2 + y), x^x⁻¹, (1 + x)², (2 + x)^y−2}
S_x	K_y	{(2 + y)^x−1, (2x − 2 + y), x^x⁻¹, (y − 1 + x)^y}
S_x	C_y	{(2 + y)^x−1, (2x − 2 + y), x^x⁻¹, (2 + x)^y}
S_x	S_y	{(2 + y)^x−1, (2x − 2 + y), x^x⁻¹, (1 + x)^y−1, (y − 1 + x)}
S_x	K(y, z)	{(2 + y + z)^x−1, (2x − 2 + y + z), x^x⁻¹, (z + x)^y, (y + x)^z}
S_x	r – regular	{(2 + y)^x−1, (2x − 2 + y), x^x⁻¹, (r + x)^y}
G₁	G₂	$D S (G_{1} {\dot{\lor}}_{T} G_{2})$ DS({G_1}{\dot \vee _T}{G_2})
K_x,y	P_z	{(2x + z)^y, (2y + z)^x, (x + y)^xy, (1 + x + y)², (2 + x + y)^z−2}
K_x,y	K_z	{(2x + z)^y, (2y + z)^x, (x + y)^xy, (z − 1 + x + y)^z}
K_x,y	C_z	{2x + z)^y, (2y + z)^x, (x + y)^xy, (2 + x + y)^z}
K_x,y	S_z	{(2x + z)^y, (2y + z)^x, (x + y)^xy, (1 + x + y)^z−1, (z − 1 + x + y)}
K_x,y	K_z,t	{(2x + z + t)^y, (2y + z + t)^x, (x + y)^xy, (x + y + z)^t, (x + y + t)^z}
K_x,y	r – regular	(2x + z)^y, (2y + z)^x, (x + y)^xy, (r + x + y)^z
r – regular	P_z	{(2r + y)^x, (2r)^xr/2, (1 + x)², (2 + x)^y−2}
r – regular	K_y	{(2r + y)^x, (2r)^xr/2, (x + y − 1)^y}
r – regular	C_y	{(2r + y)^x, (2r)^xr/2, (2 + x)^y}
r – regular	S_y	{(2r + y)^x, (2r)^xr/2, (1 + x)^y−1, (x + y − 1)}
r – regular	K_y,z	{(2r + y + z)^x, (2r)^xr/2, (x + y)^z, (x + z)^y}
r₁ – regular	r₂ – regular	{(2r₁ + y)^x, (2r₁)^xr₁/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.

eISSN:: 2444-8656
Sprache:: Englisch

Zeitrahmen der Veröffentlichung:: Volume Open
Fachgebiete der Zeitschrift:: Biologie, andere, Mathematik, Angewandte Mathematik, Allgemeines, Physik

Zeitschrift RSS Feed

Degree Sequence of Graph Operator for some Standard Graphs

Online veröffentlicht: 10. Aug. 2020

Seitenbereich: 99 - 108

Eingereicht: 10. Apr. 2019

Akzeptiert: 05. Juni 2019

DOI: https://doi.org/10.2478/amns.2020.2.00018

Schlüsselwörter
Degree sequence, graph operators, standard graphs

© 2020 Harisha et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Fig. 1

Fig. 2

Fig. 3

Degree Sequence of Graph Operator for some Standard Graphs

Online veröffentlicht: 10. Aug. 2020

Seitenbereich: 99 - 108

Eingereicht: 10. Apr. 2019

Akzeptiert: 05. Juni 2019

DOI: https://doi.org/10.2478/amns.2020.2.00018

SchlüsselwörterDegree sequence, graph operators, standard graphs

© 2020 Harisha et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Fig. 1

Fig. 2

Fig. 3

Schlüsselwörter
Degree sequence, graph operators, standard graphs