Wiener Indices of Maximal k-Degenerate Graphs

Allan Bickle; Zhongyuan Che

doi:10.1007/s00373-020-02264-8

Wiener Indices of Maximal k-Degenerate Graphs

Allan Bickle, Zhongyuan Che

Penn State Beaver

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	581-589
Number of pages	9
Journal	Graphs and Combinatorics
Volume	37
Issue number	2
DOIs	https://doi.org/10.1007/s00373-020-02264-8
State	Published - Mar 2021

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-020-02264-8

Cite this

@article{0dfb2fd8d807408bacabeb89ab7624cd,

title = "Wiener Indices of Maximal k-Degenerate Graphs",

abstract = "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.",

author = "Allan Bickle and Zhongyuan Che",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK part of Springer Nature.",

year = "2021",

month = mar,

doi = "10.1007/s00373-020-02264-8",

language = "English (US)",

volume = "37",

pages = "581--589",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - Wiener Indices of Maximal k-Degenerate Graphs

AU - Bickle, Allan

AU - Che, Zhongyuan

PY - 2021/3

Y1 - 2021/3

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

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

UR - http://www.scopus.com/inward/record.url?scp=85099264220&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099264220&partnerID=8YFLogxK

U2 - 10.1007/s00373-020-02264-8

DO - 10.1007/s00373-020-02264-8

M3 - Article

AN - SCOPUS:85099264220

SN - 0911-0119

VL - 37

SP - 581

EP - 589

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

Wiener Indices of Maximal k-Degenerate Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this