Functions on adjacent vertex degrees of trees with given degree sequence
Hua Wang
Open Mathematics, Tome 12 (2014), p. 1656-1663 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this note we consider a discrete symmetric function f(x, y) where f(x,a)+f(y,b)⩾f(y,a)+f(x,b)foranyx⩾yanda⩾b, associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as ∑uv∈E(T)f(deg(u),deg(v)), are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:268999 
@article{bwmeta1.element.doi-10_2478_s11533-014-0439-5,
     author = {Hua Wang},
     title = {Functions on adjacent vertex degrees of trees with given degree sequence},
     journal = {Open Mathematics},
     volume = {12},
     year = {2014},
     pages = {1656-1663},
     zbl = {1295.05080},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0439-5}
}

Hua Wang. Functions on adjacent vertex degrees of trees with given degree sequence. Open Mathematics, Tome 12 (2014) pp. 1656-1663. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0439-5/

[1] D. Cvetković, M. Doob, H. Sachs, A. Torgašev, Recent results in the theory of graph spectra, Annals of Discrete Mathematics Series, North-Holland, 1988. | Zbl 0634.05054

[2] D. Cvetkovic, M. Petric, A table of connected graphs on six vertices, Discrete Math. 50 (1984) 37–49. http://dx.doi.org/10.1016/0012-365X(84)90033-5

[3] C. Delorme, O. Favaron, D. Rautenbach, On the Randic index, Discrete Math. 257 (2002) 29–38. http://dx.doi.org/10.1016/S0012-365X(02)00256-X | Zbl 1009.05075

[4] S. Fajtlowicz, On conjectures of Graffiti-II, Congr. Numer. 60 (1987) 187–197. | Zbl 0713.05054

[5] O. Favaron, M. Mahéo, J.F. Saclé, Some eigenvalue properties in graphs (conjectures of Graffiti-II), Discrete Math. 111(1993) 197–220. http://dx.doi.org/10.1016/0012-365X(93)90156-N | Zbl 0785.05065

[6] H. Liu, M. Lu, F. Tian, Trees of extremal connectivity index, Discrete Appl. Math. 154(2006) 106–119. http://dx.doi.org/10.1016/j.dam.2004.10.009 | Zbl 1082.05025

[7] M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc. 97(1975) 6609–6615. http://dx.doi.org/10.1021/ja00856a001 | Zbl 0770.60091

[8] D. Rautenbach, A note on trees of maximum weight and restricted degrees, Discrete Math. 271(2003) 335–342. http://dx.doi.org/10.1016/S0012-365X(03)00135-3 | Zbl 1022.05013

[9] N. Schmuck, S. Wagner, H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants, MATCH Commun. Math.Comput.Chem. 68(2012) 273–292. | Zbl 1289.05145

[10] H. Wang, Extremal trees with given degree sequence for the Randic index, Discrete Math. 308(2008) 3407–3411. http://dx.doi.org/10.1016/j.disc.2007.06.026 | Zbl 1160.05016

[11] H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Applied Mathematics, 156(2008) 2647–2654. http://dx.doi.org/10.1016/j.dam.2007.11.005 | Zbl 1155.05020

[12] H. Wiener, Structural determination of paraffin boiling point, J. Amer. Chem. Soc. 69(1947) 17–20. http://dx.doi.org/10.1021/ja01193a005

[13] X.-D. Zhang, Q.-Y. Xiang, L.-Q. Xu, R.-Y. Pan, The Wiener index of trees with given degree sequences, MATCH Commun.Math.Comput.Chem., 60(2008) 623–644.

[14] X.-M. Zhang, X.-D. Zhang, D. Gray, H. Wang, The number of subtrees of trees with given degree sequence, J. Graph Theory, 73(2013) 280–295. http://dx.doi.org/10.1002/jgt.21674 | Zbl 1269.05022

[15] L. Zhong, The harmonic index for graphs, Applied Math. Letters, 25(2012) 561–566. http://dx.doi.org/10.1016/j.aml.2011.09.059 | Zbl 1243.05126

[16] B. Zhou, N. Trinajstic, On a novel connectivity index, J. Math. Chem. 46(2009) 1252–1270. http://dx.doi.org/10.1007/s10910-008-9515-z | Zbl 1197.92060

[17] B. Zhou, N. Trinajstic, On general sum-connectivity index, J. Math. Chem. 47(2010) 210–218. http://dx.doi.org/10.1007/s10910-009-9542-4 | Zbl 1195.92083