Wiener index of generalized stars and their quadratic line graphs

Andrey A. Dobrynin; Leonid S. Mel'nikov

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 161-175
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Andrey A. Dobrynin, and Leonid S. Mel'nikov. "Wiener index of generalized stars and their quadratic line graphs." Discussiones Mathematicae Graph Theory 26.1 (2006): 161-175. <http://eudml.org/doc/270582>.

@article{AndreyA2006,
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.},
author = {Andrey A. Dobrynin, Leonid S. Mel'nikov},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance in a graph; Wiener index; star; iterated line graph; line graph},
language = {eng},
number = {1},
pages = {161-175},
title = {Wiener index of generalized stars and their quadratic line graphs},
url = {http://eudml.org/doc/270582},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Andrey A. Dobrynin
AU - Leonid S. Mel'nikov
TI - Wiener index of generalized stars and their quadratic line graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 161
EP - 175
AB - 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.
LA - eng
KW - distance in a graph; Wiener index; star; iterated line graph; line graph
UR - http://eudml.org/doc/270582
ER -

References

top
  1. [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. [2] S.H. Bertz, Branching in graphs and molecules, Discrete Appl. Math. 19 (1988) 65-83, doi: 10.1016/0166-218X(88)90006-6. Zbl0633.05063
  3. [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. [4] F. Buckley, Mean distance of line graphs, Congr. Numer. 32 (1981) 153-162. 
  5. [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. [6] Chemical Graph Theory - Introduction and Fundamentals, D. Bonchev and D.H. Rouvray, eds. (Gordon & Breach, New York, 1991). 
  7. [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. Zbl0913.05042
  8. [8] A.A. Dobrynin, Distance of iterated line graphs, Graph Theory Notes New York 37 (1998) 8-9. 
  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. Zbl0982.05044
  10. [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. Zbl0993.05059
  11. [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. Zbl0935.05040
  12. [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. Zbl1066.05060
  13. [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. Zbl1079.05031
  14. [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. Zbl1052.05029
  15. [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. [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. Zbl1080.05028
  17. [17] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283-296. Zbl0329.05112
  18. [18] R.C. Entringer, Distance in graphs: trees, J. Combin. Math. Combin. Comput. 24 (1997) 65-84. Zbl0880.05029
  19. [19] I. Gutman, Distance of line graphs, Graph Theory Notes New York 31 (1996) 49-52. 
  20. [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. [21] I. Gutman and L. Pavlović, More of distance of line graphs, Graph Theory Notes New York 33 (1997) 14-18. 
  22. [22] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer-Verlag, Berlin, 1986). Zbl0657.92024
  23. [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. [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. [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. [26] F. Harary, Graph Theory, (Addison Wesley, 1969). 
  27. [27] G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities (Cambridge University Press: Cambridge, 1934, 2nd ed. 1988). Zbl0010.10703
  28. [28] S. Nikolić, N. Trinajstić and Z. Mihalić, The Wiener index: developments and applications, Croat. Chem. Acta 68 (1995) 105-129. 
  29. [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. Zbl0552.05048
  30. [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. Zbl0603.05045
  31. [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. [32] N. Trinajstić, Chemical Graph Theory (CRC Press: Boca Raton, 1983; 2nd ed. 1992). 
  33. [33] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.