Functions on adjacent vertex degrees of trees with given degree sequence

Hua Wang

Open Mathematics (2014)

  • Volume: 12, Issue: 11, page 1656-1663
  • ISSN: 2391-5455

Abstract

top
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 ) f o r a n y x ⩾ y a n d a ⩾ b , associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as ∑ u v ∈ E ( T ) f ( d e g ( u ) , d e g ( 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.

How to cite

top

Hua Wang. "Functions on adjacent vertex degrees of trees with given degree sequence." Open Mathematics 12.11 (2014): 1656-1663. <http://eudml.org/doc/268999>.

@article{HuaWang2014,
abstract = {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.},
author = {Hua Wang},
journal = {Open Mathematics},
keywords = {Degrees; Function; Index; Trees; vertex degrees; degree sequence; discrete symmetric function; greedy tree; Randic index; sum-connectivity index; harmonic index},
language = {eng},
number = {11},
pages = {1656-1663},
title = {Functions on adjacent vertex degrees of trees with given degree sequence},
url = {http://eudml.org/doc/268999},
volume = {12},
year = {2014},
}

TY - JOUR
AU - Hua Wang
TI - Functions on adjacent vertex degrees of trees with given degree sequence
JO - Open Mathematics
PY - 2014
VL - 12
IS - 11
SP - 1656
EP - 1663
AB - 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.
LA - eng
KW - Degrees; Function; Index; Trees; vertex degrees; degree sequence; discrete symmetric function; greedy tree; Randic index; sum-connectivity index; harmonic index
UR - http://eudml.org/doc/268999
ER -

References

top
  1. [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. Zbl0634.05054
  2. [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. [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 Zbl1009.05075
  4. [4] S. Fajtlowicz, On conjectures of Graffiti-II, Congr. Numer. 60 (1987) 187–197. Zbl0713.05054
  5. [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 Zbl0785.05065
  6. [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 Zbl1082.05025
  7. [7] M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc. 97(1975) 6609–6615. http://dx.doi.org/10.1021/ja00856a001 Zbl0770.60091
  8. [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 Zbl1022.05013
  9. [9] N. Schmuck, S. Wagner, H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants, MATCH Commun. Math.Comput.Chem. 68(2012) 273–292. Zbl1289.05145
  10. [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 Zbl1160.05016
  11. [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 Zbl1155.05020
  12. [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. [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. [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 Zbl1269.05022
  15. [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 Zbl1243.05126
  16. [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 Zbl1197.92060
  17. [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 Zbl1195.92083

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.