Electronic Journal of Graph Theory and Applications (Oct 2021)

Edge erasures and chordal graphs

  • Jared Culbertson,
  • Dan P. Guralnik,
  • Peter F. Stiller

DOI
https://doi.org/10.5614/ejgta.2021.9.2.13
Journal volume & issue
Vol. 9, no. 2
pp. 409 – 418

Abstract

Read online

We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph. This leads to a characterization of chordal graphs via deletions of a sequence of exposed edges from a complete graph. Most interesting is that in this context the connected components of the edge-induced subgraph of exposed edges are 2-edge connected. We use this latter fact in the weighted case to give a modified version of Kruskal's second algorithm for finding a minimum spanning tree in a weighted chordal graph. This modified algorithm benefits from being local in an important sense.

Keywords