Vol. 08  No. 04 ( 2019 ), Article ID: 29894 , 5 pages
10.12677/AAM.2019.84080

Wiener Index of Transformation Graph G---

Yanhua Zhao

College of Mathematics and System Science, Xinjiang University, Urumqi Xinjiang

Received: Apr. 3rd, 2019; accepted: Apr. 18th, 2019; published: Apr. 25th, 2019

ABSTRACT

The transformation graph G--- of a graph G is the graph with vertex set $V\left(G\right)\cup E\left(G\right)$ , in which two vertices u and v are joined by an edge if one of the following conditions holds: 1) $u,v\in V\left(G\right)$ and they are not adjacent in G, 2) $u,v\in E\left(G\right)$ and they are not adjacent in G, 3) one of u and v is in $V\left(G\right)$ while the other is in $E\left(G\right)$ , and they are not incident in G. The Wiener index $W\left(G\right)$ of G is the sum of the distances between all pairs of vertices in G. In this note, for any graph G, we determine the Wiener index of G---, when G--- is connected.

Keywords:Transformation Graph, Wiener Index

1. 引言

2. 主要内容

2.1. 预备知识

2.2. 直径小于等于2

Figure 1. $\text{diam}\left({G}^{---}\right)=3$

$W\left({G}^{---}\right)=\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n.$

$\begin{array}{c}W\left({G}^{---}\right)=\underset{u,v}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{u,e}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{e,f}{\sum }{d}_{{G}^{---}}\left(e,f\right)\\ =\left(\underset{uv\notin E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{uv\in E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)\right)+\left(\underset{{m}_{ue}=0}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{{m}_{ue}=1}{\sum }{d}_{{G}^{---}}\left(u,e\right)\right)\\ +\left(\underset{{m}_{ef}=0}{\sum }{d}_{{G}^{---}}\left(e,f\right)+\underset{{m}_{ef}=1}{\sum }{d}_{{G}^{---}}\left(e,f\right)\right)\\ =\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-m+2m\right)+\left(mn-2m+4m\right)+\left(\left(\begin{array}{c}m\\ 2\end{array}\right)-\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)+2\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)\right)\\ =\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n.\end{array}$

2.3. 直径等于3

1) $W\left({G}^{---}\right)=\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+1$

2) $W\left({G}^{---}\right)=\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+4$

3) $W\left({G}^{---}\right)=\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+2$

4) $W\left({G}^{---}\right)=\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+3$

$\begin{array}{c}W\left({G}^{---}\right)=\underset{u,v}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{u,e}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{e,f}{\sum }{d}_{{G}^{---}}\left(e,f\right)\\ =\left(\underset{uv\notin E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{uv\in E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)\right)+\left(\underset{{m}_{ue}=0}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{{m}_{ue}=1}{\sum }{d}_{{G}^{---}}\left(u,e\right)\right)\\ +\left(\underset{{m}_{ef}=0}{\sum }{d}_{{G}^{---}}\left(e,f\right)+\underset{{m}_{ef}=1}{\sum }{d}_{{G}^{---}}\left(e,f\right)\right)\\ =\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-m+2\left(m-1\right)+3\right)+\left(mn-2m+4m\right)+\left(\left(\begin{array}{c}m\\ 2\end{array}\right)-\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)+2\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)\right)\\ =\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+1.\end{array}$

$\begin{array}{c}W\left({G}^{---}\right)=\underset{u,v}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{u,e}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{e,f}{\sum }{d}_{{G}^{---}}\left(e,f\right)=\left(\underset{uv\notin E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{uv\in E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)\right)\\ +\left(\underset{{m}_{ue}=0}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{{m}_{ue}=1}{\sum }{d}_{{G}^{---}}\left(u,e\right)\right)+\left(\underset{{m}_{ef}=0}{\sum }{d}_{{G}^{---}}\left(e,f\right)+\underset{{m}_{ef}=1}{\sum }{d}_{{G}^{---}}\left(e,f\right)\right)\\ =\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-m+2\left(m-2\right)+3×2\right)+\left(mn-2m+2\left(2m-2\right)+3×2\right)\\ +\left(\left(\begin{array}{c}m\\ 2\end{array}\right)-\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)+2\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)\right)\\ =\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+4.\end{array}$

$\begin{array}{c}W\left({G}^{---}\right)=\underset{u,v}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{u,e}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{e,f}{\sum }{d}_{{G}^{---}}\left(e,f\right)\\ =\left(\underset{uv\notin E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{uv\in E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)\right)\\ +\left(\underset{{m}_{ue}=0}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{{m}_{ue}=1}{\sum }{d}_{{G}^{---}}\left(u,e\right)\right)+\left(\underset{{m}_{ef}=0}{\sum }{d}_{{G}^{---}}\left(e,f\right)+\underset{{m}_{ef}=1}{\sum }{d}_{{G}^{---}}\left(e,f\right)\right)\\ =\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-m+2\left(m-1\right)+3\right)+\left(mn-2m+2\left(2m-1\right)+3\right)+\left(\left(\begin{array}{c}m\\ 2\end{array}\right)-\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)+2\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)\right)\\ =\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+2.\end{array}$

$\begin{array}{c}W\left({G}^{---}\right)=\underset{u,v}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{u,e}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{e,f}{\sum }{d}_{{G}^{---}}\left(e,f\right)\\ =\left(\underset{uv\notin E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)+\underset{uv\in E\left(G\right)}{\sum }{d}_{{G}^{---}}\left(u,v\right)\right)+\left(\underset{{m}_{ue}=0}{\sum }{d}_{{G}^{---}}\left(u,e\right)+\underset{{m}_{ue}=1}{\sum }{d}_{{G}^{---}}\left(u,e\right)\right)\\ +\left(\underset{{m}_{ef}=0}{\sum }{d}_{{G}^{---}}\left(e,f\right)+\underset{{m}_{ef}=1}{\sum }{d}_{{G}^{---}}\left(e,f\right)\right)\\ =\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-m+2\left(m-1\right)+3\right)+\left(mn-2m+2\left(2m-2\right)+3×2\right)+\left(\left(\begin{array}{c}m\\ 2\end{array}\right)-\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)+2\underset{v\in V\left(G\right)}{\sum }\left(\begin{array}{c}{d}_{G}\left(v\right)\\ 2\end{array}\right)\right)\\ =\frac{1}{2}\left({m}^{2}+{n}^{2}+\underset{v\in V\left(G\right)}{\sum }{d}_{G}^{2}\left(v\right)\right)+mn+\frac{3}{2}m-\frac{1}{2}n+3.\end{array}$

Wiener Index of Transformation Graph G---[J]. 应用数学进展, 2019, 08(04): 703-707. https://doi.org/10.12677/AAM.2019.84080

1. 1. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. American Elsevier, New York, Macmillan, London.

2. 2. Wiener, H. (1947) Structural Determination of Paraffin Boiling Point. Journal of the American Chemical Society, 69, 17-20. https://doi.org/10.1021/ja01193a005

3. 3. Entringer, R.C., Jackson, D.E. and Snyder, D.A. (1976) Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296.

4. 4. Dobrynin, A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Applications. Acta Applicandae Mathematica, 66, 211-249. https://doi.org/10.1023/A:1010767517079

5. 5. Wu, B. and Meng, J. (2001) Basic Properties of Total Transformation Graphs. Journal of Mathematical Study, 34, 109-116.

6. 6. Wu, B., Zhang, L. and Zhang, Z. (2005) The Transformation Graph Gxyz When xyz = −++. Discrete Mathematics, 296, 263-270.

7. 7. Chen, J. (2006) Super Edge-Connectivity of Two Classes of Transformation Graphs. Doctoral Thesis, Xinjiang University, Urumchi.

8. 8. Xu, L. and Wu, B. (2008) Transformation Graph . Discrete Mathematics, 308, 5144-5148.