nach oben

Journal of Combinatorial Optimization

Erschienen in:

24.10.2016

On maximum Wiener index of trees and graphs with given radius

verfasst von: Kinkar Ch. Das, M. J. Nadjafi-Arani

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.

Vorheriger Artikel Recoverable robust spanning tree problem under interval uncertainty representations

Nächster Artikel Triple-solution approach for the strip packing problem with two-staged patterns

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aouchiche M, Bonnefoy JM, Fidahoussen A, Caporossi G, Hansen P, Hiesse L, Lachere J, Monhait A (2006) Variable neighborhood search for extremal graphs. 14. The autoGraphiX 2 system. In: Liberti L, Maculan N (eds) Global Optimization: from theory to implementation. Springer, New York, pp 281–310CrossRef

Bonchev D (2002) The Wiener number-some applications and new developments. In: Rouvray DH, King RB (eds) Topology in chemistry: discrete mathematics of molecules. Horwood, Chichester, pp 58–88CrossRef

Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan, New YorkCrossRefMATH

Chen Y, Wu B, An X (2013) Wiener index of graphs with radius two. ISRN Combinatorics. doi:10.1155/2013/906756

Das KC, Nadjafi-Arani MJ (2014) Comparison between the Szeged index and the eccentric connectivity index. Discrete Appl Math 186:74–86MathSciNetCrossRefMATH

Das KC, Gutman I, Nadjafi-Arani MJ (2015) Relations between distance-based and degree-based topological indices. Appl Math Comput 270:142–147MathSciNet

DeLaVina E, Waller B (2008) Spanning trees with many leaves and average distance. Electron J Combin 15(R33):16MathSciNetMATH

Dobrynin AA, Entringer R, Gutman I (2001) Wiener index of trees: theory and applications. Acta Appl Math 66:211–249MathSciNetCrossRefMATH

Fajtlowicz S, Waller WA (1987) On two conjectures of GRAFFITI II. Congr Numer 60:187–197MATH

Fischermann M, Hoffmann A, Rautenbach D, Székely L, Volkmann L (2003) Wiener index versus maximum degree in trees. Discrete Appl Math 122:127–137MathSciNetCrossRefMATH

Harary F (1959) Status and contrastatus. Sociometry 22(1):23–43MathSciNetCrossRef

Khodashenas H, Nadjafi-Arani MJ, Ashrafi AR, Gutman I (2011) A new proof of the Szeged–Wiener theorem. Kragujev J Math 35(1):165–172MathSciNetMATH

Klavžar S (2013) Structure of Fibonacci cubes: a survey. J Comb Optim 25:505–522MathSciNetCrossRefMATH

Klavžar S, Nadjafi-Arani MJ (2015) Cut method: update on recent developments and equivalence of independent approaches. Curr Org Chem 19(4):348–358CrossRef

Klavžar S, Nadjafi-Arani MJ (2014) Wiener index in weighted graphs via unification of \(\Theta ^{\ast }\)-classes. Eur J Combin 36:71–76MathSciNetCrossRefMATH

Klavžar S, Nadjafi-Arani MJ (2014) Improved bounds on the difference between the Szeged index and the Wiener index of graphs. Eur J Combin 39:148–156MathSciNetCrossRefMATH

Knor M, Škrekovski R, Tepeh A (2015) Mathematical aspects of Wiener index. arXiv:1510.00800

Liu H, Pan XF (2008) On the Wiener index of trees with fixed diameter. MATCH Commun Math Comput Chem 60:85–94MathSciNetMATH

Mukwembi S, Vetrik T (2014) Wiener index of trees of given order and diameter at most 6. Bull Aust Math Soc 89:379–396MathSciNetCrossRefMATH

Plesnik J (1984) On the sum of all distances in graph or diagraph. J Graph Theory 8:1–24MathSciNetCrossRefMATH

Škrekovski R, Gutman I (2014) Vertex version of the Wiener theorem. MATCH Commun Math Comput Chem 72:295–300MathSciNetMATH

Stevanović D (2008) Maximizing Wiener index of graphs with fixed maximum degree. MATCH Commun Math Comput Chem 60:71–83MathSciNetMATH

Su G, Xiong L, Su X, Chen X (2015) Some results on the reciprocal sum-degree distance of graphs. J Comb Optim 30:435. doi:10.1007/s10878-013-9645-5 MathSciNetCrossRefMATH

Wang H (2008) The extremal values of the Wiener index of a tree with given vertex degree sequence. Discrete Appl Math 156:2647–2656MathSciNetCrossRefMATH

Wiener H (1947) Structural determination of paraffin boiling points. J Am Chem Soc 69:17–20CrossRef

Wu B, An X, Liu G, Yan G, Liu X (2013) Minimum degree, edge-connectivity and radius. J Comb Optim 26(3):585–591MathSciNetCrossRefMATH

Titel: On maximum Wiener index of trees and graphs with given radius
verfasst von: Kinkar Ch. Das
M. J. Nadjafi-Arani
Publikationsdatum: 24.10.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0092-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Total edge irregularity strength of accordion graphs

A note on orientation and chromatic number of graphs

Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans

Matching and domination numbers in r-uniform hypergraphs

On Motzkin–Straus type results for non-uniform hypergraphs

Equitable vertex arboricity of 5-degenerate graphs