Wiener Indices of Maximal k-Degenerate Graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021-03, Vol.37 (2), p.581-589
Main Authors: Bickle, Allan, Che, Zhongyuan
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Trees (mathematics)
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ≥ 2 k + 2 , we characterize all extremal graphs for the upper bound.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-020-02264-8