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.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Algorithmica |
| ISSN | 0178-4617 |
| DOI | |
| Status | Udgivet - 2022 |
Emneord
- Chordal graphs
- Maximum number of edges
- Matching number