This work is licensed under the Creative Commons Attribution 4.0 International License.
Introduction
A graph G =(V,E) is an ordered pair of set of vertices and edges, where edges are unordered pair of vertices. Also G is said to be a (p,q) graph if |V| = p and |E| = q. For a graph G = (V,E) if u, v ∈V(G) then the distance d (u, v) between u and v is defined as the length of a shortest u-v path in G. The Wiener index of G, denoted by W(G), is defined as
$$W\left( G \right)=\sum\limits_{u\ne v}^{\,}{d\left( u,v \right)},$$
where the sum is taken through all unordered pairs of vertices of G. Wiener index was introduced by Wiener [17]. It is related to boiling point, heat of evaporation, heat of formation, chromatographic retention times, surface tension, vapour pressure, partition coefficients, total electron energy of polymers, ultrasonic sound velocity, internal energy, etc., (see [12]). For this reason Wiener index is widely studied by chemists. Mathematical properties and chemical applications of the Wiener index have been intensively studied over the past thirty years. For more information about the Wiener index in chemistry and mathematics (see [11]) and [1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 18], respectively. In this paper we introduce a new composition of two graphs and study the Wiener indices of the resulting graphs.
The composition of two graphs G = (p,q) and H = (r, s) is denoted by G[H], whose vertex set is V(G) × V(H) and two vertices u = (u1,u2) and v = (v1, v2) ∈ V(G[H]) are adjacent if and only if [u1 = v1 and (u2, v2) ∈ E(H)] or [(u1, v1) ∈ E(G)]. Note that G[H] has p copies of H, and we may label these copies by vertices of V(G). Now two vertices with the same name in different copies are adjacent in G[H] if and only if their corresponding labels are adjacent in G. The graphs G, H and their composition G[H] are shown in Figure 1.
Fig. 1
The graphs G, H, G[H]
We are interested in giving new composition of graphs such that (V(G) ∪ E(G)) × V(H) and (V(G) ∪ V′(G)) × V(H) are the set of vertices. For this purpose we first recall some operations on graphs.
The total graph T(G) is the graph whose vertex set is V(G) ∪ E(G) and two vertices are adjacent if and only if they are adjacent or incident in G. The notion of total graph was introduced by Behzad & Chartrand [2]. The middle graph or semi-total line graph M (G) of G is the graph whose vertex set is V(G) ∪ E(G). Two vertices in M (G) are adjacent if and only if they are adjacent edges in G, or one is a vertex and another is an edge incident on it in G. A structural characterization and various properties of middle graphs were presented by Sampathkumar & Chikkodimath [14]. The semi-total point graph Q(G) of G is the graph whose vertex set is V(G)∪E(G). Two vertices in Q(G) are adjacent if and only if they are adjacent vertices in G, or one is a vertex and another is an edge incident on it in G. It is introduced by Sampathkumar & Chikkodimath [15]. The subdivision graph S (G) of G is the graph whose vertex set is V(G)∪E(G). Two vertices in S (G) are adjacent if and only if one is a vertex and another is an edge incident on it in G. The subdivision graph S (G), the semi-total point graph Q(G), the middle graph M (G) and the total graph T(G) of a graph G are shown in Figure 2.
Fig. 2
The graphs G, S(G), Q(G), M(G), T(G)
The splitting graph Λ(G) of a graph G is the graph whose vertex set is V(G)∪V(G), where V′(G) is the copy of V(G) (i.e., V′(G) = {v′: v ∈ V(G)}) and the edge set is E(G)∪{xy′: xy ∈ E(G)}. The vertex v′ is called the twin of the vertex v, (and v the twin of v′). It is introduced by Sampathkumar and Walikar [16] . Theclosed splitting graph Λ[G] of a graph G is the graph whose vertex set is V(G)∪V′(G), where V′(G) is the copy of V(G) (i.e., V′(G) = v′: v ∈ V(G)) and the edge set is E(G) ∪ {xx′: x ∈ V(G)} ∪ {xy′: xy ∈ E(G)}. The shadowgraph of G, denoted by D2(G), has as the vertex set V(G) ∪ V′(G), and the edge set E (G) ∪ {x′y: xy ∈ E (G)} ∪ {xy′: xy ∈ E (G)}. The closed shadowgraph of G, denoted by D2[G], has as the vertex set V(G)∪V(G), and the edge set E(G)∪{x′y′: xy ∈ E(G)}∪{xy′: xy ∈ E(G)}∪{xx′: x ∈ V(G)}. The vertex vis called the twin of the vertex v, (and v the twin of v′). We illustrate these definitions in Figure 3.
Fig. 3
The graphs G, P = Λ(G), Q = Λ[G], R = D2(G) and S = D2[G]
Let G =(p,q) and H =(r, s) be two graphs and also let F(G) be one of the symbols S(G),M(G),Q(G),T(G). The F-composition F (G)[H] is a graph with the set of vertices V(F(G)[H]) = (V(G)∪E(G))×V(H) and two vertices u=(u1,u2) and v =(v1, v2) of F(G)[H] are adjacent if and only if [u1 =v1∈V(G) and (u2, v2) ∈ E(H)] or [(u1, v1) ∈ E(F(G))]. Note that F (G)[H] has p copies of the graph H, and we may label these copies by vertices of G. We illustrate these definitions in Figure 4.
Fig. 4
The graphs G, H, S(G)[H], Q(G)[H], M(G)[H] and T(G)[H]
Let G = (p,q) and H = (r, s) be two graphs and also let F (G) be one of the symbols Λ(G),Λ[G],D2(G),D2[G]. The F-composition F (G)[H] is a graph with the set of vertices V(F(G)[H]) = (V(G)∪V′(G))×V(H) and two vertices u = (u1,u2) and v = (v1, v2) of F(G)[H] are adjacent if and only if [u1 = v1∈ V(G) and (u2, v2) ∈ E(H)] or [(u1, v1) ∈ E(F(G))]. Note that F(G)[H] has p copies of the graph H, and we may label these copies by vertices of G. We illustrate these definitions in Figure 5.
Fig. 5
The graphs G, H, P = Λ(G)[H], Q = Λ[G][H], R = D2(G)[H] and S = D2[G][H]
Main Results
Lemma 1
[18] Let G = (p,q) and H = (r, s) be two connected graphs. Then,
$$W\left( G\left[ H \right] \right)={{r}^{2}}\left( W\left( G \right)+p \right)-p\left( s+r \right).$$
Theorem 1
Let G = (p,q) and H = (r, s) be two connected graphs and F(G) = S(G),Q(G),M(G), or T(G). Then,
$$W\left( F\left( G \right)\left[ H \right] \right)={{r}^{2}}\left( W\left( F\left( G \right) \right)+q+p \right)-p\left( s+r \right)-rq$$
Proof. Let G =(p,q) and H =(r, s) be two connected graphs. By the definition of F (G)[H] it can be understood as obtained by taking p copies of H and by joining all the vertices of ith and jth copies of H if and only if the ith and jth vertices of G are adjacent. Also a pair of vertices of F (G)[H] whose first tuple is corresponding
to the edges of G are adjacent to the vertices of F (G)[H] if their first tuple are adjacent in F (G). Hence, the vertices in each copy of H of F (G)[H] are either adjacent (if they are adjacent in H) or are at distance 2 (if they are non-adjacent in H). A pair of verices of F (G)[H] belonging to different copies of H has the same distance as the corresponding two vertices of G. Also a pair of vertices of F (G)[H] corresponding to the edges of G, whose second tuple is not same and first tuple is same, has the distance always two. And a pair of verices of F (G)[H], whose first tuple is corresponding to the vertices of F (G) has the same distance as the corresponding two vertices of F (G). From this we get,
$$\begin{align}& W\left( F\left( G \right)\left[ H \right] \right)=p\left[ q+2\left\{ \left( ^{p}{{C}_{2}} \right)-s \right\} \right]+{{r}^{2}}W\left( F\left( G \right) \right)+2q\left( ^{r}{{C}_{2}} \right) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,={{r}^{2}}\left( W\left( F\left( G \right) \right)+q+p \right)-p\left( s+r \right)-rq. \\ \end{align}$$
Theorem 2
Let G = (p,q) and H = (r, s) be two connected graphs and F(G) = Λ(G),Λ[G],D2(G), or D2[G]. Then,
$$W\left( F\left( G \right)\left[ H \right] \right)={{r}^{2}}\left( W\left( F\left( G \right) \right)+2p \right)-p\left( s+2r \right).$$
Proof. Let G =(p,q) and H =(r, s) be two connected graphs. By the definition of F (G)[H] it can be understood as obtained by taking p copies of H and by joining all the vertices of ith and jth copies of H is and only if the ith and jth vertices of G are adjacent. Also a pair of vertices of F (G)[H] whose first tuple is twin of the vertices of G are adjacent to the vertices of F (G)[H] if their first tuple are adjacent in F (G). Hence, the vertices in each copy of H of F (G)[H] are either adjacent (if they are adjacent in H) or are at distance 2 (if they are non-adjacent in H). A pair of verices of F (G)[H] belonging to different copies of H has the same distance as the corresponding two vertices of G. Also a pair of vertices of F (G)[H] corresponding to twin of the vertices of G, whose second tuple is not same and first tuple is same, has the distance always two. And a pair of verices of F (G)[H], whose first tuple is corresponding to the vertices of F (G) has the same distance as the corresponding two vertices of F (G). From this we get,
$$\begin{align}& W\left( F\left( G \right)\left[ H \right] \right)=p\left[ q+2\left\{ \left( ^{p}{{C}_{2}} \right)-s \right\} \right]+{{r}^{2}}W\left( F\left( G \right) \right)+2p\left( ^{r}{{C}_{2}} \right) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,={{r}^{2}}\left( W\left( F\left( G \right) \right)+2p \right)-p\left( s+2r \right). \\ \end{align}$$
Conclusion
Here, we have defined new graph operations F-composition F (G)[H], where F (G) be one of the symbols S(G),M(G),Q(G),T(G),Λ(G),Λ[G],D2(G),D2[G]. Then, we gave some results for the Wiener indices of the these graph operations.
