A Short Proof of the Size of Edge-Extremal Chordal Graphs

Year 2022, Volume: 5 Issue: 2, 63 - 66, 31.08.2022

Mordechai Shalom

https://doi.org/10.33187/jmsm.1058501

Abstract

[3] have recently determined the maximum number of edges of a chordal graph with a maximum degree less than $d$ and the matching number at most $\nu$ by exhibiting a family of chordal graphs achieving this bound. We provide simple proof of their result.

Keywords

Chordal graphs, Edge-extremal graphs, Matching number

References

• [1] V. Chvatal, D. Hanson, Degrees and matchings, J. Comb. Theory., Ser. B, 20(2) (1976), 128–138.
• [2] N. Balachandran, N. Khare, Graphs with restricted valency and matching number, Discrete Mathematics, 309 (2009), 4176–4180.
• [3] J. R. S. Blair, P. Heggernes, P. T. Lima, D. Lokshtanov, On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number, Proceeding of the 14th Latin American Symposium on Theoretical Informatics (LATIN 2009), (2020), 600–612.
• [4] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory., 16 (1974), 47–56.
• [5] T. Ekim, M. Shalom, O. S¸eker, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, J. Comb. Optim., 41(3) (2021), 710–735.