Functions on adjacent vertex degrees of trees with given degree sequence

• Autorzy: Hua Wang
• Języki publikacji: EN

Abstrakty

EN

In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in 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.

Słowa kluczowe

EN

Degrees; Function; Index; Trees

Kategorie tematyczne

• 05C05: Trees
• 05C07: Vertex degrees
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2014
• Tom: 12
• Numer: 11
• Strony: 1656-1663

Daty

wydano

2014-11-01

online

2014-06-29

Twórcy

autor

Hua Wang

• Georgia Southern University

Bibliografia

• [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.
• [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
• [4] S. Fajtlowicz, On conjectures of Graffiti-II, Congr. Numer. 60 (1987) 187–197.
• [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
• [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
• [7] M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc. 97(1975) 6609–6615. http://dx.doi.org/10.1021/ja00856a001
• [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
• [9] N. Schmuck, S. Wagner, H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants, MATCH Commun. Math.Comput.Chem. 68(2012) 273–292.
• [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
• [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
• [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
• [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
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-014-0439-5