On the difference between the Szeged and the Wiener index

被引：14

作者：

Bonamy, Marthe ^{[1
]}

Knor, Martin ^{[2
]}

Luzar, Borut ^{[3
]}

Pinlou, Alexandre ^{[4
,5
]}

Skrekovski, Riste ^{[3
,6
,7
]}

机构：

[1] CNRS, LaBRI, Talence, France

[2] Slovak Univ Technol Bratislava, Dept Math, Fac Civil Engn, Bratislava, Slovakia

[3] Fac Informat Studies, Novo Mesto, Slovenia

[4] Univ Montpellier, LIRMM, CNRS, Montpellier, France

[5] Univ Paul Valery Montpellier 3, Dept MIAp, Montpellier, France

[6] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[7] Univ Primorska, FAMNIT, Koper, Slovenia

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2017年 / 312卷

关键词：

Wiener index; Szeged index; Revised Szeged index; Szeged-Wiener relation; GRAPHS; DISTANCE;

D O I：

10.1016/j.amc.2017.05.047

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove a conjecture of Nadjafi-Arani et al. on the difference between the Szeged and the Wiener index of a graph (Nadjafi-Aranifi et al., 2012). Namely, if G is a 2-connected non-complete graph on n vertices, then Sz (G) - W (G) >= 2n - 6. Furthermore, the equality is obtained if and only if G is the complete graph Kn-1 with an extra vertex attached to either 2 or n - 2 vertices of We apply our method to strengthen some known results on the difference between the Szeged and the Wiener index of bipartite graphs, graphs of girth at least five, and the difference between the revised Szeged and the Wiener index. We also propose a stronger version of the aforementioned conjecture. (C) 2017 Elsevier Inc. All rights reserved.

引用

页码：202 / 213

页数：12

共 24 条

[1]

Al-Fozan T, 2014, MATCH-COMMUN MATH CO, V72, P339

[2]

Chen L, 2012, TRANS COMB, V1, P43

[3] The (revised) Szeged index and the Wiener index of a nonbipartite graph [J].

Chen, Lily ;

Li, Xueliang ;

Liu, Mengmeng .

EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 :237-246

[4]

Dobrynin A., 1995, Graph Theory Notes of New York, V28, P21

[5]

ENTRINGER RC, 1976, CZECH MATH J, V26, P283

[6]

Gutman I., 1994, Graph Theory Notes N. Y., V27, P9

[7]

Hansen P., 2010, P PLEN TALK INT C MA

[8] STATUS AND CONTRASTATUS [J].

HARARY, F .

SOCIOMETRY, 1959, 22 (01) :23-43

[9] THE SZEGED INDEX AND AN ANALOGY WITH THE WIENER INDEX [J].

KHADIKAR, PV ;

DESHPANDE, NV ;

KALE, PP ;

DOBRYNIN, A ;

GUTMAN, I ;

DOMOTOR, G .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1995, 35 (03) :547-550

[10] The Szeged and the Wiener index of graphs [J].

Klavzar, S ;

Rajapakse, A ;

Gutman, I .

APPLIED MATHEMATICS LETTERS, 1996, 9 (05) :45-49

← 1 2 3 →