Cycles, the Degree Distance, and the Wiener Index

Affiliation(s)

Department of Mathematics, University of Florida, Gainesville, USA.

Department of Mathematical Sciences, Georgia Southern University, Statesboro, USA.

Department of Mathematics, University of Florida, Gainesville, USA.

Department of Mathematical Sciences, Georgia Southern University, Statesboro, USA.

ABSTRACT

The degree distance of a graph G is , where and are the degrees of vertices , and is the distance between them. The Wiener index is defined as . An elegant result (Gutman; Klein, Mihali?,, Plav?i? and Trinajsti?) is known regarding their correlation, that for a tree T with n vertices. In this note, we extend this study for more general graphs that have frequent appearances in the study of these indices. In particular, we develop a formula regarding their correlation, with an error term that is presented with explicit formula as well as sharp bounds for unicyclic graphs and cacti with given parameters.

The degree distance of a graph G is , where and are the degrees of vertices , and is the distance between them. The Wiener index is defined as . An elegant result (Gutman; Klein, Mihali?,, Plav?i? and Trinajsti?) is known regarding their correlation, that for a tree T with n vertices. In this note, we extend this study for more general graphs that have frequent appearances in the study of these indices. In particular, we develop a formula regarding their correlation, with an error term that is presented with explicit formula as well as sharp bounds for unicyclic graphs and cacti with given parameters.

Cite this paper

D. Gray and H. Wang, "Cycles, the Degree Distance, and the Wiener Index,"*Open Journal of Discrete Mathematics*, Vol. 2 No. 4, 2012, pp. 156-159. doi: 10.4236/ojdm.2012.24031.

D. Gray and H. Wang, "Cycles, the Degree Distance, and the Wiener Index,"

References

[1] H. Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of the American Chemical Society, Vol. 69, No. 1, 1947, pp. 17-20. doi:10.1021/ja01193a005

[2] A. A. Dobrynin and A. A. Kochetova, “Degree Distance of A Graph: A Degree Analogue of the Wiener Index,” Journal of Chemical Information and Computer Sciences, Vol. 34, No. 5, 1994, pp. 1082-1086. doi:10.1021/ci00021a008

[3] P. Dankelmann, I. Gutman, S. Mukwembi and H. C. Swart, “On the Degree Distance of a Graph,” Discrete Applied Mathematics, Vol. 157, No. 13, 2009, pp. 2773-2777. doi:10.1016/j.dam.2009.04.006

[4] A. A. Dobrynin, R. Entringer and I. Gutman, “Wiener Index of Trees: Theory and Applications,” Acta Applicandae Mathematicae, Vol. 66, No. 3, 2001, pp. 211-249. doi:10.1023/A:1010767517079

[5] Z. Du and B. Zhou, “Minimum Wiener Indices of Trees and Unicyclic Graphs of Given Matching Number,” Match, Vol. 63, No. 1, 2010, pp. 101-112.

[6] M. Fischermann, A. Hoffmann, D. Rautenbach, L. A. Székely and L. Volkmann, “Wiener Index versus Maximum Degree in Trees,” Discrete Applied Mathematics, Vol. 122, No. 1-3, 2002, pp. 127-137. doi:10.1016/S0166-218X(01)00357-2

[7] H. Liu and M. Lu, “A Unified Approach to Cacti for Different Indices,” Match, Vol. 58, No. 1, 2007, pp. 183-194.

[8] A. I. Tomescu, “Properties of Connected Graphs Having Minimum Degree Distance,” Discrete Applied Mathematics, Vol. 309, No. 9, 2009, pp. 2745-2748. doi:10.1016/j.disc.2008.06.031

[9] A. I. Tomescu, “Unicyclic and Bicyclic Graphs Having Minimum Degree Distance,” Discrete Applied Mathematics, Vol. 156, No. 2, 2008, pp. 125-130. doi:10.1016/j.dam.2007.09.010

[10] I. Gutman, “Selected Properties of the Schultz Molecular Topological Index,” Journal of Chemical Information and Computer Sciences, Vol. 34, No. 5, 1994, pp. 1087-1089. doi:10.1021/ci00021a009

[11] D. J. Klein, Z. Mihalic′, D. Plav?ic′ and N. Trinajstic′, “Molecular Topological Index: A Relation with the Wiener Index,” Journal of Chemical Information and Computer Sciences, Vol. 32, No. 4, 1992, pp. 304-305.

[1] H. Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of the American Chemical Society, Vol. 69, No. 1, 1947, pp. 17-20. doi:10.1021/ja01193a005

[2] A. A. Dobrynin and A. A. Kochetova, “Degree Distance of A Graph: A Degree Analogue of the Wiener Index,” Journal of Chemical Information and Computer Sciences, Vol. 34, No. 5, 1994, pp. 1082-1086. doi:10.1021/ci00021a008

[3] P. Dankelmann, I. Gutman, S. Mukwembi and H. C. Swart, “On the Degree Distance of a Graph,” Discrete Applied Mathematics, Vol. 157, No. 13, 2009, pp. 2773-2777. doi:10.1016/j.dam.2009.04.006

[4] A. A. Dobrynin, R. Entringer and I. Gutman, “Wiener Index of Trees: Theory and Applications,” Acta Applicandae Mathematicae, Vol. 66, No. 3, 2001, pp. 211-249. doi:10.1023/A:1010767517079

[5] Z. Du and B. Zhou, “Minimum Wiener Indices of Trees and Unicyclic Graphs of Given Matching Number,” Match, Vol. 63, No. 1, 2010, pp. 101-112.

[6] M. Fischermann, A. Hoffmann, D. Rautenbach, L. A. Székely and L. Volkmann, “Wiener Index versus Maximum Degree in Trees,” Discrete Applied Mathematics, Vol. 122, No. 1-3, 2002, pp. 127-137. doi:10.1016/S0166-218X(01)00357-2

[7] H. Liu and M. Lu, “A Unified Approach to Cacti for Different Indices,” Match, Vol. 58, No. 1, 2007, pp. 183-194.

[8] A. I. Tomescu, “Properties of Connected Graphs Having Minimum Degree Distance,” Discrete Applied Mathematics, Vol. 309, No. 9, 2009, pp. 2745-2748. doi:10.1016/j.disc.2008.06.031

[9] A. I. Tomescu, “Unicyclic and Bicyclic Graphs Having Minimum Degree Distance,” Discrete Applied Mathematics, Vol. 156, No. 2, 2008, pp. 125-130. doi:10.1016/j.dam.2007.09.010

[10] I. Gutman, “Selected Properties of the Schultz Molecular Topological Index,” Journal of Chemical Information and Computer Sciences, Vol. 34, No. 5, 1994, pp. 1087-1089. doi:10.1021/ci00021a009

[11] D. J. Klein, Z. Mihalic′, D. Plav?ic′ and N. Trinajstic′, “Molecular Topological Index: A Relation with the Wiener Index,” Journal of Chemical Information and Computer Sciences, Vol. 32, No. 4, 1992, pp. 304-305.