2019/08/24 by Bickle, Allan, Che, Zhongyuan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1908.09202
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.