Skip to search boxSkip to navigationSkip to main content

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

  • United States Military Academy
    ,
  • University of Bergen
    ,
  • ,
  • University of California
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-review

Open access

Publication Information

Output type

Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-review

Original language

English

Journal (Volume, Issue Number)

Algorithmica

Publication milestones

  • Published - 2022

Publication status

Published - 2022

ISSN

0178-4617

Publication IDs

  • Scopus: 85126845996

Abstract

We determine the maximum number of edges that a chordal
graph G can have if its degree, ∆(G), and its matching number, ν(G), are bounded. To do so, we show that for every d, ν ∈ N, there exists a chordal graph G with ∆(G) < d and ν(G) < ν whose number of edges matches the upper bound, while having a simple structure: it is a disjoint union of cliques and stars.

Publication metrics

PlumX, opens in new tab

Citations
3
Captures
2