Research Article
BibTex RIS Cite

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

Year 2022, , 63 - 66, 31.08.2022
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.

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.
Year 2022, , 63 - 66, 31.08.2022
https://doi.org/10.33187/jmsm.1058501

Abstract

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.
There are 5 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Articles
Authors

Mordechai Shalom 0000-0002-2688-5703

Publication Date August 31, 2022
Submission Date January 16, 2022
Acceptance Date March 19, 2022
Published in Issue Year 2022

Cite

APA Shalom, M. (2022). A Short Proof of the Size of Edge-Extremal Chordal Graphs. Journal of Mathematical Sciences and Modelling, 5(2), 63-66. https://doi.org/10.33187/jmsm.1058501
AMA Shalom M. A Short Proof of the Size of Edge-Extremal Chordal Graphs. Journal of Mathematical Sciences and Modelling. August 2022;5(2):63-66. doi:10.33187/jmsm.1058501
Chicago Shalom, Mordechai. “A Short Proof of the Size of Edge-Extremal Chordal Graphs”. Journal of Mathematical Sciences and Modelling 5, no. 2 (August 2022): 63-66. https://doi.org/10.33187/jmsm.1058501.
EndNote Shalom M (August 1, 2022) A Short Proof of the Size of Edge-Extremal Chordal Graphs. Journal of Mathematical Sciences and Modelling 5 2 63–66.
IEEE M. Shalom, “A Short Proof of the Size of Edge-Extremal Chordal Graphs”, Journal of Mathematical Sciences and Modelling, vol. 5, no. 2, pp. 63–66, 2022, doi: 10.33187/jmsm.1058501.
ISNAD Shalom, Mordechai. “A Short Proof of the Size of Edge-Extremal Chordal Graphs”. Journal of Mathematical Sciences and Modelling 5/2 (August 2022), 63-66. https://doi.org/10.33187/jmsm.1058501.
JAMA Shalom M. A Short Proof of the Size of Edge-Extremal Chordal Graphs. Journal of Mathematical Sciences and Modelling. 2022;5:63–66.
MLA Shalom, Mordechai. “A Short Proof of the Size of Edge-Extremal Chordal Graphs”. Journal of Mathematical Sciences and Modelling, vol. 5, no. 2, 2022, pp. 63-66, doi:10.33187/jmsm.1058501.
Vancouver Shalom M. A Short Proof of the Size of Edge-Extremal Chordal Graphs. Journal of Mathematical Sciences and Modelling. 2022;5(2):63-6.

29237    Journal of Mathematical Sciences and Modelling 29238

                   29233

Creative Commons License The published articles in JMSM are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.