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.
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.
| Original language | English |
|---|---|
| Journal | Algorithmica |
| ISSN | 0178-4617 |
| DOIs | |
| Publication status | Published - 2022 |
Keywords
- Chordal graphs
- Maximum number of edges
- Matching number