2017/06/14 by Culbertson, Jared, Guralnik, Dan P., Stiller, Peter F.
#05C22 #05C75 #51K05 #57Q10 #62H30 (secondary) #68R10 (primary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)
paper · doi:10.48550/arxiv.1706.04537
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.