Edge erasures and chordal graphs

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

Abstract


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


chordal graphs; exposed edges; edge erasures; minimum spanning trees; weighted graphs; Kruskal's algorithm

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.13

References

G. Carlsson, Topology and data. Bull. Amer. Math. Soc., 46(2):255–308, 2009.

J. Culbertson, D.P. Guralnik, and P.F. Stiller, Functorial hierarchical clustering with overlaps. Discrete Appl. Math., 236:108–123, 2018.

P. De Caria. A joint study of chordal and dually chordal graphs. PhD thesis, Universidad Nacional de La Plata, 2012.

G.A. Dirac, On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 25(1):71–76, 1961.

A. Dochtermann and A. Engstrom, Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin., 9, 2009.

F.F. Dragan, Strongly orderable graphs: A common generalization of strongly chordal and chordal bipartite graphs, Discrete Appl. Math., 99(1-3):427–442, 2000.

H.T. Faal. Clique roots of K4-free chordal graphs, Electron. J. Graph Theory Appl., 7(1):105–111, 2019.

R. Froberg, On stanley-reisner rings, Banach Center Publications, 26(2):57–70, 1990.

D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15(3):835–855, 1965.

D.P. Guralnik, B. Moran, A. Pezeshki and O. Arslan, Detecting poisoning attacks on hierarchical malware classification systems, In SPIE Proceedings Vol. 10185: Cyber Sensing 2017.

H. Hajiabolhassan and M.L. Mehrabadi. On clique polynomials, Australas. J. Combin., 18:313–316, 1998.

D. Kozlov. Combinatorial Algebraic Topology, vol. 21, Springer Science & Business Media, 2007.

J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem, Proceeding of the American Mathematical Society, 7(1):48–50, 1956.

J. Spinrad and R. Sritharan, Algorithms for weakly triangulated graphs, Discrete Appl. Math., 59(2):181–191, 1995.

J.H.C. Whitehead, Simplicial spaces, nuclei and m-groups, Proc. Lond. Math. Soc., 2(1):243–327, 1939.

J.H.C. Whitehead, Simple homotopy types, Amer. J. Math., 72(1):1–57, 1950.

D. Zhu, D.P. Guralnik, X. Wang, X. Li and B. Moran, Statistical properties of the single linkage hierarchical clustering estimator, J. Statist. Plann. Inference, 185:15–28, 2017.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats