Wiener Number of Some Subgraphs in Archimedean Tilings

Yunjing Pan

Cheng Yi College, Jimei University, Xiamen, China.

DOI: 10.4236/am.2021.1211062                

Abstract

In this paper, we deduce Wiener number of some connected subgraphs in tilings (4, 4, 4, 4) and (4, 6, 12), which are in Archimedean tilings. And compute their average distance.

Keywords

Archimedean Tiling, Wiener Number, Binary Hamming Graph, Average Distance

1. Introduction

One of the molecular-graph-based quantity W, introduced by Harold Wiener in 1947 [1], is nowadays known as the name Wiener index or Wiener number. For a connected graph G, let V(G) denote the set of vertices and E(G) the set of edges. Then the Wiener number of G, denoted by W(G), is defined by:

$W\left(G\right)={\displaystyle \underset{u\mathrm{,}v\subseteq V\left(G\right)}{\sum }}d\left(u\mathrm{,}v\mathrm{<mo>\; |\; </mo>}G\right)$

where $d\left(u\mathrm{,}v\mathrm{<mo>\; |\; </mo>}G\right)$ is the distance between vertices of u and v, and the summation goes over all vertices in $V\left(G\right)$.

It is found that many physical and chemical properties that depend primarily on the compactness and the extent of branching are usually well correlated with W. And Wiener number has a lot of applications in different fields [2] [3] [4] [5].

From the definition of Wiener number, it is easy to find that the calculation of Wiener number in a lot of graphs is rather complicated. As a result, people research on the method of computing the Wiener number of graphs: such as the Wiener number of the hexagonal system; extremal tree on Wiener number and so on [6] [7] [8]. In 1947, Wiener already gave a much more convenient formula to compute the Wiener number of trees: we denote a tree by T, $n_1\left(e\right)$ and $n_2\left(e\right)$ are the number of vertices of T lying on the two sides of the edge e, then:

$W\left(T\right)={\displaystyle \underset{e}{\sum }}{n}_1\left(e\right)n_2(\; e\; )$

where the summation goes over all edges of T.

For a connected graph G, the average distance of G is another index, which depends on the Wiener number. The average distance of G is denoted by W(G), and is defined by:

$\bar{W}\left(G\right)=\frac{W\left(G\right)}{C_n^2}\mathrm{,}$ (1)

where n is the number of vertices of G.

A plane tiling $T=\left\{T_1\mathrm{,}{T}_2\mathrm{,}\cdots \right\}$ is a countable family of closed sets which covers the plane without gaps and overlaps, where $T_1\mathrm{,}{T}_2\mathrm{,}\cdots$ are known as tiles of T [9].

In a tiling, a vertex is of type $n_1{n}_2\cdots n_r$ if it is surrounded in cyclic order by regular n-gons of order $n_1,n_2,\cdots$ and $n_r$.

There exist precise 11 distinct types of edge-to-edge tilings by regular polygons such that all vertices of the tiling are of the same type. These 11 types of tilings are usually called Archimedean tilings [9].

They are: (3, 3, 3, 3, 3, 3), (4, 4, 4, 4), (6, 6, 6), (4, 4, 3, 3, 3), (4, 8, 8), (4, 3, 4, 3, 3), (6, 3, 6, 3), (6, 3, 3, 3, 3), (4, 6, 12), (12, 3, 12), (6, 4, 3, 4) (Figure 1).

In this paper, we shall restrict attention to Archimedean tilings. And the subgraphs in Archimedean tilings are simply-connected graphs.

Figure 1. Some archimedean tilings.

$\Sigma$ be a finite a alphabet and let $w_1$ and $w_2$ be words of equal length over $\Sigma$. $H\left(w_1\mathrm{,}{w}_2\right)$, the Hamming distance between $w_1$ and $w_2$, is the number of positions in which $w_1$ and $w_2$ differ. For the graph G, if each vertex $v\in V\left(G\right)$ can be labeled by a word $l\left(v\right)$ of fixed length, such that $H\left(l\left(u\right)\mathrm{,}l\left(v\right)\right)=d\left(u\mathrm{,}v\right)$ for all $u\mathrm{,}v\in V\left(G\right)$, we call it Hamming graph. In particular, if $\Sigma =\left\{\mathrm{0,1}\right\}$, we call G a binary Hamming graph.

G is a subgraph of one of tilings (4, 4, 4, 4), (6, 6, 6), (4, 8, 8), (4, 6, 12). An elementary cut segment C is a straight line segment drawn orthogonal to some edges; starting from the perimeter and ending at the perimeter; and touching the perimeter only twice; deleting the edges which orthogonal to C, there are exactly two connected components (Figure 2).

About fifty years later, Sandi Klavzar, Ivan Gutman, Bojan Mohar found a similarly convenient way to calculate the Wiener number of binary Hamming graphs [10]. Later, they proved that all connected subgraphs of tiling (6, 6, 6) are binary Hamming graphs, and they computed the Wiener number of some benzenoid hydrocarbons [11]. Furthermore, only four tilings in Archimedean tilings, which are (4, 4, 4, 4), (6, 6, 6), (4, 8, 8) and (4, 6, 12) tilings, all their connected subgraphs are binary Hamming graphs that are proved. And follow the way mentioned in [10], a convenient way to compute the Wiener number of the subgraphs of tilings (4, 4, 4, 4), (6, 6, 6), (4, 8, 8) and (4, 6, 12) are proved [12], which is called the elementary cut method. Let G be a binary Hamming graph on n vertices and with k elementary cut segments. For $i=1,\cdots ,k$, let $n_i$ be the number of vertices of G in one of the components of the graph obtained from G by removing the ith elementary cut.

Then:

$W\left(G\right)={\displaystyle \underset{i=1}{\overset{k}{\sum }}}{n}_i\left(n-n_i\right),$ (2)

The elementary cut method is similar to the formula to compute the Wiener number of trees.

In this paper, we deduce the Wiener number of some interesting subgraphs in tilings (4, 4, 4, 4) and (4, 6, 12), and compute their average distance.

Figure 2. Elementary cut segment.

2. The Wiener Number of Some Subgraphs in Tiling (4, 4, 4, 4) and (4, 6, 12)

1) Aztec diamond graph. A Aztec Diamond of order n, denoted by H_n, is a plane graph consisted by squares of length 1 (Figure 3 and Figure 4). Many work has been done about Aztec Diamond graph, such as the problem of perfect matching and independent set of it [10] [11]. Now we consider the Wiener number of Aztec Diamond.

In Figure 4, we give the horizontal elementary cut segments of H_n. There exist one additional groups of symmetry-equivalent elementary cut segments, obtained by rotating the former group by +90˚. Therefore, if one applies Equation (2) to only the horizontal elementary cut segments, the result will be just one second of the Wiener number of H_n.

Figure 3. Aztec diamond graph H₁, H₂, H₃, H₄.

Figure 4. Aztec diamond graph H_n.

First, we calculate the number of H_n. It is easy to get:

$\begin{array}{l}n\left(H_{n+1}\right)-n\left(H_n\right)=4n+4,\\ n\left(H_n\right)-n\left(H_{n-1}\right)=4(n-1)+4,\\ n\left(H_{n-1}\right)-n\left(H_{n-2}\right)=4(n-2)+4,\\ ⋮\\ n\left(H_2\right)-n\left(H_1\right)=4+4,\end{array}$

To sum up the equations above, we get:

$n\left(H_{n+1}\right)-n\left(H_1\right)=4\left(1+2+3+\cdots +n\right)+4n=2n^2+6n\mathrm{,}$

That is: $n\left(H_n\right)=2n^2+2n$.

For arbitrary horizontal elementary cut segment $C_i\left(i=1,2,\cdots ,n\right)$, $n\left(G_{C_i}^0\right)=2+4+\cdots +2i=i\left(i+1\right)$.

Denote $C_i\left(i=1,\cdots ,2n-1\right)$ contribute to the Wiener number of G is $W_1$, then we have:

$W_1={\displaystyle \underset{C_i}{\sum }}n\left(G_{C_i}^0\right)n\left(G_{C_i}^1\right)=2{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}}\left(i+1\right)i\left[2n^2+2n-i\left(i+1\right)\right]+n^2{\left(n+1\right)}^2,$

Simplify the equation above:

$W\left(H_n\right)=2W_1=\left(2/15\right)\left(14n^5+35n^4+20n^3-5n^2-4n\right).$

Furthermore, we get $\bar{W}\left(H\left(n\right)\right)=\frac{\left(2/15\right)\left(14n^5+35n^4+20n^3-5n^2-4n\right)}{C_{2n^2+2n}^2}$. When n gets large enough, $\bar{W}\left(H\left(n\right)\right)$ approximates to $\left(14/15\right)n$.

2) Zig-zag polyomino chain

As illustrate in Figure 5, it is a zig-zag chain G which contains n squares. Notice that n is even, suppose that $n=2m$. It is easy to get $n\left(G\right)=2n+2$.

In Figure 5 are indicated two groups of elementary cut segments: one group is horizontal elementary cut segments $C_i\left(i=1,\cdots ,m\right)$ (labeling from up to down), another group is $A_j\left(j=1,\cdots ,m+1\right)$ (labeling from left to right).

Denote $C_i\left(i=1,\cdots ,m\right)$ contribute to the Wiener number of G is $W_1$, $A_j\left(j=1,\cdots ,m+1\right)$ contribute to the Wiener number of G is $W_2$.

Figure 5. Zig-zag polyomino chain.

$W_1={\displaystyle \underset{C_i}{\sum }}n\left(G_{C_i}^0\right)n\left(G_{C_i}^1\right)=6\left(2n-1\right)+{\displaystyle \underset{k=1}{\overset{m-2}{\sum }}}\left(3+4k\right)\left(2n+2-3-4k\right),$

$W_2={\displaystyle \underset{A_j}{\sum }}n\left(G_{A_j}^0\right)n\left(G_{A_j}^1\right)=8n+10\left(2n-3\right)+{\displaystyle \underset{k=1}{\overset{m-3}{\sum }}}\left(5+4k\right)\left(2n+2-5-4k\right).$

Simplify the two equations above:

$W_1=\left(1/3\right)n^3+n^2+\left(7/6\right)n,$

$W_2=\left(1/3\right)n^3+n^2+\left(31/6\right)n-1.$

Then we get:

$W\left(G\right)=W_1+W_2=\left(2/3\right)n^3+2n^2+\left(19/3\right)n-1.$

Furthermore, we get $\bar{W}\left(G\right)=\frac{\left(2/3\right)n^3+2n^2+\left(19/3\right)n-1}{C_{2n+2}^2}$. When n gets large enough, $\bar{W}\left(H\left(n\right)\right)$ approximates to $\left(1/12\right)n$.

3) At last, we give a linear subgraph G of tiling (4, 6, 12), as illustrated in Figure 6. It contains n regular dodecagons.

It is easy to calculate: when $n=1$, $W\left(G\right)=2304$ ; when $n=2$, $W\left(G\right)=11556$ ; when $n=3$, $W\left(G\right)=29052$ ; when $n=4$, $W\left(G\right)=70020$. Next, we compute the Wiener number of G when $n\ge 5$.

It is easy to get the number of vertices of G is:

$n\left(G\right)=36+24\left(n-1\right)=24n+12.$

There are four groups elementary cut segments: the first is horizontal elementary cut segment C, $n\left(G_C^0\right)=12n+6$, denote C contribute to $W\left(G\right)$ is $W_1$ ; the second group is $H_k\left(k=1,2,\cdots ,2n+1\right)$, $n\left(G_{H_k}^0\right)=6+12k$, denote this group contribute to $W\left(G\right)$ is $W_2$ ; the third group is $A_j$ and ${A^{\prime }}_j$ $\left(j=1,2,\cdots ,n\right)$, here ${A^{\prime }}_j$ can be obtained by rotating $A_j$ a certain angle, so $A_j$ and ${A^{\prime }}_j$ $\left(j=1,2,\cdots ,n\right)$ contribute to $W\left(G\right)$ are the same, denote $A_j\left(j=1,2,\cdots ,n\right)$ contribute to $W\left(G\right)$ is $W_3$ ; the fourth group is $C_i$ and ${C^{\prime }}_i$ $\left(i=1,2,\cdots ,n+2\right)$, here ${C^{\prime }}_i$ can be obtained by rotating $C_i$ a certain angle, so $C_i$ and ${C^{\prime }}_i$ $\left(i=1,2,\cdots ,n+2\right)$ contribute to $W\left(G\right)$ are the same, denote $C_i$ $\left(i=1,2,\cdots ,n+2\right)$ contribute to $W\left(G\right)$ is $W_4$.

Figure 6. A linear subgraph G of tiling (4, 6, 12).

By calculating:

$W_1={\left(12n+6\right)}^2=144n^2+144n+36,$

$\begin{array}{c}{W}_2={\displaystyle \underset{H_k}{\sum }}n\left(G_{H_k}^0\right)n\left(G_{H_k}^1\right)\\ =6\left(24n+12-6\right)+{\displaystyle \underset{k=0}{\overset{2n}{\sum }}}\left(6+12k\right)\left(24n+12-6-12k\right)\\ =192n^3+288n^2+168n+36,\end{array}$

$\begin{array}{c}{W}_3={\displaystyle \underset{A_j}{\sum }}n\left(G_{A_j}^0\right)n\left(G_{A_j}^1\right)\\ ={\displaystyle \underset{j=0}{\overset{n-1}{\sum }}}\left(18+24j\right)\left(24n+12-18-24j\right)\\ =192n^3+288n^2+168n,\end{array}$

$\begin{array}{c}{W}_4={\displaystyle \underset{C_i}{\sum }}n\left(G_{C_i}^0\right)n\left(G_{C_i}^1\right)\\ =12\left(24n+12-6\right)+42\left(24n+12-21\right)+84\left(24n+12-42\right)\\ +{\displaystyle \underset{i=1}{\overset{n-4}{\sum }}}\left(42+24i\right)\left(24n+12-42-24i\right)\\ =96n^3+144n^2+516n-90.\end{array}$

Therefore the Wiener number of G is:

$W\left(G\right)=W_1+W_2+2W_3+2W_4=576n^3+1008n^2+1512n-108.$

Furthermore, we get $\bar{W}\left(G\right)=\frac{576n^3+1008n^2+1512n-108}{C_{24n+12}^2}$. When n gets large enough, $\bar{W}\left(H\left(n\right)\right)$ approximates to 2n.

3. Conclusion Remark

In this paper, we deduce the Wiener number of Aztec Diamond graph, zig-zag polyomino chain in tiling (4, 4, 4, 4) and a linear subgraph in tiling (4, 6, 12), and find their average distance.

Funding

This work was supported by the Fujian Provincial Department of Education Young and Middle-aged Teacher Education Research Project (No. JAT191154).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20. https://doi.org/10.1021/ja01193a005
[2]	Banerjee, S., Nath, D. and Chaudhuri, B.K. (1982) Phenomenological Theory of the Isostructural Phase Transition in H-Bonded and with a Pseudospin Model. Physical Review B, 25, 1883. https://doi.org/10.1103/PhysRevB.25.1883
[3]	Basak, S.C., Restrepo, G. and Villaveces, J.L. (2014) Advances in Mathematical Chemistry and Applications. Hentham Science e-book, Vol. 1.
[4]	Bonchev, D. (2002) The Wiener Number, Some Applications and New Developments. In: Topology in Chemistry: Discrete Mathematics of Molecules. Woodhead Publishing, Chichester, 58-88. https://doi.org/10.1016/B978-1-898563-76-1.50008-1
[5]	Diudea, M.V., Gutman, I. and Jantschi, L. (2001) Molecular Topology. Nova, Huntington.
[6]	Dobrynin, A.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
[7]	Shiu, W.C. and Lam, P.C.B. (1997) Wiener Numbers of Some Pericondensed Benzenoid Molecule Systems. Congrseeus Numerantium, 126, 113-124.
[8]	Gutman, I., Yeh, Y.N., Lee, S.L. and Luo, Y.L. (1993) Some Recent Results in the Theory of the Wiener Number. Indian Journal of Chemistry, 32A, 651-661.
[9]	Ng Lay Ling (2004) Tilings and Patterns. Honours Project, Department of Mathematics, National Univercity of Singapore.
[10]	Klavzar, S., Gutman, I. and Mohar, B. (1995) Labeling of Benzenoid Systems which Reflects the Vertex-Distance Relations. Journal of Chemical Information and Computer Science, 35, 590-593. https://doi.org/10.1021/ci00025a030
[11]	Gutman, I. and Klavzar, S. (1996) A Method for Calculating Wiener Numbers of Benzenoid Hydrocarbons. Models in Chemistry, 133, 389-399.
[12]	Pan, Y.J., Xie, M.F. and Zhang, F.J. (2018) Partial Cubes and Archimedean Tilings. Acta Mathematicae Applicatae Sinica., 34, 782-791. https://doi.org/10.1007/s10255-018-0788-0