On Wiener Index of Graphs and Their Line Graphs

被引：0

作者：

Cohen, Nathann ^{[2
,3
]}

Dimitrov, Darko ^{[4
]}

Krakovski, Roi ^{[5
]}

Skrekovski, Riste ^{[1
,6
]}

Vukasinovic, Vida

机构：

[1] Inst Math Phys & Mech, Ljubljana 1111, Slovenia

[2] UNSA, I3S, CNRS, F-06902 Sophia Antipolis, France

[3] INRIA, F-06902 Sophia Antipolis, France

[4] Free Univ Berlin, Inst Informat, D-14195 Berlin, Germany

[5] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel

[6] Jozef Stefan Inst, Comp Syst Dept, Ljubljana 1000, Slovenia

来源：

MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY | 2010年 / 64卷 / 03期

关键词：

TOPOLOGICAL INDEXES; TREES; SYSTEMS; NUMBER;

D O I：

暂无

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

The Wiener index of a graph G, denoted by W(G), is the sum of distances between all pairs of vertices in G. In this paper, we consider the relation between the Wiener index of a graph G and its line graph L(G). We show that if G is of minimum degree at least two, then W(G) <= W (L(G)). We prove that for every non-negative integer go, there exists g > g(0), such that there are infinitely many graphs G of girth g, satisfying W(G) = W(L(G)). This partially answers a question raised by Dobrynin and Mel'nikov [10] and encourages us to conjecture that the answer to a stronger form of their question is affirmative.

引用

页码：683 / 698

页数：16

共 26 条

[1] Combinatorial Nullstellensatz
Alon, N
[J]. COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (1-2) : 7 - 29
[2] Resistance-distance matrix: A computational algorithm and its application
Babic, D
Klein, DJ
Lukovits, I
Nikolic, S
Trinajstic, N
[J]. INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2002, 90 (01) : 166 - 176
[3] Bian H, 2009, MATCH-COMMUN MATH CO, V61, P631
[4] Buckley F., 1981, C NUMER, V32, P153
[5] Chen AL, 2009, MATCH-COMMUN MATH CO, V61, P623
[6] The edge-Wiener index of a graph
Dankelmann, P.
Gutman, I.
Mukwembi, S.
Swart, H. C.
[J]. DISCRETE MATHEMATICS, 2009, 309 (10) : 3452 - 3457
[7] Dobrynin AA, 2005, MATCH-COMMUN MATH CO, V53, P209
[8] Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers
Dobrynin, AA
Mel'nikov, LS
[J]. APPLIED MATHEMATICS LETTERS, 2005, 18 (03) : 307 - 312
[9] Wiener index of hexagonal systems
Dobrynin, AA
Gutman, I
Klavzar, S
Zigert, P
[J]. ACTA APPLICANDAE MATHEMATICAE, 2002, 72 (03) : 247 - 294
[10] Wiener index of trees: Theory and applications
Dobrynin, AA
Entringer, R
Gutman, I
[J]. ACTA APPLICANDAE MATHEMATICAE, 2001, 66 (03) : 211 - 249

← 1 2 3 →