On the Zagreb index inequality of graphs with prescribed vertex degrees

被引：12

作者：

Andova, Vesna ^{[1
]}

Bogoev, Saso ^{[2
]}

Dimitrov, Darko ^{[3
]}

Pilipczuk, Marcin ^{[4
]}

Skrekovski, Riste ^{[5
]}

机构：

[1] Ss Cyril & Methodius Univ, Inst Math & Phys, Fac Elect Engn & Informat Technol, Skopje 1000, North Macedonia

[2] Minist Finance, IT Dept, Skopje 1000, North Macedonia

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

[4] Univ Warsaw, Inst Informat, PL-02097 Warsaw, Poland

[5] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 08期

关键词：

First Zagreb index; Second Zagreb index;

D O I：

10.1016/j.dam.2011.01.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a simple graph G with n vertices and m edges, the inequality M-1(G)/n <= M-2(G)/m. where M-1 (G) and M-2 (G) are the first and the second Zagreb indices of G, is known as the Zagreb indices inequality. A set S is good if for every graph whose degrees of vertices are in S, the inequality holds. We characterize that an interval [a, a + n] is good if and only if a >= n(n-1)/2 or [a, a + n] = [1,4]. We also present an algorithm that decides if an arbitrary set S of cardinality s is good, which requires O(s(2) logs) time and O(s) space. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：852 / 858

页数：7

共 17 条

[1]

Andova V, 2011, MATCH-COMMUN MATH CO, V65, P647

[2]

BALABAN AT, 1983, TOP CURR CHEM, V114, P21

[3] Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system [J].