Jared Culbertson^a , Dan P. Guralnik^b , Peter F. Stiller^c

^aSensors Directorate, Air Force Research Laboratory, 2241 Avionics Circle, Bldg. 620, Wright–Patterson Air Force Base, Ohio 45433-7302, USA.

jared.culbertson@afresearchlab.com, danguralnik@ufl.edu, stiller@math.tamu.edu

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 edgeinduced 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 Mathematics Subject Classification: 05C22, 05C75, 68R10 (primary), 57Q10, 51K05, 62H30 (secondary) DOI: 10.5614/ejgta.2021.9.2.13

1. Introduction

In this short paper we prove several results about chordal graphs by focusing on edges which are each properly contained in a unique maximal complete subgraph; these we call exposed edges. Our first result gives a characterization of chordal graphs as those that can be produced through a

Received: 12 December 2018, Revised: 2 May 2021, Accepted: 10 May 2021.

^bMechanical & Aerospace Engineering, University of Florida, MAE-B, room 327A, 633 Gale Lemerand Dr, Gainesville, FL 32603, USA.

^cDepartment of Mathematics, MS3368, Texas A&M University, College Station, Texas 77843-3368, USA.

Figure 1. A sequence of three erasures of exposed edges, left to right, performed on a chordal graph (cliques illustrated as simplices for emphasis). Exposed edges being deleted are marked in red; the other exposed edges are marked with yellow dashes. Transitions (a→b→c) introduce new exposed edges; transition (c→d) turns an exposed edge into an unexposed one. This effect is even more pronounced with larger cliques. Finally, note how all transitions are marked with stark changes to the topology of the edge-induced subgraph of exposed edges.

sequence of exposed edge deletions starting from a complete graph. This characterization does not follow immediately from the usual vertex-centric characterizations of chordal graphs in terms of elimination orderings or minimal separators, and is also distinct from the important representation of chordal graphs as intersection graphs of a family of subtrees of a tree (see [3] for a survey of these). The edge deletions that we consider are different from the edge-without-vertex elimination orderings of related graph classes (for example, see the characterization of strongly orderable graphs in [6]).

At first glance, one might think that exposed edges could be added to or removed from a chordal graph en masse while maintaining chordality. However, the edge-induced subgraph of exposed edges in a chordal graph can change dramatically through a single deletion of an exposed edge, turning exposed edges into unexposed ones, and vice-versa (see Figure 1). Moreover, in the reverse direction, care must be taken when adding an edge to a chordal graph to ensure that the edge is both exposed in the larger graph and that the graph remains chordal.

Despite the unruly behavior of the edge-induced subgraph of exposed edges, we are able to circumvent the problems this creates by proving that its connected components are always 2-edge connected. This, in turn, leads to a third result, namely a variation of Kruskal's second algorithm [13] for finding a minimum spanning tree in a weighted graph, with its attached relationship to ultrametrics and single-linkage clustering. This relationship is discussed in more detail in Section 3. A potential application of our characterization would be to extend the results of [7] on clique roots of K4-free chordal graphs to a broader family using an inductive computation of clique polynomials based on the technique of [11, Lemma 1].

Our early investigations were motivated by applications of data clustering (see [2], a survey [1], and some applications discussed in [17, 10]) and a search for an adequate notion of a minimum spanning complex for our Aⁿ clustering methods, analogous to the role played by minimum spanning trees for single-linkage clustering. The results in this paper directly apply to the topological study of flag complexes obtainable by collapses from a simplex. In fact, the language is interchangeable since the flag condition means the abstract simplicial complex is completely determined by its 1-skeleton. We have chosen the graph theoretical language for a more consistent presentation, but all the results can be restated topologically in terms of chordal complexes, which are flag complexes whose 1-skeleton is a chordal graph. For example, our process of deleting an

exposed edge produces a simple strong deformation retraction of the associated chordal complex. For more on this topological perspective and the relationship to simplicial collapses, see the final section of the paper.

2. Exposed edges in chordal graphs: erasures and edge connectivity

We begin by collecting some basic definitions, notation, and terminology.

Definition 2.1. Let G = (V, E) be an undirected simple graph (with no loops or multiple edges) having finite vertex set V and edge set E. The degree of a vertex v will be denoted by degG(v). The open G-neighborhood of a vertex v ∈ V is

\[N_G(v) = \{ w \in V \setminus \{v\} \mid vw \in E \}.\]

The closed neighborhood NG[v] = NG(v) ∪ {v}. We will denote the induced subgraph on A ⊆ V by G[A]. On occasion, we will simplify notation by understanding NG(v) or NG[v] to be the induced subgraph G[NG(v)] or G[NG[v]]. Whether we are referring to the induced subgraph or just the vertex set will be clear from the context. In particular, complete subgraphs will occasionally be referred to as cliques. Note G[NG(v)] is sometimes called the link of v, particularly in a more topological setting.

If v1, . . . , v^k is an ordering on V , let Gⁱ = G[{vⁱ , . . . , vk}]. A vertex v is simplicial if the induced subgraph on NG[v] is complete. We say that a graph has a perfect elimination ordering if there is some ordering of V such that vⁱ is simplicial in Gⁱ for each 1 ≤ i ≤ k. Recall also that a bridge is a cut-edge, that is, an edge whose removal increases the number of connected components of the graph.

Definition 2.2. An undirected simple graph G is chordal if every induced cycle has length three. Chordality is an induced-hereditary property.

There are many characterizations of chordal graphs available in the literature. We will not attempt here to give a full survey of the relevant results, but rather point the reader to [3], which provides an excellent guide to the related literature. However, there is one characterization that we will need in the sequel and one implication—we combine those as a theorem here.

Theorem 2.1 ([4, 9]). A graph is chordal if and only if it has a perfect elimination ordering. Moreover, any chordal graph is either complete or has two non-adjacent simplicial vertices.

Borrowing from topology, and to simplify the exposition, we refer to an edge whose endpoints induce a two-element maximal clique as a facet edge. The following lemma, however, states that for chordal graphs, the notions of bridge and facet edge are equivalent; although this is not true for an arbitrary graph (a non-bridge facet edge is in an induced cycle of length at least four).

Lemma 2.1. Let G be a graph. If an edge xy ∈ G is a bridge, then it is a facet edge. Additionally, if G is chordal, then the converse holds.

Definition 2.3. Let G be a graph. An edge \(xy \in G\) is said to be exposed, if xy is contained in a unique maximal clique and xy is not a facet edge. We will denote the edge-induced subgraph of exposed edges of G by \(\partial G\).

Definition 2.4. Suppose G, H are graphs with the same vertex set V. We say that H is obtained from G through an edge erasure, if G contains an exposed edge e such that H = G - e.

The topological nature of an erasure, which can be described in terms of a strong deformation retraction, will be discussed in Section 4. We now provide a useful characterization of exposed edges.

Lemma 2.2. An edge \(vw \in \partial G\) if and only if \(N_G(v) \cap N_G(w)\) is a nonempty clique in G.

Proof. We remark that for any two vertices \(v, w \in G\), the intersection \(N_G(v) \cap N_G(w)\) is just the union of all maximal cliques which contain both v and w, minus \(\{v, w\}\). The result follows immediately from this observation and the definitions.

The previous lemma highlights that our notion of an exposed edge is weaker than that of a simplicial edge [6], where the intersection is replaced by the union of the neighborhoods. Indeed, it follows from the lemma that an edge vw is exposed if and only if w is a non-isolated simplicial vertex of \(G[N_G(v)]\), and vice versa.

Theorem 2.2. A graph H can be obtained from a complete graph through a sequence of erasures of exposed edges if and only if H is a connected chordal graph. Throughout the erasure process each graph in the sequence remains a connected chordal graph.

Proof. First, we can see that erasures from connected chordal graphs produce connected chordal graphs as follows. Suppose H = G - xy, with G a connected chordal graph and \(xy \in \partial G\). If C is an induced cycle in H such that \(\{x,y\} \nsubseteq C\) (i.e., possibly containing x or y, but not both), then C is also an induced cycle of G and so of length G. Otherwise, suppose \(\{x,y\} \subset C\) and |C| > 3. Note that if |C| > 4, then the induced subgraph G' = C + xy of G has an induced cycle of length greater than G, a contradiction. This leaves us with the case where \(G = xv_1yv_2x\) for some G, we must have G0, otherwise G1 would lie in two distinct maximal cliques and G2 would not be exposed. However, G3 (hence in G4) means that G4 would not be an induced cycle in G4, a contradiction. As for connectedness, it is easy to see that an erasure does not disconnect a connected graph since by definition a bridge is not an exposed edge.

Conversely, it suffices to show that for any non-complete connected chordal graph G, we can add an edge e such that \(e \in \partial(G+e)\) with G+e chordal. (Merely ensuring \(e \in \partial(G+e)\) does not guarantee that G+e is chordal.) Given such a G, suppose \(v_1,\ldots,v_k\) is a perfect elimination ordering for G. Let \(1 \leq \ell \leq k\) be the smallest index such that \(G_i\) is complete for \(i > \ell\). Then there is some \(j > \ell\) with \(v_\ell v_j \notin G\), because \(G_\ell\) is not complete, but \(G_{\ell+1}\) is.

Let us show that \(e := v_{\ell}v_j\) is the edge we are looking for. Setting G' = G + e, we claim that \(v_1, \ldots, v_k\) is also a perfect elimination ordering for G'. This will demonstrate that G' is chordal, by Theorem 2.1.

For \(i < \ell\), the neighbors of \(v_i\) in G' are just the same neighbors of \(v_i\) in G, and \(N_{G_i}[v_i]\) is a clique since \(v_i\) is simplicial in \(G_i\). In particular, \(\{v_j, v_\ell\} \nsubseteq N_G(v_i)\) since \(e \notin G\). Thus \(v_i\) is also

simplicial in \(G_i'\). On the other hand, for \(i > \ell\), \(G_i\) (and hence \(G_i'\)) is complete and so every vertex is simplicial. We still need to check that \(v_\ell\) is simplicial in \(G_\ell'\). This follows from the fact that \(v_j v_n \in G_\ell'\) for all \(n > \ell\) since \(G_{\ell+1}'\) is complete.

It remains to show that \(e \in \partial G'\). It is convenient to use the characterization of exposed edges given in Lemma 2.2. Notice again that for \(i < \ell\), we must have that \(\{v_j, v_\ell\} \nsubseteq N_{G'}(v_i)\), since as noted above, \(\{v_i, v_\ell\} \nsubseteq N_{G}(v_i)\). Hence

\[N_{G'}(v_i) \cap N_{G'}(v_\ell) = N_{G'_{\ell}}(v_\ell) \setminus \{v_i\},\]

which is a clique, as shown above, because \(v_{\ell}\) is simplicial in \(G'_{\ell}\).

It is natural to ask whether one could retain this result while replacing the class of exposed edges with a different one. This is easily answered by noticing that the removal of a non-exposed edge either disconnects the graph (in the case of a facet edge) or results in an induced 4-cycle.

Theorem 2.2 is similar in spirit to the result of Spinrad and Sritharan [14] showing that weakly chordal graphs can be recognized by the possibility of successively adding edges through the two-pair construction to arrive at a complete graph.

The following observations can be derived directly from the definitions and will be useful below:

Lemma 2.3. Let G be a graph. If \(S \subset E\) is a set of facet edges, then \(\partial G = \partial (G - S)\). If v is a simplicial vertex with \(\deg_G(v) > 1\), then every edge e incident with v is exposed.

Proposition 2.1. Any connected chordal graph G can be reduced through a sequence of erasures to a tree.

Proof. By Theorem 2.2, it suffices to verify that if G is not a tree, then G contains an exposed edge. Let G' be the subgraph of G obtained by removing all facet edges and let \(G'_0\) be a connected component of G' which is not a single isolated vertex. By Theorem 2.1 and Lemma 2.3, \(G'_0\) has exposed edges, and they are also exposed in G.

Lemma 2.4. Let G be a chordal graph and v a vertex in G that is in a maximal clique of size at least three. Then v is incident with at least two exposed edges.

Proof. Since v is in a maximal clique of size at least three, the induced subgraph \(N_G(v)\) is chordal and not edgeless. Thus there is some connected component of \(N_G(v)\) containing an edge, and so we can use Theorem 2.1 to find two simplicial vertices \(v_1, v_2\) in \(N_G(v)\) in that component. But this implies that \(N_G(v) \cap N_G(v_i)\) is a (non-empty) clique for i = 1, 2, and so \(vv_1\) and \(vv_2\) are exposed edges in G. Note that an isolated vertex u in \(N_G(v)\) would correspond to a facet edge uv in G. \(\square\)

Theorem 2.3. If G is a chordal graph, then every connected component of \(\partial G\) is 2-edge connected.

Proof. It is simple to check that the theorem holds when G is either complete or has no more than four vertices. Now suppose that G is a counterexample with a minimal number of vertices (so \(|G| \ge 5\)).

First, we claim that G has no facet edges. By Lemma 2.1, it suffices to verify that G is bridgeless. Suppose e were a bridge (and hence not exposed in G). Applying Lemma 2.3 with S = {e}, we have that ∂G = ∂(G − e). Now, the connected components of G − e each have fewer vertices than G, implying that all exposed edges in G − e occur in cycles. It follows that G could not have been a counter-example—a contradiction.

Since G is chordal, Theorem 2.1 allows us to find non-adjacent simplicial vertices u, v ∈ G. Then G − u has fewer vertices and so every exposed edge of G − u is contained in a cycle of exposed edges in G − u. Notice that for vertices x, y ∈ G − u, we have that

\[N_{G-u}(x) \cap N_{G-u}(y) = [N_G(x) \cap N_G(y)] \setminus \{u\}.\]

and so using Lemma 2.2 we see that if {x, y} * NG[u], then xy is exposed in G − u if and only if xy is exposed in G. Thus in this case, if xy is exposed in G we can find a cycle C = xyv¹ · · · vkx ⊂ ∂(G − u). If none of the edges in C are in NG(u), then C ⊂ ∂G. However, if some edges of C are contained in NG(u), then let i be the smallest index with vivi+1 in NG(u). Similarly, let j be the largest index with vj−1v^j in NG(u). Notice that j > i, but we could have j = i + 1 if there is a single edge of C in NG(u). (In order to make the notation consistent, we are treating v⁰ as y and vk+1 as x.) Since G has no facet edges, we may apply Lemma 2.3 to see that the cycle C ⁰ = xyv¹ · · · vi−1viuvjvj+1 . . . vkx is a cycle of exposed edges in G containing xy.

The remaining case to be considered is when {x, y} ⊂ NG[u]. Here {x, y} * NG(v), since xy ∈ ∂G and u and v are not adjacent. Hence, by the same reasoning as before, we can find a cycle of exposed edges in G containing xy by modifying a cycle of exposed edges in G − v containing xy.

3. Weighted chordal graphs and w-erasures

We turn now to an application of these results in the setting of edge-weighted finite graphs, and show a connection with single-linkage clustering through minimum spanning trees.

Definition 3.1. Let (G, w) be an edge-weighted graph, with w: E → R^≥0 , and let H be a subgraph with the induced weight. We say that H is obtained from G through a w-erasure, if H = G − e where e ∈ ∂G with w(e) ≥ w(e 0 ) for any exposed edge e ⁰ of G.

Observe that given any sequence G0, G1, . . . , G^m of graphs obtained through erasures of exposed edges e0, e1, . . . , em−1, we can define a weighting w of G⁰ such that G0, G1, . . . , G^m is also a sequence of w-erasures. Also, recall that a minimum spanning tree for a connected weighted graph G is a spanning tree which minimizes the sum of the weights over the edges of the tree.

Theorem 3.1. Let (G, w) be a weighted, connected chordal graph. If G⁰ is obtained from G through a w-erasure, then G⁰ contains a minimum spanning tree of (G, w).

Proof. Let xy ∈ ∂G and G⁰ = G−xy be obtained by a w-erasure. First, recall that G⁰ is connected since any bridge in G is not exposed and hence not removed in a w-erasure. It is also clear that the theorem holds whenever |V (G)| ≤ 3.

Figure 2. Example of a heaviest edge that is not exposed: the "`¹ square" drawn on the left is a weighted K⁴ with two edges of weight 2, both of them exposed (initially all edges are). Performing a single w-erasure (bottom, yellow dashed edges) results in one diameter becoming unexposed, with all the remaining edges being shorter. Proceeding with Kruskal's original algorithm (top, red edges) results in a four cycle before a minimum spanning tree is obtained, while w-erasures maintain chordality throughout.

Let T be a minimum spanning tree of (G, w). The case of concern is when xy ∈ T. Then let Tx, T^y denote the connected components of x and y, respectively, in T − xy. Let F denote the set of all edges uv ∈ G with u ∈ T^x and v ∈ Ty, excluding the edge xy. Since G⁰ is connected, F intersects G⁰ . For any uv ∈ F, the graph T 0 := T − xy + uv is a spanning tree of G, implying wuv ≥ wxy, by minimality of T.

On the other hand, if uv ∈ ∂G, then wuv ≤ wxy and so any exposed edge in F has equal weight with xy. Now we can appeal to Theorem 2.3 to see that xy is contained in a cycle of exposed edges of G which necessarily intersects F, say at uv. Thus T ⁰ = T − xy + uv is another minimum spanning tree contained of (G, w) in G⁰ .

In his seminal paper on minimum spanning trees [13], Kruskal proposed two algorithms for computing such a tree. The second of which proceeds as follows: starting with the complete graph G⁰ = Kⁿ endowed with the weight w, for each i ≥ 0 remove from Gⁱ a heaviest edge (that is, one whose w-value is maximal) among those not separating the current graph to obtain Gi+1. The process terminates after stage t = n−1 2 with Gt+1 a tree. Using the cut property of minimum spanning trees, it is easy to argue that every minimum spanning tree of (Kn, w) may be obtained in this way. The preceding theorem then allows us to show that, surprisingly, when restricting this algorithm to only exposed edges, we are nonetheless able to recover all minimum spanning trees. In so doing, we have replaced a global eligibility criterion, namely checking non-separation for a heaviest edge, with a local condition: checking whether a heaviest edge satisfies Lemma 2.2. Some differences between the two algorithms are illustrated in Figure 2.

Corollary 3.1. Consider a weighted complete graph (Kn, w), for example, the weighted graph associated with a finite metric space. Then a maximal sequence of w-erasures produces a minimum

spanning tree for (Kn, w). Any minimum spanning tree for w can be obtained in this way.

Proof. By induction, the first statement is a direct consequence of Proposition 2.1 and Theorem 3.1. For the second, let us start with a given minimal spanning tree T for w, and a sequence G0, . . . , G^k of graphs obtained by erasure, with G⁰ = Kⁿ and Gⁱ containing T for each 0 ≤ i ≤ k. If G^k 6= T, then for any exposed edge xy in T of maximal weight (among the exposed edges of Gk), the same reasoning as in the proof of Theorem 3.1 (and using the same notation), shows that there must be another exposed edge uv in G^k with equal weight as xy and u ∈ Tx, v ∈ T^y (in particular, uv /∈ T). Thus we can extend the sequence by setting Gk+1 = G^k − uv.

4. Connections to the topological viewpoint

Topologically, we can view the characterization of chordality given in Theorem 2.1 in terms of perfect elimination orderings as providing the basis for realizing chordal graphs as the 1 dimensional skeleta of simplicial flag complexes assembled through successive "coning-off' of existing simplices; or (by reversing the perspective) of simplicial flag complexes which admit an exceedingly tame kind of strong-deformation retraction to a vertex through a sequence of "vertexcollapses." Put in the language of simple homotopy theory (see, e.g. [12], Definition 6.13 and the ensuing discussion), erasing a simplicial vertex w of a chordal graph G is realized in the polyhedron |K| of the subtended complex K as the straight-line homotopy from the identity mapping of |K| to the (realization of the) simplicial map K → sd(K). This homotopy fixes all vertices of K − w and maps w to the barycenter of its opposing face in K, which is the face subtended by the collection of the neighbors of w in G, see Figure 3 (left).

Figure 3. Collapsing an 'exposed' vertex w in a 3-facet (left); an exposed edge uv in a 2-facet (center); and an exposed edge in a 3-facet (right).

Using the same language, the erasure process described in this paper can be understood as another restricted type of strong deformation retraction characterized, at the level of one-dimensional skeleta, by the removal of exposed edges. Indeed, at the level of the complexes, it quickly becomes evident that erasing an arbitrary edge of Gⁱ to obtain Gi+1 (as required by Kruskal's algorithm) does not guarantee a strong deformation retraction of Kⁱ = K^Gi onto Ki+1, unless the edge being removed is exposed. Here Kⁱ is the flag complex with 1-skeleton Gⁱ and an exposed edge is one that is properly contained in a unique maximal simplex of Kⁱ . Then it is possible to eliminate the edge by "pressing in" in the form of an edge-collapse, see Definition 6.13 in [12] and Figure 3 (center,right). Homotopy equivalences of this kind have been studied by combinatorial algebraic topologists since the introduction of the notions of collapsibility and simple homotopy types by Whitehead [15, 16] (also see [12], Chapter 6, for an overview and more modern treatment). Our results, then, provide an understanding of chordal graphs as 1-skeleta of connected flag complexes

arising as strong deformation retractions of a simplex, providing an interpretation of chordality from the standpoint of extendibility.

An alternative view, from a purely algebraic perspective, ties edge-erasures to chordality via Froberg's theorem [8] on linear resolution of edge ideals in Stanley–Reisner rings. Simplicial ¨ collapses were applied in an alternative proof of Froberg's theorem in [5], strengthening the topo- ¨ logical connection.

We close by briefly noting that this approach could be generalized by considering simplicial complexes other than the simplex as starting points, or ambient complexes, for the erasure process. For example, an interesting replacement would be the standard triangulation of the n-cube induced by its isomorphism with the Hasse diagram of the inclusion order in a power set. The corresponding question, then, is to identify which families of complexes/graphs might be characterized as emerging from some ambient complex S by excavating them out of S via repeated application of a restricted family of collapses, subject to a suitable stopping condition.

Acknowledgement

The authors gratefully acknowledge the support of Air Force Office of Science Research under the LRIR 15RYCOR153, MURI FA9550-10-1-0567 and FA9550-11-10223 grants, respectively. We especially want to thank Anton Dochtermann for introducing us to the algebraic perspective via Stanley–Reisner rings.

References

• [1] G. Carlsson, Topology and data. Bull. Amer. Math. Soc., 46(2):255–308, 2009.
• [2] J. Culbertson, D.P. Guralnik, and P.F. Stiller, Functorial hierarchical clustering with overlaps. Discrete Appl. Math., 236:108–123, 2018.
• [3] P. De Caria. A joint study of chordal and dually chordal graphs. PhD thesis, Universidad Nacional de La Plata, 2012.
• [4] G.A. Dirac, On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg ¨ , 25(1):71–76, 1961.
• [5] A. Dochtermann and A. Engstrom, Algebraic properties of edge ideals via combinatorial ¨ topology, Electron. J. Combin., 9, 2009.
• [6] 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.
• [7] H.T. Faal. Clique roots of K4-free chordal graphs, Electron. J. Graph Theory Appl., 7(1):105– 111, 2019.
• [8] R. Froberg, On stanley-reisner rings, ¨ Banach Center Publications, 26(2):57–70, 1990.

• [9] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15(3):835–855, 1965.
• [10] 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.
• [11] H. Hajiabolhassan and M.L. Mehrabadi. On clique polynomials, Australas. J. Combin., 18:313–316, 1998.
• [12] D. Kozlov. Combinatorial Algebraic Topology, vol. 21, Springer Science & Business Media, 2007.
• [13] 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.
• [14] J. Spinrad and R. Sritharan, Algorithms for weakly triangulated graphs, Discrete Appl. Math., 59(2):181–191, 1995.
• [15] J.H.C. Whitehead, Simplicial spaces, nuclei and m-groups, Proc. Lond. Math. Soc., 2(1):243– 327, 1939.
• [16] J.H.C. Whitehead, Simple homotopy types, Amer. J. Math., 72(1):1–57, 1950.
• [17] 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.