Wiener Indices of Maximal k-Degenerate Graphs

被引：8

作者：

Bickle, Allan ^{[1
]}

Che, Zhongyuan ^{[2
]}

机构：

[1] Penn State Univ, Dept Math, Altoona Campus, Altoona, PA 16601 USA

[2] Penn State Univ, Dept Math, Beaver Campus, Monaca, PA 15061 USA

来源：

GRAPHS AND COMBINATORICS | 2021年 / 37卷 / 02期

关键词：

k-Tree; Maximal k-degenerate graph; Wiener index; DISTANCE;

D O I：

10.1007/s00373-020-02264-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is maximal k-degenerate if each induced subgraph has a vertex of degree at most k and adding any new edge to the graph violates this condition. In this paper, we provide sharp lower and upper bounds on Wiener indices of maximal k-degenerate graphs of order n >= k >= 1. A graph is chordal if every induced cycle in the graph is a triangle and chordal maximal k-degenerate graphs of order n >= k are k-trees. For k-trees of order n >= 2k + 2, we characterize all extremal graphs for the upper bound.

引用

页码：581 / 589

页数：9

共 50 条

[21] On the maximal eccentric connectivity indices of graphs
Jian-bin Zhang
Zhong-zhu Liu
Bo Zhou
Applied Mathematics-A Journal of Chinese Universities, 2014, 29 : 374 - 378
[22] On the maximal eccentric connectivity indices of graphs
ZHANG Jian-bin
LIU Zhong-zhu
ZHOU Bo
Applied Mathematics:A Journal of Chinese Universities, 2014, (03) : 374 - 378
[23] On the maximal eccentric connectivity indices of graphs
Zhang Jian-bin
Liu Zhong-zhu
Zhou Bo
APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B, 2014, 29 (03) : 374 - 378
[24] Computing Wiener and hyper-Wiener indices of unitary Cayley graphs
Loghman, Amir
IRANIAN JOURNAL OF MATHEMATICAL CHEMISTRY, 2012, 3 (02): : 121 - 125
[25] Graphs with the second and third maximum Wiener indices over the 2-vertex connected graphs
Bessy, Stephane
Dross, Francois
Knor, Martin
Skrekovski, Riste
DISCRETE APPLIED MATHEMATICS, 2020, 284 : 195 - 200
[26] The nine smallest hyper-Wiener indices of trees and the eight smallest hyper-Wiener (Wiener) indices of unicyclic graphs
Liu, Muhuo
Liu, Bolian
UTILITAS MATHEMATICA, 2014, 95 : 129 - 139
[27] ON THE VERTEX-EDGE WIENER INDICES OF THORN GRAPHS
Azari, Mahdieh
MATEMATICKI VESNIK, 2019, 71 (03): : 263 - 276
[28] WIENER AND VERTEX PI INDICES OF THE STRONG PRODUCT OF GRAPHS
Pattabiraman, K.
Paulraja, P.
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (04) : 749 - 769
[29] Wiener and vertex PI indices of Kronecker products of graphs
Hoji, Marhaba
Luo, Zhaoyang
Vumar, Elkin
DISCRETE APPLIED MATHEMATICS, 2010, 158 (16) : 1848 - 1855
[30] ON A RELATION BETWEEN SZEGED AND WIENER INDICES OF BIPARTITE GRAPHS
Chen, L.
Li, X.
Liu, M.
Gutman, I.
TRANSACTIONS ON COMBINATORICS, 2012, 1 (04) : 43 - 49

← 1 2 3 4 5 →