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

This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s00373-020-02264-8

Files

Metadata

Work Title Wiener Indices of Maximal k-Degenerate Graphs
Access
Open Access
Creators
  1. Allan Bickle
  2. Zhongyuan Che
License In Copyright (Rights Reserved)
Work Type Article
Publisher
  1. Springer Science and Business Media LLC
Publication Date January 9, 2021
Publisher Identifier (DOI)
  1. 10.1007/s00373-020-02264-8
Source
  1. Graphs and Combinatorics
Deposited May 27, 2022

Versions

Analytics

Collections

This resource is currently not in any collection.

Work History

Version 1
published

  • Created
  • Added WI-k-Degenerate-10-25-20-1.pdf
  • Added Creator Allan Bickle
  • Added Creator Zhongyuan Che
  • Published
  • Updated