Discussiones Mathematicae Graph Theory 26(1) (2006) 161-175

WIENER INDEX OF GENERALIZED STARS AND THEIR QUADRATIC LINE GRAPHS

Andrey A. Dobrynin and Leonid S. Mel'nikov

Sobolev Institute of Mathematics
Russian Academy of Sciences
Siberian Branch, Novosibirsk 630090, Russia
e-mail: dobr@math.nsc.ru, omeln@math.nsc.ru

Abstract

The Wiener index, W, is the sum of distances between all pairs of vertices in a graph G. The quadratic line graph is defined as L(L(G)), where L(G) is the line graph of G. A generalized star S is a tree consisting of Δ ≥ 3 paths with the unique common endvertex. A relation between the Wiener index of S and of its quadratic graph is presented. It is shown that generalized stars having the property W(S) = W(L(L(S)) exist only for 4 ≤ Δ ≤ 6. Infinite families of generalized stars with this property are constructed.

Keywords and phrases: distance in a graph, Wiener index, star, iterated line graph.

2000 Mathematics Subject Classification: 05C12, 05C05.

References

[1] A.T. Balaban, I. Motoc, D. Bonchev and O. Mekenyan, Topological indices for structure-activity correlations, Topics Curr. Chem. 114 (1983) 21-55, doi: 10.1007/BFb0111212.
[2] S.H. Bertz, Branching in graphs and molecules, Discrete Appl. Math. 19 (1988) 65-83, doi: 10.1016/0166-218X(88)90006-6.
[3] S.H. Bertz and W.F. Wright, The graph theory approach to synthetic analysis: definition and application of molecular complexity and synthetic complexity, Graph Theory Notes New York 35 (1998) 32-48.
[4] F. Buckley, Mean distance of line graphs, Congr. Numer. 32 (1981) 153-162.
[5] E.R. Canfield, R.W. Robinson and D.H. Rouvray, Determination of the Wiener molecular branching index for the general tree, J. Comput. Chem. 6 (1985) 598-609, doi: 10.1002/jcc.540060613.
[6] Chemical Graph Theory - Introduction and Fundamentals, D. Bonchev and D.H. Rouvray, eds. (Gordon & Breach, New York, 1991).
[7] A.A. Dobrynin and I. Gutman, The Wiener index for trees and graphs of hexagonal systems, Diskretn. Anal. Issled. Oper. Ser. 2 5 (1998) 34-60, in Russian.
[8] A.A. Dobrynin, Distance of iterated line graphs, Graph Theory Notes New York 37 (1998) 8-9.
[9] A.A. Dobrynin, R. Entringer and I. Gutman, Wiener index for trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249, doi: 10.1023/A:1010767517079.
[10] A.A. Dobrynin, I. Gutman, S. Klavžar and P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247-294, doi: 10.1023/A:1016290123303.
[11] A.A. Dobrynin, I. Gutman and V. Jovasević, Bicyclic graphs and their line graphs with the same Wiener index, Diskretn. Anal. Issled. Oper. Ser. 2 4 (1997) 3-9, in Russian.
[12] A.A. Dobrynin and L.S. Mel'nikov, Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers, Appl. Math. Lett. 18 (2005) 307-312, doi: 10.1016/j.aml.2004.03.007.
[13] A.A. Dobrynin and L.S. Mel'nikov, Wiener index for graphs and their line graphs, Diskretn. Anal. Issled. Oper. Ser. 2 11 (2004) 25-44, in Russian.
[14] A.A. Dobrynin and L.S. Mel'nikov, Trees and their quadratic line graphs having the same Wiener index, MATCH Commun. Math. Comput. Chem. 50 (2004) 145-164.
[15] A.A. Dobrynin and L.S. Mel'nikov, Trees, quadratic line graphs and the Wiener index, Croat. Chem Acta 77 (2004) 477-480.
[16] A.A. Dobrynin and L.S. Mel'nikov, Wiener index, line graphs and the cyclomatic number, MATCH Commun. Math. Comput. Chem. 53 (2005) 209-214.
[17] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283-296.
[18] R.C. Entringer, Distance in graphs: trees, J. Combin. Math. Combin. Comput. 24 (1997) 65-84.
[19] I. Gutman, Distance of line graphs, Graph Theory Notes New York 31 (1996) 49-52.
[20] I. Gutman, V. Jovasević and A.A. Dobrynin, Smallest graphs for which the distance of the graph is equal to the distance of its line graph, Graph Theory Notes New York 33 (1997) 19.
[21] I. Gutman and L. Pavlović, More of distance of line graphs, Graph Theory Notes New York 33 (1997) 14-18.
[22] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer-Verlag, Berlin, 1986).
[23] I. Gutman, Y.N. Yeh, S.L. Lee and Y.L. Luo, Some recent results in the theory of the Wiener number, Indian J. Chem. 32A (1993) 651-661.
[24] I. Gutman and E. Estrada, Topological indices based on the line graph of the molecular graph, J. Chem. Inf. Comput. Sci. 36 (1996) 541-543, doi: 10.1021/ci950143i.
[25] I. Gutman, L. Popović, B.K. Mishra, M. Kaunar, E. Estrada and N. Guevara, Application of line graphs in physical chemistry. Predicting surface tension of alkanes, J. Serb. Chem. Soc. 62 (1997) 1025-1029.
[26] F. Harary, Graph Theory, (Addison Wesley, 1969).
[27] G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities (Cambridge University Press: Cambridge, 1934, 2nd ed. 1988).
[28] S. Nikolić, N. Trinajstić and Z. Mihalić, The Wiener index: developments and applications, Croat. Chem. Acta 68 (1995) 105-129.
[29] J. Plesnik, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984) 1-21, doi: 10.1002/jgt.3190080102.
[30] O.E. Polansky and D. Bonchev, The Wiener number of graphs. I. General theory and changes due to some graph operations, MATCH Commun. Math. Comput. Chem. 21 (1986) 133-186.
[31] D.H. Rouvray, Should we have designs on topological indices?, in: R.B. King, ed., Chemical Application of Topology and Graph Theory, (Elsevier, Amsterdam, 1983) 159-177.
[32] N. Trinajstić, Chemical Graph Theory (CRC Press: Boca Raton, 1983; 2nd ed. 1992).
[33] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005.

Received 24 June 2005
Revised 22 July 2005