Enumerating Threshold Graphs and Some Related Graph Classes

David Galvin, Greyson Wesley, and Bailee Zacovic Department of Mathematics University of Notre Dame Notre Dame, IN 46556 USA

                    dgalvin1@nd.edu
                    gwesley@nd.edu
                    bzacovic@nd.edu

Abstract

We give combinatorial proofs of some enumeration formulas involving labelled threshold, quasi-threshold, loop-threshold and quasi-loop-threshold graphs. In each case we count by number of vertices and number of components. For threshold graphs, we also count by number of dominating vertices, and for loop-threshold graphs we count by number of looped dominating vertices.

We also obtain an analog of the Frobenius formula (connecting Eulerian numbers and Stirling numbers of the second kind) in the context of labelled threshold graphs.

1 Introduction and summary of results

A threshold graph is a graph G for which there exist a real number t (the threshold) and an assignment a : V (G) → ℝ of real numbers to the vertices of G with the property that uv is an edge of G if and only if a(u) + a(v) > t. Equivalently, there exist s ∈ ℝ and b : V (G) → ℝ such that I ⊆ V (G) is an independent set (a set spanning no edges) if and only if ∑_{v∈I} b(v) ≤ s.

Threshold graphs were introduced by Chvátal and Hammer [5] in relation to a set packing problem, and were later independently discovered by various other authors in mathematics, operations research, computer science and psychology. The wide applicability of threshold graphs is due in part to the fact that they admit many alternate characterizations. Indeed, the monograph on threshold graphs by Mahadev and Peled begins by establishing eight distinct characterizations [12, Theorem 1.2.4] (and also gives a good history of their appearance in various fields).

The most germane characterization for the purposes of this note is that the family of threshold graphs is the smallest (by containment) family of (simple, finite) graphs that contains K_{1}, and is closed under adding isolated vertices and adding dominating vertices (vertices adjacent to all other vertices in the graph).

Let t_{n} denote the number of labelled threshold graphs on n vertices (almost always in this note, we will implicitly take the label set to be [n] := {1, …, n}). The beginning of the sequence (t_{n})_{n≥1} is shown in Table 1, and appears in the On-Line Encyclopedia of Integer Sequences (OEIS) [14], as entry \underline{A005840}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ t_{n} & 1 & 2 & 8 & 46 & 332 & 2874 \end{matrix}

Table 1: The count of labelled threshold graphs on vertex set [n].

An ascent in a permutation π = π_{1} ⋯ π_{n} of [n] (given here in one-line notation, as all permutations in this note will be) is an index i ∈ [n−1] with π_{i} < π_{i+1}. The Eulerian number \left⟨{n \atop k}\right⟩ counts the number of permutations of [n] with k ascents (OEIS \underline{A008292}; but note that that entry uses an offset indexing, counting permutations with k − 1 ascents). Beissinger and Peled [2] implicitly observed, via a generating function argument, the formula

t_{n} = ∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩2^{k},  (1)

valid for n ≥ 2. Spiro [15] recently gave a combinatorial proof of (1). In this note, we give combinatorial proofs of other enumeration formulas for threshold graphs, and for some related graph families—quasi-threshold graphs, loop-threshold graphs, and quasi-loop-threshold graphs.

In Sections 1.1 (threshold graphs), 1.2 (quasi-threshold graphs), 1.3 (loop-threshold graphs) and 1.4 (quasi-loop-threshold graphs) we present and discuss our results, and then we give the proofs in Sections 2, 3, 4 and 5.

1.1 Labelled threshold graph results

We begin in Section 2.1 by recalling Spiro’s combinatorial proof of (1), as it introduces ideas and notation that will be useful throughout the note.

Next we present combinatorial proofs of two other formulas for t_{n} that are presented at OEIS \underline{A005840}: for n ≥ 1, and taking t_{0} = 1,

t_{n} = 1 − n + ∑_{k=0}^{n−1} \binom{n}{k}t_{k}  (2)

(Section 2.2), and for n ≥ 1, and taking t_{0} = t_{1} = 1,

t_{n+1} = n(t_{n} − t_{n−1}) + ∑_{k=0}^{n} \binom{n}{k}t_{k}t_{n−k}.  (3)

(Section 2.3).

In Section 2.4, we consider the enumeration of labelled threshold graphs by number of components. This work has already been carried out, using generating functions, by Beissinger and Peled [2] (and in fact they added another parameter, number of distinct vertex degrees). Here, we take a fully combinatorial approach. For n, k ≥ 1, let t-comp_{n,k} denote the number of labelled threshold graphs on vertex set [n] with k components. We establish that

(i) t-comp_{1,1} = 1,

(ii) for n ≥ 2, t-comp_{n,1} = ∑_{k=1}^{n−1}(n − k)\left⟨{n−1 \atop k−1}\right⟩2^{k−1} (= \frac{t_{n}}{2} ),

(iii) for n ≥ 3 and 2 ≤ k ≤ n − 1, t-comp_{n,k} = \binom{n}{k−1} t-comp_{n−k+1,1} and

(iv) for n ≥ 2, t-comp_{n,n} = 1.

(These all follow in a straightforward way from (1).)

The triangle (t-comp_{n,k} : n ≥ 1, 1 ≤ k ≤ n) is shown in Table 2, and is OEIS \underline{A348436}. The first column of the triangle is the sequence enumerating connected labelled threshold graphs on n vertices (n ≥ 1), and is OEIS \underline{A317057}. (A different sequence, OEIS \underline{A053525}, is listed as enumerating connected labelled threshold graphs on n vertices. This sequence is identical to OEIS \underline{A317057} for n ≥ 2, but at n = 1 takes the value 0 rather than the correct value of 1. Also, at OEIS \underline{A005840} there is an incorrect conjecture concerning the number of connected labelled threshold graphs.)

The Stirling number of the second kind \left\{{n \atop k}\right\} (OEIS \underline{A008277}) counts partitions of a set of size n into k non-empty blocks (when we say “partition” from here on, we always mean “partition into non-empty blocks”). There is an identity linking Eulerian numbers and Stirling numbers of the second kind (due originally to Frobenius [9], and discussed in [12, Chapter 17.2]): for n ≥ 1,

∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩x^{k} = ∑_{ℓ=1}^{n} ℓ!\left\{{n \atop ℓ}\right\}(x − 1)^{n−ℓ}.  (4)

t-comp_{n,k} k = 1 2 3 4 5 6
n = 1  1
2  1 1
3  4 3 1
4  23 16 6 1
5 166 115 40 10 1
6 1437 996 345 80 15 1

Table 2: The count of labelled threshold graphs on vertex set [n] with k components.

We will see in Section 1.3 that this identity is directly relevant to the enumeration of loopthreshold graphs. In Section 2.5, we prove an analog of (4) in the setting of labelled threshold graphs. Let op2_{n,ℓ} denote the number of ordered partitions of [n] (also known as weak orders) into ℓ blocks, in which the first (i.e., smallest) block has size at least 2.

Theorem 1. For n ≥ 2,

∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩x^{k−1} = ∑_{ℓ=1}^{n−1} op2_{n,ℓ}(x − 1)^{n−ℓ−1}.  (5)

Note the parallel between (4) and (5): the ℓ!\left\{{n \atop ℓ}\right\} on the right-hand side of (4) is the number of ordered partitions of [n] into ℓ blocks, with no restriction on the size of the first block. Note also that setting y = x + 1 in (5) and comparing coefficients of y^{n−ℓ−1} gives an exact formula for op2_{n,ℓ}, namely

op2_{n,ℓ} = ∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩\binom{k − 1}{n − ℓ − 1}.  (6)

The triangle (op2_{n,ℓ} : n ≥ 1, 1 ≤ ℓ ≤ n) is shown in Table 3, and is OEIS \underline{A348576}. The row sums of this triangle, 0, 1, 4, 23, 166, 1437, …, enumerate ordered partitions of a set of size n (n ≥ 1) into (any number of) non-empty blocks, in which the first block has size at least 2. This is OEIS \underline{A053525}.

As discussed earlier, labelled threshold graphs can be constructed iteratively, starting from a single vertex, by successively adding isolated or dominating vertices. Although there is not a unique such iterative construction, the number of dominating vertices added in any such construction of G is independent of the choice of construction. Let d(G) denote this number (note that we do not consider the initial vertex to be dominating). In Section 2.6 we obtain an explicit expression for d_{n,k}, the number of labelled threshold graphs G on vertex set [n] with d(G) = k: d_{n,0} = 1 for all n ≥ 1, d_{2,1} = 1, d_{2,k} = 0 for all k ≥ 2, and for n ≥ 3, k ≥ 1,

d_{n,k} = \begin{matrix}∑_{ℓ≥1} \binom{n}{k+1} op2_{k+1,ℓ} [(ℓ − 1)!\left\{{n−k−1 \atop ℓ−1}\right\} + ℓ!\left\{{n−k−1 \atop ℓ}\right\}] + \\ ∑_{ℓ≥1} \binom{n}{k}ℓ!\left\{{k \atop ℓ}\right\} [op2_{n−k,ℓ+1} + op2_{n−k,ℓ}] . \end{matrix}  (7)

op2_{n,ℓ} ℓ = 1 2 3 4 5 6
n = 1  0
2  1 0
3  1 3 0
4  1 10 12 0
5  1 25 80 60 0
6  1 56 360 660 360 0

Table 3: The count of ordered partitions of [n] into ℓ non-empty blocks, in which the first block has size at least 2.

(Note that (6) gives a way of calculating the op2_{·,·} terms, in terms of more fundamental counting sequences.) The triangle (d_{n,k} : n ≥ 1, 0 ≤ k ≤ n − 1) is shown in Table 4, and is OEIS \underline{A350060}.

d_{n,k} k = 0 1  2  3 4 5
n = 1  1
2  1 1
3  1 6  1
4  1 22 22  1
5  1 65 200 65 1
6  1 171 1265 1265 171 1

Table 4: The count of labelled threshold graphs on vertex set [n] in which k dominating vertices are added in an iterative construction.

1.2 Labelled quasi-threshold graph results

The family of quasi-threshold graphs is the smallest family of graphs that contains K_{1}, and is closed under adding dominating vertices and taking disjoint unions; it properly contains the family of threshold graphs. Like threshold graphs, quasi-threshold graphs have many alternate characterizations. One such is that they are precisely the comparability graphs of trees; it was in this context that they were first studied, by Wolk [17]. Another characterization is that quasi-threshold graphs are precisely those with the property that in each induced subgraph, the size of the largest independent set equals the number of maximal cliques. As observed by Golumbic [10], it is trivial to show that such graphs are perfect, and so quasi-threshold graphs are also called trivially perfect graphs.

Let qt_{n} denote the number of labelled quasi-threshold graphs on n vertices. As was possibly first explicitly observed by Guruswami [11], the sequence (qt_{n})_{n≥1} begins as is shown in Table 5, and is OEIS \underline{A058864}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ qt_{n} & 1 & 2 & 8 & 49 & 402 & 4144 \end{matrix}

Table 5: The count of labelled quasi-threshold graphs on vertex set [n].

In Section 3.1, we give a combinatorial proof of the following formula that appears at OEIS \underline{A058864}:

qt_{n} = ∑_{k=0}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}(k + 1)^{k−1}.  (8)

The proof uses the method of sign-changing involutions (see, for example, [4]). Since this method will be used again in the sequel (to prove (13)), we digress here to give a brief description of it.

Suppose that we have a family (F_{n})_{n≥0} of sets, and that we want to verify the identity |F_{n}| = ∑_{k=0}^{n}(−1)^{n−k}g(n, k), where the g(n, k) are non-negative integers for all n, k ≥ 0. We proceed as follows.

Step 1 Find a set G_{n} whose size is ∑_{k=0}^{n} g(n, k), that naturally partitions as G_{n} = ∪_{k=0}^{n}G_{n,k}, where |G_{n,k}| = g(n, k).

Step 2 Find an involution ι : G_{n} → G_{n} (a bijection satisfying ι ∘ ι = identity) with the following properties:

• all the fixed points of ι lie in G_{n}^{even} := ∪_{k: n−k even} G_{n,k}, and

• all the orbits of size 2 of ι intersect both G_{n}^{even} and G_{n} \ G_{n}^{even}.

Note that these conditions together imply that G_{n}^{fixed}, the set of fixed points of ι, satisfies

|G_{n}^{fixed}| = ∑_{k=0}^{n}(−1)^{n−k}g(n, k).

Step 3 Find a bijection from G_{n}^{fixed} to F_{n}.

Guruswami [11] used generating functions to obtain the following explicit formula for qt-conn_{n}, the number of connected labelled quasi-threshold graphs on n vertices:

qt-conn_{n} = ∑_{k=1}^{n}(−1)^{n+k}\left\{{n \atop k}\right\}k^{k−1}.  (9)

As described in Section 3.2, the proof of (8) is easily modified to give a combinatorial proof of (9). More generally, we give a simple combinatorial proof of the following:

Claim 2. The number qt-comp_{n,ℓ} of labelled quasi-threshold graphs on n vertices with ℓ components is

qt-comp_{n,ℓ} = ∑_{k=1}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}ℓ\binom{k}{ℓ}k^{k−ℓ−1}.  (10)

The triangle (qt-comp_{n,ℓ} : n ≥ 1, 1 ≤ ℓ ≤ n) is shown in Table 6, and is OEIS \underline{A350528}. The first column (enumerating connected labelled quasi threshold graphs, by number of vertices) is OEIS \underline{A058863}.

qt-comp_{n,ℓ} ℓ = 1  2 3 4 5 6
n = 1  1
2  1  1
3  4  3 1
4  23 19 6 1
5 181 155 55 10 1
6 1812 1591 600 125 15 1

Table 6: The count of labelled quasi-threshold graphs on vertex set [n] with ℓ components.

1.3 Labelled loop-threshold graph results

All graphs that have been considered so far have been simple. For the last two families that we consider, loops are allowed, but not multiple edges. The two families are direct analogs of threshold and quasi-threshold graphs, in the world of looped graphs.

The family of loop-threshold graphs is the smallest family of graphs (finite, potentially with loops, but without multiple edges) that contains K_{1} and K_{1}^{loop} (a loop on a single vertex), and is closed under adding isolated vertices and adding looped dominating vertices (looped vertices also adjacent to all other vertices in the graph).

Both loop-threshold and quasi-loop-threshold graphs (see Section 1.4) were introduced by Cutler and Radcliffe [8] as part of their study of extremal enumerative questions for graph homomorphisms. These families are natural to consider as target graphs in this context; for example, independent sets in graphs can be encoded as homomorphisms to the loop-threshold graph that is formed by adding a looped dominating vertex to an isolated vertex. Cutler and Radcliffe prove that for each n and m and loop-threshold graph H, among the m-edge n-vertex graphs that admit the most homomorphisms to H there is at least one threshold graph; and if H is quasi-loop-threshold, then at least one maximizer is quasi-threshold.

Cutler and Radcliffe also observe that loop-threshold and quasi-loop-threshold graphs have characterizations in terms of vertex neighborhoods that are exact analogs of well-known characterizations of threshold and quasi-threshold graphs. Specifically, a graph is threshold iff for each pair x, y ∈ V (G) we have either N(x)\{y} ⊆ N(y)\{x} or N(y)\{x} ⊆ N(x)\{y}, where N(x) is the set of vertices adjacent to x (see [6]), while it is loop-threshold iff for each pair x, y ∈ V (G) we have either N(x) ⊆ N(y) or N(y) ⊆ N(x) (note that N(x) includes x if there is a loop at x) (see [8]). On the quasi- side, a graph is quasi-threshold iff there is a containment relation between N(x) \ {y} and N(y) \ {x} for each adjacent pair x, y ∈ V (G) (see [7]), while it is loop-quasi-threshold iff there is a containment relation between N(x) and N(y) for each adjacent pair x, y ∈ V (G) (see [8]).

Unlike for threshold graphs, little previous work has been done on enumeration of labelled loop-threshold graphs. Let lt_{n} denote the number of labelled loop-threshold graphs on n vertices. The sequence (lt_{n})_{n≥1} is shown in Table 7 (the first few terms can be found by inspection; later terms follow from our results.)

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ lt_{n} & 2 & 6 & 26 & 150 & 1082 & 9366 \end{matrix}

Table 7: The count of labelled loop-threshold graphs on vertex set [n].

In Section 4.1 we show that this sequence is OEIS \underline{A000629}, whose nth term counts the number of cyclically ordered partitions of n + 1 objects. We do this by presenting a combinatorial proof of the formula

lt_{n} = 2 ∑_{k=1}^{n} k!\left\{{n \atop k}\right\},  (11)

which is given at OEIS \underline{A000629}. Note that the right-hand side of (11) does indeed enumerate cyclically ordered partitions of n + 1 objects. Indeed, ∑_{k=1}^{n} k!\left\{{n \atop k}\right\} enumerates ordered partitions of [n], and there is a 1-to-2 correspondence between ordered partitions of [n], and cyclically ordered partitions of [n + 1]: close the ordered partition into a cyclically ordered partition, and either let n + 1 be in a block on its own between the last and first blocks of the ordered partition, or include n + 1 in the first block.

Setting x = 2 in the Frobenius formula (4), we obtain from (11) the following analog of (1) for loop-threshold graphs:

lt_{n} = ∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩2^{k+1}.  (12)

The right-hand side above appears at OEIS \underline{A000629}. (Actually, (12) appears at OEIS \underline{A000629} with 2^{k+1} replaced by 2^{k}; this discrepancy is explained by the fact that at OEIS \underline{A000629}, the Eulerian number \left⟨{n \atop k}\right⟩ is counting permutations of [n] with k − 1 ascents rather than with k.) In Section 4.2 we give a short direct combinatorial proof of (12) (as opposed to one passing through the Frobenius formula). It is similar in spirit to Spiro’s proof of (1).

Our proof of (12) is very similar to a proof of a related identity involving Eulerian numbers and Stirling numbers given by Bona [3, Section 1.1.3], and generalizes easily to a combinatorial proof of the full Frobenius formula, that is different from the semi-combinatorial proof given in [2]. For completeness, we also include this extension in Section 4.2.

Another formula suggested by OEIS \underline{A000629} is the alternating sum

lt_{n} = ∑_{k=0}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}k!2^{k}.  (13)

The right-hand sides of (12) and (13) can be seen to be equal using the Frobenius identity (4) at x = 1/2 (and using the symmetry \left⟨{n \atop ℓ}\right⟩ = \left⟨{n \atop n−1−ℓ}\right⟩ of the Eulerian numbers). In Section 4.3 we use a sign-changing involution to give a direct combinatorial proof of (13).

Next, we consider the enumeration of loop-threshold graphs by number of components. Let lt-comp_{n,k} denote the number of labelled loop-threshold graphs on vertex set [n] with k components. In Section 4.4 we give the easy derivation that, for n, k ≥ 1:

(i) lt-comp_{n,1} = ∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩2^{k} (so lt-comp_{n,1} = \frac{lt_{n}}{2} for n ≥ 2),

(ii) for n ≥ 3 and 2 ≤ k ≤ n − 1, lt-comp_{n,k} = \binom{n}{k−1} lt-comp_{n−k+1,1}, and

(iii) for n ≥ 2, lt-comp_{n,n} = n + 1.

The triangle (lt-comp_{n,k} : n ≥ 1, 1 ≤ k ≤ n) is shown in Table 8, and is OEIS \underline{A350531}. This is very close to OEIS \underline{A154921}—in the triangle shown in Table 8, replace the last nonzero entry (m + 1) of each row with two entries (m, 1) to get OEIS \underline{A154921}. The first column of the triangle, the sequence of connected labelled loop-threshold graphs by number of vertices, is, apart from an anomaly at n = 1, OEIS \underline{A000670}.

lt-comp_{n,k} k = 1  2  3 4 5 6
n = 1  2
2  3  3
3  13  9  4
4  75 52 18 5
5 541 375 130 30 6
6 4683 3246 1125 260 45 7

Table 8: The count of labelled loop-threshold graphs on vertex set [n] with k components.

Just as with threshold graphs, we can associate to any loop-threshold graph G an invariant ld(G), the number of looped dominating vertices added in any iterative construction of G. This takes values between 0 and |V (G)|, the number of vertices of G, and unlike the analogous invariant for threshold graphs, ld(G) can easily be measured without considering the iterative construction—it is the number of looped vertices of G. Notice also that in contrast to the case of threshold graphs, we do not have to make an arbitrary decision regarding the first vertex in the construction.

Let ld_{n,k} denote the number of labelled loop-threshold graphs G on vertex set [n] with ld(G) = k. Notice that ld_{n,0} = 1 for all n ≥ 1. By a very similar argument to the one used to derive (7) (presented in Section 2.6), we can derive that for n ≥ 2, k ≥ 1, we have

ld_{n,k} = \binom{n}{k} ∑_{ℓ≥1} ℓ!\left\{{k \atop ℓ}\right\}h(ℓ, n, k).

where

h(ℓ, n, k) = (ℓ − 1)!\left\{{n − k \atop ℓ − 1}\right\} + 2ℓ!\left\{{n − k \atop ℓ}\right\} + (ℓ + 1)!\left\{{n − k \atop ℓ + 1}\right\}.

(We omit the proof.) The triangle (ld_{n,k} : n ≥ 1, 0 ≤ k ≤ n) is shown in Table 9, and is OEIS \underline{A350745}.

ld_{n,k} k = 0 1  2  3  4 5 6
n = 1  1 1
2  1 4  1
3  1 12 12  1
4  1 32 84 32  1
5  1 80 460 460 80 1
6  1 192 2190 4600 2190 192 1

Table 9: The count of labelled loop-threshold graphs on vertex set [n] with k looped vertices.

1.4 Labelled quasi-loop-threshold graph results

The family of quasi-loop-threshold graphs is the smallest family of graphs (finite, potentially with loops, but without multiple edges) that contains K_{1} and K_{1}^{loop} (a loop on a single vertex), and is closed under taking disjoint unions and adding looped dominating vertices; it properly contains the family of loop-threshold graphs. (See the start of Section 1.3 for a little more on this family). As with loop-threshold graphs, little previous work has been done on enumeration of labelled quasi-loop-threshold graphs.

Let qlt_{n} denote the number of labelled quasi-loop-threshold graphs on n vertices. The sequence (qlt_{n})_{n≥1} is shown in Table 10 (the first few terms can be found by inspection; later terms follow from our results.)

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ qlt_{n} & 2 & 7 & 42 & 376 & 4513 & 68090 \end{matrix}

Table 10: The count of labelled quasi-loop-threshold graphs on vertex set [n].

In Section 5 we show that this sequence is an offset of OEIS \underline{A038052}, whose nth term counts the number of labeled trees whose vertices are labelled with the blocks of a partition of [n]. Specifically, we show that qlt_{n} is the (n + 1)st term of \underline{A038052}. We do this by presenting a combinatorial proof of the formula

qlt_{n} = ∑_{k=1}^{n+1} \left\{{n + 1 \atop k}\right\}k^{k−2}.  (14)

Note that by Cayley’s formula, the right-hand side of (14) (which is given at OEIS \underline{A038052}) is easily seen to enumerate labeled trees whose vertices are labelled with the blocks of a partition of [n + 1].

We conclude our note by considering the enumeration of labelled quasi-loop-threshold graphs by number of components. Here things are not as clean as in the case of quasithreshold graphs. In Section 5 we consider the number qlt-conn_{n} of connected labelled quasi-loop-threshold graphs on n vertices (this turns out to be a useful first step in obtaining (14)), and show that qlt-conn_{1} = 2 and for n ≥ 2

qlt-conn_{n} = ∑_{k=1}^{n} \left\{{n \atop k}\right\}k^{k−1}.  (15)

Except for an anomaly at n = 1, the sequence (qlt-conn_{n})_{n≥1} is OEIS \underline{A048802} (that sequence takes value 2 at n = 1, as opposed to 1; so OEIS \underline{A048802} counts labelled quasi-loop-threshold on n vertices that have at least one looped dominating vertex.)

Let qlt-comp_{n,ℓ} denote the number of labelled quasi-loop-threshold on n vertices with ℓ components. It follows via standard considerations that

qlt-comp_{n,ℓ} = \frac{1}{ℓ!} ∑_{x_{1}+···+x_{ℓ}=n, x_{i}≥1} \binom{n}{x_{1}, …, x_{ℓ}} qlt-conn_{x_{1}} ⋯ qlt-conn_{x_{ℓ}} .  (16)

We also have, via the exponential formula (see e.g. [16]), that

qlt-comp_{n,ℓ} = \frac{n!}{ℓ!}[x^{n}] (∑_{k≥1} \frac{qlt-conn_{k} x^{k}}{k!} )^{ℓ} ,

where [x^{n}]f(x) denotes the coefficient of x^{n} in the power series f(x). The triangle (qlt-comp_{n,k} : n ≥ 1, 1 ≤ k ≤ n) is shown in Table 11, and is OEIS \underline{A350746}.

qlt-comp_{n,ℓ} ℓ = 1  2  3  4 5 6
n = 1  2
2  3  4
3  16  18
4 133 155  72 16
5 1521 1810 910 240 32
6 22184 26797 14145 4180 720 64

Table 11: The count of labelled quasi-loop-threshold on vertex set [n] with k components.

2 Proofs for threshold graph results

2.1 Spiro’s proof of (1)

Our goal here is to establish that for n ≥ 2 the number t_{n} of labelled threshold graphs on [n] satisfies

t_{n} = ∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩2^{k}.  (17)

Threshold graphs can be constructed from K_{1} by iteratively adding isolated or dominating vertices, and so a labelled threshold graph G on vertex set [n], n ≥ 2, can be uniquely encoded by a pair (s, P), where

• s ∈ {+, −} and

• P is an ordered partition of [n] with the first block having size at least 2.

Indeed, if the construction of G from K_{1} begins by assigning a label to K_{1} and then adding some (labelled) dominating vertices, we can take s = + and take as the first block of P the label assigned to K_{1} together with the labels of all the added dominating vertices that are added before the first isolated vertex is added; then take the second block of P to be the labels of all the isolated vertices that are added before the next dominating vertex is added, and so on. If the construction of G from K_{1} begins by assigning a label to K_{1} and then adding some isolated vertices, we can take s = − and then proceed similarly. It is easily seen that each threshold graph has a unique code, and that for each pair (s, P) there is a unique threshold graph that has (s, P) as its code. (See Figure 1.)

So, let O_{n} be the set of all pairs (s, P) with s ∈ {+, −} and with P a partition of [n] with first block having size at least 2, and let P_{n} be the set of triples (s, π, c) where

• s ∈ {+, −},

• π is a permutation of [n] that starts with an ascent, and

2 3 1 4 5 1 3 5 2 4

Figure 1: Two labelled threshold graphs. The one on the left has code (+, 23/14/5), while the one on the right has code (−, 135/24).

• c is an assignment of a color, from a palette of two colors, say red and blue, to each of the ascents of π other than the first ascent.

Claim 3. |O_{n}| = |P_{n}|.

Before proving Claim 3 we complete the combinatorial proof of (1) by observing that the right-hand side of (17) enumerates P_{n}. Indeed, there are (n − k)\left⟨{n−1 \atop k−1}\right⟩ permutations of [n] that have k ascents and that start with an ascent (this is established in [15, Lemma 6], and is also observed by Gessel at OEIS \underline{A008292}). For each such permutation, there are 2^{k−1} ways to 2-color the ascents (other than the first ascent); the extra factor of 2 in the summand on the right-hand side of (17) allows for the selection of s.

A natural operation on ordered partitions comes up in the proof of Claim 3, and will recur throughout other proofs, so we record it as a definition.

Definition 4. For an ordered partition P = P_{1}/ ⋯ /P_{k} with, for each i, P_{i} = {p_{i1}, …, p_{iℓ_{i}}} (p_{i1} < ⋯ < p_{iℓ_{i}}), the flattening of P is the permutation

π_{f}(P) = p_{11} ⋯ p_{1ℓ_{1}} ⋯ p_{k1} ⋯ p_{kℓ_{k}}

of ∪_{i=1}^{k}P_{i}.

For example, for P = 57/321/64 (an ordered partition of [7]), we have π_{f}(P) = 5712346.

Proof (of Claim 3). We describe a bijection from O_{n} to P_{n}. Given a pair (s, P) ∈ O_{n}, set π = π_{f}(P) (see Definition 4). Because the first block of P has size at least 2, π starts with an ascent. Color an ascent (other than this initial one) red if it is not the largest element of its block, and blue otherwise (note that ascents colored blue are necessarily the largest elements in their blocks). The triple (s, π, c) is in P_{n}.

Example 5. The pair (+, 235/17/46/8) ∈ O_{n} maps to the triple

(+, 23517468, c) ∈ P_{n},

where c^{−1}(red) = {3, 1, 4} and c^{−1}(blue) = {6}.

To see that the map described above from O_{n} to P_{n} is a bijection, we now describe how to invert it. Given a triple (s, π, c) ∈ P_{n}, form an ordered partition P of [n] as follows: write π in one-line notation, make a break in π after each ascent colored blue, and after each descent. Let P_{1} (the first block of P) be the set of symbols that occur before the first break, P_{2} (the second block of P) be the set of symbols that occur between the first and second breaks, et cetera. Then the pair (s, P) is in O_{n}, and is easily seen to map to (s, π, c) under the map described in paragraph preceding Example 5.

2.2 Proof of (2)

The goal here is to establish that the number t_{n} of labelled threshold graphs on vertex set [n] satisfies

t_{n} = 1 − n + ∑_{k=0}^{n−1} \binom{n}{k}t_{k}

for n ≥ 1, with t_{0} = 1.

The identity is evident for n = 1, 2, so we consider n ≥ 3, for which the identity is equivalent to

t_{n} = 2 + ∑_{k=2}^{n−1} \binom{n}{k}t_{k}.  (18)

We use that t_{n} = |O_{n}| for n ≥ 2, where O_{n} is the set of pairs (s, P) with s ∈ {+, −} and with P an ordered partition of [n] in which the first block has at least two elements (see Section 2.1). This equality fails for n ≤ 1, which explains the need here (and later) to deal with small n instances of the recurrence by hand rather than via a general bijection.

There is one ordered partition of [n] with only one block, and this partition appears in two elements of O_{n} (one with s = + and one with s = −). This accounts for the 2 on the right-hand side of (18).

For all other ordered partitions, the union of all the blocks but the final one has size ranging from 2 to n − 1; let this size be k (this is the index of summation in the sum on the right-hand side of (18)). The number of pairs (s, P) corresponding to each k is \binom{n}{k} (select the set L of labels that do not appear in the final block) times t_{k} (select a pair (s, P′), where s ∈ {+, −} and P′ is an ordered partition of L in which the first block has at least two elements); note that each (s, P′) gives rise to a unique element of O_{n} by appending [n] \ L as a block at the end of P′. This establishes (18).

2.3 Proof of (3)

The goal here is to establish that the number t_{n} of labelled threshold graphs on vertex set [n] satisfies

t_{n+1} = n(t_{n} − t_{n−1}) + ∑_{k=0}^{n} \binom{n}{k}t_{k}t_{n−k}

for n ≥ 1, with t_{0} = t_{1} = 1. The k = 0 term in the sum is t_{n} and the k = 1 term is nt_{n−1}, so the recurrence can be rewritten as

t_{n+1} = (n + 1)t_{n} + ∑_{k=2}^{n} \binom{n}{k}t_{k}t_{n−k}.  (19)

This identity is easy to verify for n = 1, 2, so from here on we assume n ≥ 3. As in Section 2.2, we use that t_{n} = |O_{n}| for n ≥ 2, where O_{n} is the set of pairs (s, P) with s ∈ {+, −} and with P an ordered partition of [n] in which the first block has at least two elements. To verify (19) we will show that

(a) (n + 1)t_{n} enumerates those pairs in O_{n+1} in which the partition P ends with a block of size 1, and

(b) the summation on the right-hand side of (19) enumerates those pairs in which P ends with a block of size at least 2.

For (a), here is a bijection from pairs (s, P) in O_{n+1} in which the partition P ends with a block of size 1, to triples (a, s′, P′) where a ∈ [n + 1], s′ ∈ {+, −} and P′ is an ordered partition of [n] in which the first block has at least two elements (note that the number of such triples is (n + 1)t_{n}): given (s, P), let a be the number in the final block of P, let s′ = s, and let P′′ be obtained from P by removing the final block. Here P′′ is an ordered partition not of [n] but of a set S of n integers; turn it into P′, an ordered partition of [n] (whose first block still has size at least 2) by replacing the ith largest element of S by i, for i = 1, …, n. (We refer to this final operation, which we will need again later, as compressing S.) This map is easily seen to be invertible.

Example 6. The pair (+, 137/6/25/4) maps to the triple (4, +, 136/5/24).

For (b): to an ordered partition P of a set of integers, associate the permutation π = π_{f}(P) (see Definition 4). For k = 2, …, n−2, { \atop n − 1}, n let O_{n+1}^{k} be the set of pairs in O_{n+1} in which the last block of P has size at least 2, and in which n + 1 appears in position k + 1 in π(P) (hereˆ ·is indicating a missing element in a sequence). For k = n−1, let O_{n+1}^{k} (= O_{n+1}^{n−1}) be the set of pairs in O_{n+1} in which the last block of P has size at least 2, and in which n + 1 appears in position 2 in π(P). We claim that

(i) ∪_{k=2}^{n}O_{n+1}^{k} is exactly the set of pairs in O_{n+1} in which the last block of P has size at least 2, and

(ii) for each k = 2, …, n, |O_{n+1}^{k}| = \binom{n}{k}t_{k}t_{n−k}.

Noting that the union in (i) is clearly a disjoint union, (i) and (ii) together yield (b), and this together with (a) yields (19).

To see (i), note that there are no pairs in O_{n+1} in which the last block of P has size at least 2, and in which n + 1 appears in position 1 in π(P)—the first block of P has at least two elements (by definition of O_{n+1}), and π(P) begins with the smallest element of the first block, which will not be n + 1. Nor are there pairs in O_{n+1} in which the last block of P has size at least 2, and in which n + 1 appears in position n in π(P)—this would put n + 1 in the last block of P, and so by construction of π(P) would put it in position n + 1. So the possible positions for n + 1 are 2 (counted by O_{n+1}^{n−1}) and 3, …, n̂, n + 1 (counted by O_{n+1}^{k}

for k = 2, …, { \atop n − 1}, n).

To see (ii), we first consider O_{n+1}^{k} for k ≠ n − 1, n. To show |O_{n+1}^{k}| = \binom{n}{k}t_{k}t_{n−k} we associate to each (s, P) ∈ O_{n+1}^{k} a quintuple (A, s′, P′, s′′, P′′) where A is a subset of [n] of size k, (s′, P′) ∈ O_{k} and (s′′, P′′) ∈ O_{n−k}, in such a way that all such quintuples are seen once as (s, P) varies over O_{n+1}^{k} (note that the number of such quintuples is \binom{n}{k}t_{k}t_{n−k}). We do this as follows. Given (s, P) ∈ O_{n+1}^{k},

• take A to be the elements that precede n + 1 in π(P); note |A| = k.

• Take s′ = s.

• To obtain P′, take all the blocks of P up to and including the one that includes n + 1. Let this block (i.e., the one containing n + 1) be f(P). Remove n + 1 from f(P) (or, if f(P) is a singleton, remove the entire block). The result is an ordered partition of the set A, whose first block has size at least 2; turn it into P′, an ordered partition of [k] whose first block has size at least 2, by compressing A (see just before Example 6).

• To obtain P′′, take all the blocks of P that occur after f(P), in reverse order (i.e., starting with the final block of P, and ending with the block that comes immediately after f(P)). The result is an ordered partition of a set T of integers of size n − k, whose first block has size at least 2 (since the last block of P has size at least 2); turn this into P′′, an ordered partition of [n − k] whose first block has size at least 2, by compressing T.

• Finally, we describe s′′, whose function is to record whether f(P) (recall, this is the block of P that contains n + 1) is a singleton or not; specifically, take s′′ = + if f(P) = {n + 1} and s′′ = − otherwise.

Example 7. The pair (−, 37/129/6/4/58) ∈ O_{9}^{4} maps to the quintuple

({1, 2, 3, 7}, −, 34/12, −, 24/1/3),

while (−, 37/12/9/6/4/58) maps to the quintuple

({1, 2, 3, 7}, −, 34/12, +, 24/1/3).

Given a quintuple (A, s′, P′, s′′, P′′) with A a subset of [n] of size k, (s′, P′) ∈ O_{k} and (s′′, P′′) ∈ O_{n−k}, we can easily invert the above association to find the unique (s, P) ∈ O_{n}^{k} that gets associated with (A, s′, P′, s′′, P′′); so |O_{n}^{k}| = \binom{n}{k}t_{k}t_{n−k}.

Next we deal with k = n, which is a little simpler than k = 2, …, n − 2. We need to establish |O_{n+1}^{n}| = t_{n} (= |O_{n}|). Given (s, P) ∈ O_{n+1}^{n}, in which (by definition of O_{n+1}^{n}) n + 1 is in the final block of P, simply remove n + 1 to obtain P′, an ordered partition of [n] in which the first block has size at least 2. The correspondence (s, P) → (s, P′) is clearly a bijection from O_{n+1}^{n} to O_{n}.

Finally we turn to the case k = n−1. We aim to show |O_{n+1}^{n−1}| = nt_{n−1}. For (s, P) ∈ O_{n+1}^{n−1}, note that since n + 1 is the second element of π(P) it must be that P begins with a block of size 2 that includes n + 1 and one other number, say a. Associate with (s, P) the triple (a, s, P′) where P′ is obtained from P by removing the first block, then ordering the blocks in reverse order (so P′ starts with a block of size at least 2) and then compressing [n + 1] \ {a}.

Example 8. The pair (+, 49/238/7/156) ∈ O_{9}^{7} maps to (4, +, 145/6/237).

This association is clearly a bijection from O_{n+1}^{n−1} to [n] × O_{n−1}, completing the proof of (19).

2.4 Labelled threshold graphs by number of components

For n, k ≥ 1, recall that we let t-comp_{n,k} be the number of labelled threshold graphs on vertex set [n] with k components. The goal of this section is to explain the (quite straightforward) derivations from (1) of the following formulas:

(i) t-comp_{1,1} = 1,

(ii) for n ≥ 2, t-comp_{n,1} = ∑_{k=1}^{n−1}(n − k)\left⟨{n−1 \atop k−1}\right⟩2^{k−1},

(iii) for n ≥ 3 and 2 ≤ k ≤ n − 1, t-comp_{n,k} = \binom{n}{k−1} t-comp_{n−k+1,1} and

(iv) for n ≥ 2, t-comp_{n,n} = 1.

Evidently the only connected labelled threshold graph on one vertex is connected, and for n ≥ 2 the only connected labelled threshold graph with n components is the edgeless graph, so (i) and (iv) hold.

For n ≥ 2, we claim that half of all labelled threshold graphs on [n] are connected. Indeed, the involution ι on O_{n} given by ι(+, P) = (−, P) and ι(−, P) = (+, P) has orbits that consist of one connected labelled threshold graph on [n] ((+, P) if P has an odd number of blocks—and so the construction of a threshold graph from (+, P) ends by adding dominating vertices—and (−, P) if P has an even number of blocks), and one graph that is not connected. Together with (1), this observation yields (ii). (Note that the involution ι interpreted in terms of threshold graphs corresponds to graph complementation.)

For n ≥ 3 and 2 ≤ k ≤ n − 1, the set of labelled threshold graphs on vertex set [n] with k components is obtained by choosing k − 1 elements from [n], choosing a connected labelled threshold graph on the remaining n − k + 1 elements, and then adding the chosen k − 1 elements as isolated vertices (i.e., as a block added to the end of P); this gives (iii).

2.5 Proof of Theorem 1

The goal here is to establish the following analog of the Frobenius formula (4): for n ≥ 2,

∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩x^{k−1} = ∑_{ℓ=1}^{n−1} op2_{n,ℓ}(x − 1)^{n−ℓ−1},  (20)

where op2_{n,ℓ} is the number of ordered partitions of [n] into ℓ blocks, with the first block having size at least 2.

For positive integers x, the right-hand side of (5) counts ordered partitions of [n] into blocks, in which the first block has size at least 2, and in which all elements are colored with one of x − 1 colors, except for the smallest element in the first block and the largest element in each of the blocks (none of which is given a color).

To each such colored partition, associate a colored permutation as follows. The permutation is obtained from the ordered partition by flattening (see Definition 4). Each element that has been colored retains its color; additionally, the entries in the permutation that correspond to the largest entries in a block, and that are also ascents, are given an xth color.

The process just described yields a bijective correspondence from colored partitions to permutations of [n] that start with an ascent and in which all ascents except the first are given one of x colors. Indeed, given such a colored permutation, we can recover the colored partition it came from by locating the ascents colored x and the (uncolored) descents—these are the largest elements of each of the blocks of the partition—and ignoring the color x.

Since (see Section 2.1) the number of permutations of [n] that start with an ascent and have k ascents is (n − k)\left⟨{n−1 \atop k−1}\right⟩, we have bijectively established (20) for all positive integers x; the identity follows for all x since both sides of (20) are polynomials in x.

2.6 Proof of (7)

Recall that for a labelled threshold graph G, we let d(G) denote the number of dominating vertices added in any iterative construction of G that starts from a single vertex and successively adds dominating or isolated vertices, and we let d_{n,k} be the number of labelled threshold graphs G on vertex set [n] for which d(G) = k. The goal of this section is to establish d_{n,0} = 1 for all n ≥ 1, d_{2,1} = 1, and for n ≥ 3, k ≥ 1,

d_{n,k} = \begin{matrix}∑_{ℓ≥1} \binom{n}{k+1} op2_{k+1,ℓ} [(ℓ − 1)!\left\{{n−k−1 \atop ℓ−1}\right\} + ℓ!\left\{{n−k−1 \atop ℓ}\right\}] + \\ ∑_{ℓ≥1} \binom{n}{k}ℓ!\left\{{k \atop ℓ}\right\} [op2_{n−k,ℓ+1} + op2_{n−k,ℓ}] . \end{matrix}  (21)

The boundary conditions (d_{n,0} = 1 for all n ≥ 1 and d_{2,1} = 1) are clear. For the recurrence: identifying a labelled threshold graph with an element of O_{n}—the set of pairs (s, P) with s ∈ {+, −} and with P an ordered partition of [n] with the first block having size at least 2 (see Section 2.1)—we can read off d(G) from (s, P) as follows. If s = −, then d(G) is the number of elements in the even-numbered blocks of P (the second, fourth, et cetera), while if s = + it is one less than the number of elements in the odd-numbered blocks of P (the “one less” because we do not consider the initial vertex in the iterative construction to be dominating).

It follows that there are four templates for a labelled threshold graph on vertex set [n] with k dominating vertices in any iterative construction of G.

(i) (+, P), with an odd number of blocks in P, and with k + 1 elements in odd-numbered blocks. To enumerate these pairs, we have to choose:

• ℓ ≥ 1, the number of odd-numbered blocks;

• the elements in the union of those blocks—\binom{n}{k+1} options; and

• the ordered block decomposition among these ℓ blocks, noting that the first block must have at least two elements—op2_{k+1,ℓ} options;

• the ordered block decomposition of the ℓ − 1 blocks that get alternately interspersed among the ℓ already chosen blocks, noting that there are no restrictions on the block sizes—(ℓ − 1)!\left\{{n−k−1 \atop ℓ−1}\right\} options.

So the number of pairs following this template is

∑_{ℓ≥1} \binom{n}{k + 1} op2_{k+1,ℓ}(ℓ − 1)!\left\{{n − k − 1 \atop ℓ − 1}\right\}.

(ii) (+, P), with an even number of blocks in P, with k + 1 elements in odd-numbered blocks. By similar reasoning to case (i) above, the number of pairs following this template is

∑_{ℓ≥1} \binom{n}{k + 1} op2_{k+1,ℓ} ℓ!\left\{{n − k − 1 \atop ℓ}\right\}.

(iii) (−, P), with an odd number of blocks in P, with k elements in even-numbered blocks. The number of pairs following this template is

∑_{ℓ≥1} \binom{n}{k}ℓ!\left\{{k \atop ℓ}\right\} op2_{n−k,ℓ+1} .

(iv) (−, P), with an even number of blocks in P, with k elements in even-numbered blocks. The enumeration of pairs following this template is

∑_{ℓ≥1} \binom{n}{k}ℓ!\left\{{k \atop ℓ}\right\} op2_{n−k,ℓ} .

Combining (i) through (iv), (21) follows.

3 Proofs for quasi-threshold graph results

3.1 Proof of (8)

The goal of this section is to obtain a combinatorial proof of the identity

qt_{n} = ∑_{k=0}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}(k + 1)^{k−1},  (22)

where qt_{n} is the number of labelled quasi-threshold graphs on [n]. The proof will be via a sign-changing involution; see the discussion just after (8).

Say that a rooted forest F is a rooted partition forest on a finite set A ⊆ ℕ if the vertices of F are the blocks of a partition of A (as usual, into non-empty blocks). Let F_{A} be the set of rooted partition forests on A. Let F_{A}^{O} be the set of forests F in F_{A} with |A| − k odd, where k is the number of vertices of F, and let F_{A}^{E} be the set of those with |A| − k even.

Write F_{n} as shorthand for F_{[n]}. Since the number of rooted forests on k labelled vertices is (k + 1)^{k−1} (this is essentially Cayley’s formula), we have

\begin{aligned}|F_{n}| & = & ∑_{k=0}^{n} \left\{{n \atop k}\right\}(k + 1)^{k−1} and \\ |F_{n}^{E}| − |F_{n}^{O}| & = & ∑_{k=0}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}(k + 1)^{k−1}. \end{aligned}  (23)

We will prove (22) in two steps.

(a) First, we will identify a subset Q_{n} of F_{n} that is equinumerous with the set of labelled quasi-threshold graphs on [n]. All F ∈ Q_{n} will have n vertices (so, the underlying partition of [n] that forms the vertex set of F will be the partition into n singleton blocks), and so be in F_{n}^{E}.

(b) Then we will describe an involution ι on F_{n} with the following properties:

(i) if {F, F′} is an orbit of size two of ι, then one of F, F′ is in F_{n}^{O} and the other is in F_{n}^{E}, and

(ii) the set of fixed points of ι is Q_{n}.

Via (23), this establishes (22).

We start with (a). We will first encode labelled quasi-threshold graphs on [n] by rooted partition forests on [n], using an encoding implicitly given in [13, Section 2.1]. We then modify the rooted partition forests on [n] that occur in this encoding to create the set Q_{n}. The initial encoding of labelled quasi-threshold graphs by rooted partition forests is obtained inductively as follows.

• If a labelled quasi-threshold graph G on [n] has ℓ components, then the associated rooted forest F (G) has ℓ components, one corresponding to each component of G; and the component of F (G) corresponding to a particular component C is a rooted partition tree on the vertex set of C.

• If a component C of G is a singleton, then the associated rooted partition tree is a single vertex; more generally, if C is a complete graph, then the associated rooted partition tree is a single vertex, whose label is the vertex set of C.

• If on the other hand C is not a singleton and is not complete, then it has a collection D of dominating vertices, and the graph obtained from C, by deleting D, has more than one component. These components, say C_{1}, …, C_{ℓ}, inductively have associated rooted partition trees, T (C_{1}), …, T (C_{ℓ}), say. The rooted partition tree associated with C is obtained from T (C_{1}), …, T (C_{ℓ}) by adding a root with label D, and an edge from D to the root of T (C_{i}) for each i.

(See Figures 2 and 3.)

5 1 9 13 10 17 16 7 15 11 14 3 4 2 6 8 12

Figure 2: A quasi-threshold graph. The component on the left is a threshold graph with code (+, 5 1/9 13/10 16 17), and the component on the right has two dominating vertices (8 and 12) joined to the union of two threshold graphs; one with code (−, 7 15 11/3 14) and the other with code (+, 2 4/6).

\begin{matrix}\{10, 16, 17\} \\ \{1, 5\} \\ \{9\} \\ \{13\} \\ \{8, 12\} \\ \{3, 14\} \\ \{2, 4\} \\ \{6\} \\ \{7\} \\ \{15\} \\ \{11\} \end{matrix}

Figure 3: The rooted partition forest associated with the quasi-threshold graph in Figure 2.

The set of rooted partition forests on [n] that arise in this encoding, as we vary over labelled quasi-threshold graphs G on [n], is precisely the set of those in which all non-leaf vertices have degree at least 2 (these are sometimes referred to as phylogenetic forests). These forests will typically have some vertices whose labels are blocks of size 2 or greater; for the purposes of obtaining a sign-changing involution (step (b)) it is helpful to make a minor modification, so that all the blocks are singletons.

Specifically, in each rooted partition forest on [n] that arises in the encoding, we replace each vertex with a path; if the vertex has label C, the path has |C| vertices, and the labels on the vertices of the path are precisely the elements of C, arranged so that they are encountered in increasing order as we move away from the root (of whatever component we happen to be in). (See Figure 4.)

10 16 17 1 9 13 5 8 12 3 14 2 4 6 7 11 15

Figure 4: The modification of the rooted partition forest from Figure 3 to form a quasithreshold forest F. For typographic convenience we have not put the labels in braces here. The dashed edges indicate h(F).

We refer to the forests produced by this modification as quasi-threshold forests, and let Q_{n} be the set of all such forests; note that |Q_{n}| = qt_{n}, and that each F ∈ Q_{n} has n vertices, and so as promised is in F_{n}^{E}.

Next we turn to (b). We describe an involution ι defined on F_{n} that fixes Q_{n}, and that changes the parity of the number of vertices for each rooted partition forest that is not in Q_{n}.

We describe the involution recursively. Let F, a rooted partition forest on A, be given, where A is a finite subset of the natural numbers. (Our interest is in A = [n], but for the purposes of describing the involution recursively, it is more convenient to generalize slightly). The construction of ι involves examining a particular subgraph h(F) of F, and, depending on the nature of that subgraph, either making a modification to F to produce ι(F), or deleting the subgraph and recursing.

We begin by describing the process by which h(F) is identified.

• Let F′ be the component of F that contains among its labels the minimum element of A.

• If F′ consists of a single vertex, then we take h(F) to be F′. If F′ has more than one vertex, then let a be the root of F′, and let b be the first vertex of F′, encountered while travelling away from a, that is either a leaf or has more than one child (note that b may be the root itself). Equivalently, b is the last vertex on the longest path in F′ that starts at a and that, other than a and b, only uses vertices of degree 2. Let h(F) be this path from a to b.

(See Figure 4.)

We can now describe the process that produces ι(F). It will have two parts: if h(F) has all singleton labels that occur in increasing order (consistent with F being a quasi-threshold forest), then we recurse; otherwise, we immediately make a modification to produce ι(F). In the description that follows, we treat this second situation first.

• If it is not the case that h(F) has all singleton labels that occur in increasing order, then let v be the first vertex along the path from a to b that witnesses this failure. There are two (mutually exclusive) possibilities for v:

(A) The label of v is not a singleton, and either

– v = a, or

– the path from a up to (but not including) v has all singleton labels that occur in increasing order, and at least one of the elements in the label of v is larger than the label at the parent of v.

In this case, replace v with two vertices, v′ and v′′, with v′′ a child of v′, v′ a child of the parent of v (if v has a parent; otherwise, v′ becomes a root), and v′′ the parent of all the children of v. Set the label of v′ to be the largest element in the label of v, and set the label of v′′ to be all other elements in the label of v. Let the resulting rooted partition forest on A be ι(F).

(B) v ≠ a, the path from a up to (but not including) v has all singleton labels that occur in increasing order, and all the elements in the label of v (which now may or may not be a singleton) are smaller than the unique element in the label of the parent of v. In this case, contract (in the usual graph-theoretic sense) along the edge joining v and its parent, and set the label of the newly created vertex ṽ to be the union of the labels of v and its parent. Let the resulting rooted partition forest on A be ι(F).

(See Figure 5.)

• If h(F) has all singleton labels that occur in increasing order, then delete h(F) from F. We now perform one of two steps:

a = {4} {6} v = {2, 5, 7, 9} a = {4} {6} v′ = {9} v′′ = {2, 5, 7} ι

Figure 5: The vertex v in the graph on the left is of type (A), and the graph on the right shows the result after modifying at v. The vertex v′ in the graph on the right is of type (B), and the graph on the left shows the result after modifying at v′.

(1) If the result is the empty graph, then the process stops, and ι(F) = F

(2) Otherwise, the resulting graph is a rooted partition forest F̃ on a proper nonempty subset B of A (the children of b, if any, become roots of their components). In this case, on F̃ we run the algorithm currently being described, beginning with identifying h(F̃). This will (eventually, recursively) produce a rooted partition forest ι(F̃) on B. We turn this into a rooted partition forest on A by restoring h(F) (with a as root), and joining b to all the roots of the components in ι(F̃) that correspond to components in F′ − h(F) (from the construction of ι there is a natural one-to-one correspondence between these two sets of components). Set ι(F) to be the rooted partition forest on [n] thus produced from F̃.

Having defined ι, we now make the observations necessary to show that when A = [n], ι satisfies all conditions required by (b) (which recall are that ι is an involution on F_{n}, that if {F, F′} is an orbit of size two of ι then one of F, F′ is in F_{n}^{O} and the other is in F_{n}^{E}, and that the set of fixed points of ι is Q_{n}).

First, note that if F is a quasi-threshold forest on [n] then by construction we have ι(F) = F, and conversely if F is not a quasi-threshold forest on [n] then that failure will be witnessed at some vertex, and so ι(F) ≠ F. So the set of fixed points of ι is certainly Q_{n}

Second, note that if ι(F) ≠ F, then the number of vertices in F and F′ have different parities (when ι makes a change to a rooted partition forest, it either adds or subtracts a vertex).

So all that remains in the verification of (b) (and thus (22)) is to argue that ι is an involution, which we now do.

Claim 9. ι is an involution on F_{n}.

Proof. Suppose first that ι(F) is obtained from F by an application of the modification described in (A). Whether or not v = a, in ι(F) the first vertex that witnesses the failure of ι(F) to be a rooted partition forest is v′′, and ι(ι(F)) is obtained from ι(F) by an application of the modification described in (B); this undoes the change that turned F into ι(F), so in this case ι(ι(F)) = F.

Suppose on the other hand that ι(F) is obtained from F by an application of the modification described in (B). Then in ι(F) the first vertex that witnesses the failure of ι(F) to be a rooted partition forest is ṽ, and ι(ι(F)) is obtained from ι(F) by an application of the modification described in (A); this undoes the change that turned F into ι(F), so in this case also ι(ι(F)) = F.

3.2 Proof of (10)

The goal of this section is to establish that

qt-comp_{n,ℓ} = ∑_{k=1}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}ℓ\binom{k}{ℓ}k^{k−ℓ−1},  (24)

where qt-comp_{n,ℓ} is the number of labelled quasi-threshold graphs on n vertices with ℓ components (generalizing (9), the case ℓ = 1).

This follows immediately from the involution given in Section 3.1. Indeed, let f(k, ℓ) denote the number of rooted forests on k vertices with ℓ components; so f(k, 1) = k^{k−1}, and

f(k, ℓ) = ℓ\binom{k}{ℓ}k^{k−ℓ−1}

(see e.g. [1, Chapter 33]). It follows that ∑_{k=1}^{n} \left\{{n \atop k}\right\}ℓ\binom{k}{ℓ}k^{k−ℓ−1} enumerates rooted partition forests on [n] that have k components. Restricting ι to this set, and noting that ι does not change the number of components of a rooted partition forest, the discussion in Section 3.1 shows that the right-hand side of (24) counts quasi-threshold forests on [n] with ℓ components. By construction, the set of such forests is equinumerous with the set of labelled quasi-threshold graphs on [n] with ℓ components.

4 Proofs for loop-threshold graph results

4.1 Proof of (11)

The goal of this section is to give a combinatorial proof of the formula

lt_{n} = 2 ∑_{k=1}^{n} k!\left\{{n \atop k}\right\},  (25)

where lt_{n} is the number of labelled loop-threshold graphs on [n].

Recall that in Section 2 we observed that a labelled threshold graph on [n] can be encoded by a pair (s, P) where s ∈ {+, −} and P is an ordered partition of [n] with the first block having size at least 2.

By almost the same process, a labelled loop-threshold graph on [n] can be encoded by a pair (s, P) where s ∈ {+, −} and P is an ordered partition of [n], with no restriction on the size of the first block. We now describe this encoding.

Recall that a loop-threshold graph G can be constructed by either starting with an unlooped or a looped vertex, and then iteratively adding isolated or looped dominating vertices. If the construction of G begins with a looped vertex, then take s = +, and take as the first block of P the label assigned to the initial loop, together with the labels of all the added looped dominating vertices that are added before the first isolated vertex is added; then take the second block of P to be the labels of all the isolated vertices that are added before the next looped dominating vertex is added, and so on. If the construction of G begins with an isolated vertex, take s = − and then proceed similarly. It is easily seen that each loop-threshold graph has a unique code, and that for each pair (s, P) there is a unique loop-threshold graph that has (s, P) as its code. (See Figure 6.)

2 3 1 4 5 1 3 5 2 4

Figure 6: Two labelled loop threshold graphs. The one on the left has code (+, 23/14/5), while the one on the right has code (−, 1/3/5/24). (Larger nodes are looped, smaller nodes are unlooped.)

Since the number of ordered partitions of [n] is ∑_{k=1}^{n} k!\left\{{n \atop k}\right\}, (25) follows.

4.2 Proof of (12)

To goal of this section is to give a combinatorial proof of the identity

lt_{n} = ∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩2^{k+1},  (26)

and also to extend it to a combinatorial proof of the Frobenius identity (4).

In Section 4.1 we observed that labelled loop-threshold graphs on vertex set [n] may be encoded by pairs (s, P) where s ∈ {+, −} and P is an ordered partition of [n]. Since the right-hand side of (26) enumerates triples (s, π, c) where s ∈ {+, −}, π is a permutation of [n], and c is a 2-coloring of the ascents of π, to establish (26) it suffices to establish a bijection between the set of ordered partitions of [n], and the set of permutations of [n] together with a 2-coloring of the ascents of the permutation.

Here is one such bijection: given an ordered partition P of [n], set π = π_{f}(P) (see Definition 4). This permutation has some ascents π_{i} with the property that π_{i} and π_{i+1} are both in the same block of P. Color these ascents red, and color the remaining ascents blue. This is easily seen to an invertible map. Indeed, given a permutation with a 2-coloring of its ascents, the ordered partition that it comes from can be obtained by breaking the permutation at descents, and at ascents colored blue.

This argument easily extends to a combinatorial proof of the Frobenius identity, which recall says

∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩x^{k} = ∑_{ℓ=1}^{n} ℓ!\left\{{n \atop ℓ}\right\}(x − 1)^{n−ℓ}.  (27)

When x is a positive integer, the right-hand side of (4) counts

ordered partitions of [n], together with a coloring (from a palette [x − 1] of x − 1 colors) of the elements of [n] that are not the largest entry in their blocks,

while the left-hand side counts

permutations of [n], together with a coloring (from a palette [x] of x colors) of the ascents of the permutation.

Here is a bijection from the first set to the second. Given an ordered partition P of [n], together with an (x − 1)-coloring c of the elements that are not largest in their blocks, set π = π_{f}(P) (see Definition 4). All elements of [n] that are not largest in their blocks are ascents in π, so the coloring c is a partial x-coloring of the ascents of π. Extend it to a full x-coloring by giving all remaining ascents color x. This map is easily seen to be invertible. Indeed, given a permutation with an x-coloring of its ascents, the ordered partition that it comes from can be obtained by breaking the permutation at all descents, and at ascents given color x.

4.3 Proof of (13)

The goal of this section is to give a combinatorial proof of the identity

lt_{n} = ∑_{k=1}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}k!2^{k}  (28)

for n ≥ 0. We have dropped the k = 0 from (13) here, since \left\{{n \atop 0}\right\} = 1 for n ≥ 1; note that (13) holds vacuously for n = 0. The proof of (28) will be via a sign-changing involution; see the discussion just after (8).

We begin by observing that ∑_{k=1}^{n} \left\{{n \atop k}\right\}k!2^{k} counts pairs (P, c) where P is an ordered par-

tition of [n] and c : {P_{1}, …, P_{k}} → {red, blue} is a 2-coloring of the blocks of P.

Let P_{n} be the collection of all such pairs, and let P_{n,k} be those pairs in which P has k blocks (so our goal is to establish lt_{n} = ∑_{k=1}^{n}(−1)^{n−k}|P_{n,k}|). Let L_{n} ⊆ P_{n} be the set of pairs (P, c) with P = P_{1}/ ⋯ /P_{k} with the following two properties:

• each block P_{i} in P is a singleton, say P_{i} = {p_{i}}, (so k = n and L_{n} ⊆ P_{n,n}) and

• if c(P_{i}) = c(P_{i+1}) (that is, if two consecutive blocks have the same color) then p_{i} < p_{j}.

Claim 10. lt_{n} = |L_{n}|.

Proof. Recall from Section 4.1 that a labelled loop-threshold graph on [n] can be encoded by a pair (s, P) where s ∈ {+, −} and P is an ordered partition of [n]. Given such a pair, we modify it to turn it into an element of L_{n} as follows. Turn P = P_{1}/ ⋯ /P_{k} into an ordered partition P′ consisting of singleton blocks, by putting every element of block i before every element of block j for each i < j, and within block i, putting the elements in increasing order. If s = +, then let c(a) be red if a is in block P_{i} of P for some odd i, and blue otherwise; if s = − then flip the roles of red and blue. This gives a map from labelled loop-threshold graph on [n] to L_{n} that is clearly invertible.

Example 11. The pair (+, 23/14/5) maps to the pair (2/3/1/4/5, c) (a coloured ordered partition) where c^{−1}(red) = {2, 3, 5} and c^{−1}(blue) = {1, 4}, while (−, 1/3/5/24) maps to (1/3/5/2/4, c) where c^{−1}(red) = {2, 3, 4} and c^{−1}(blue) = {1, 5}.

In the presence of Claim 10, to prove (28) it suffices to find an involution ι on P_{n} with the following two properties:

(i) if {(P, c), (P′, c′)} is an orbit of size two of ι, then one of (P, c), (P′, c′) is in P_{n,k} with k even, and the other is in P_{n,k} with k odd (that is, ι changes the parity of the number of blocks in P), and

(ii) The set of fixed points of ι is L_{n}.

We first describe such an ι, and then show that it has all the claimed properties.

Given an ordered partition P = P_{1}/ ⋯ /P_{k} of [n] and a 2-coloring c of the blocks of P, scan the blocks in increasing order (P_{1} first, then P_{2}, et cetera), until the first time that a block P_{i} is encountered that satisfies one of the following two (mutually exclusive) conditions:

(A) P_{i} is not a singleton, or

(B) P_{i} = {p_{i}} is a singleton, and furthermore satisfies

• i < k (that is, P_{i} is not the final block of P), • c(P_{i}) = c(P_{i+1}), and

• p_{i} > p for all p ∈ P_{j+1} (that is, the unique element in P_{i} is larger than everything in the block that comes after it).

If the first such block that is encountered is P_{i}, of type (A), with P_{i} = {p_{i1}, …, p_{iℓ}} (p_{i1} < ⋯ < p_{iℓ}, ℓ ≥ 2), then modify (P, c) as follows.

• Replace P with P′ = P_{1}/ ⋯ /P_{i−1}/P′_{i}/P′′_{i}/P_{i+1}/ ⋯ /P_{k} where P′_{i} = p_{iℓ} and P′′_{i} = {p_{i1}, …, p_{i(ℓ−1)}}, and

• replace c with c′ that agrees with c on P_{j}, j ≠ i, and also satisfies c′(P′_{i}) = c′(P′′_{i}) = c(P_{i}).

(See Example 12 below.) In this case, set ι(P, c) = (P′, c′).

If the first such block encountered is P_{i} = {p_{i}} of type (B), with P_{i+1} = {p_{i1}, …, p_{iℓ}} (p_{i1} < ⋯ < p_{iℓ}, ℓ ≥ 2), then modify (P, c) as follows.

• Replace P with P′ = P_{1}/ ⋯ /P_{i−1}/P_{i} ∪ P_{i+1}/P_{i+2}/ ⋯ /P_{k}, and

• replace c with c′ that agrees with c on P_{j}, j ≠ i, and also satisfies c′(P_{i} ∪ P_{i+1}) = c(P_{i}) = c(P_{i+1}) (note that P_{i}, P_{i+1} have the same color by definition of a type (B) block).

(Again, see Example 12.) In this case, set ι(P, c) = (P′, c′).

Example 12. The pair (5/3/7/1/246/89, c) ∈ L_{9} with c^{−1}(red) = {1, 3, 5} and c^{−1}(blue) = {2, 4, 6, 7, 8, 9} gets mapped by ι to (5/3/7/1/6/24/89, c), and vice versa.

Call a block a flip block if it is a block of either type (A) or type (B). If no flip blocks are encountered, then set ι(P, c) = (P, c).

It is clear that if (P, c) is not a fixed point of ι, then the parity of the number of blocks of ι(P, c) is different from the parity of the number of blocks of (P, c) (ι either increases or decreases the number of blocks by 1). It is also clear, from the definition of L_{n} and the construction of ι, that the set of fixed points of ι (pairs (P, c) without a flip block) is precisely L_{n}. The proof of (28) will thus be completed by showing that ι is an involution, which we now do.

Claim 13. ι is an involution.

Proof. Suppose that the first flip block that is encountered in (P, c) is a block of type (A). With the notation as in the definition of ι above, consider the pair (P′, c′). This certainly has a block of type (B), namely P′_{i} = p_{iℓ}. If P′_{i} is the first block of either type (A) or type (B) in P′, then ι(P′, c′) = (P, c). We claim that P′_{i} is indeed the first such block.

Indeed, if P_{j} with j < i − 1 is a flip block in (P′, c′), then clearly it is also a flip block in (P′, c′), a contradiction. If P_{i−1} is a block of type (A) in (P′, c′), then it is a block of type (A) in (P, c), again a contradiction.

Finally, if P_{i−1} is a block of type (B) in (P′, c′), then it is a singleton in both P and P′, is not the last block in either, has the same color under c′ as P′_{i}, so has the same color under c as P_{i}, and its one element is larger than p_{iℓ}, so is larger than every element in P_{i}. It follows that P_{i−1} is a block of type (B) in (P, c), a contradiction. The conclusion is that if the first block that is encountered in (P, c) is a block of type (A), then (ι ∘ ι)(P, c) = (P, c).

Now suppose that the first flip block that is encountered in (P, c) is a block of type (B). With the notation as in the definition of ι above, consider the pair (P′, c′). This certainly has a block of type (A), namely P_{i}∪P_{i+1}. If this is the first flip block in P′, then ι(P′, c′) = (P, c). We claim that P_{i} ∪ P_{i+1} is indeed the first such block.

Indeed, as before, if either P_{j} with j < i − 1 is a flip block in (P′, c′), or if P_{i−1} is a block of type (A) in (P′, c′), then we quickly arrive at a contradiction.

The remaining case to consider is when P_{i−1} is a block of type (B) in (P′, c′). In this case it is a singleton in both P and P′, is not the last block in either, it has the same color under c′ as P_{i} ∪ P_{i+1}, so has the same color under c as P_{i}, and its one element is larger than everything in P_{i} ∪ P_{i+1}, so is larger than the one element in P_{i}. It follows that P_{i−1} is a block of type (B) in (P, c), a contradiction. The conclusion is that if the first flip block that is encountered in (P, c) is a block of type (B), then (ι ∘ ι)(P, c) = (P, c). This completes the verification that ι is an involution.

4.4 Counting labelled loop-threshold graphs by number of components

Let lt-comp_{n,k} be the number of labelled loop-threshold graphs on vertex set [n] with k components. The goal of this section is to give the straightforward verification of the identities (valid for n, k ≥ 1)

(i) lt-comp_{n,1} = ∑_{k=0}^{n−1} \left⟨{n \atop k}\right⟩2^{k},

(ii) for n ≥ 3 and 2 ≤ k ≤ n − 1, lt-comp_{n,k} = \binom{n}{k−1} lt-comp_{n−k+1,1}, and

(iii) for n ≥ 2, lt-comp_{n,n} = n + 1.

To see (i), recall that labelled loop-threshold graphs on [n] are encoded by pairs (s, P) where s ∈ {+, −} and P is an ordered partition of [n]. From the correspondence given in Section 4.1 we see that if P has an odd number of blocks then (+, P) is connected (its construction ends with the addition of some looped dominating vertices) while (−, P), whose construction ends with the addition of some isolated vertices, is not connected. On the other hand if P has an even number of blocks then (−, P) is connected while (+, P) is not. It follows that half of all loop-threshold graphs on [n] are connected, and (i) follows from (26). (This argument could also have been presented as follows. The map that sends a graph to its complement is an involution on loop-threshold graphs that sends connected graphs to disconnected, and vice-versa).

For (ii): for n ≥ 3 and 2 ≤ k ≤ n − 1, the set of labelled loop-threshold graphs on vertex set [n] with k components is obtained by choosing k − 1 elements from [n], choosing a connected labelled loop-threshold graph on the remaining n − k + 1 elements, and then adding the chosen k − 1 elements as isolated vertices.

For (iii): up to isomorphism there are two loop-threshold graphs on vertex set [n] with n components. One is the edgeless graph, which has one possible labelling. The other consists of a looped vertex together with n − 1 isolated vertices, and this has n possible labellings.

5 Proofs for quasi-loop-threshold graph results

Let qlt_{n} denote the number of labelled quasi-loop-threshold graphs on n vertices. One goal of this section is to combinatorially establish the formula

qlt_{n} = ∑_{k=1}^{n+1} \left\{{n + 1 \atop k}\right\}k^{k−2}.  (29)

The second goal is to show that qlt-conn_{n}, the number of connected labelled quasi-loop-threshold graphs on n vertices, satisfies qlt-conn_{2} = 2 and for n ≥ 2

qlt-conn_{n} = ∑_{k=1}^{n} \left\{{n \atop k}\right\}k^{k−1}.  (30)

We start with (30), which will prove to be a useful stepping-stone to (29).

Claim 14. For n ≥ 1, ∑_{k=1}^{n} \left\{{n \atop k}\right\}k^{k−1} (the right-hand side of (30)) enumerates labelled quasi-loop-threshold graphs on n vertices that have at least one looped dominating vertex.

This immediately yields (30)—for n ≥ 2, being connected and having at least one looped dominating vertex are equivalent, and (30) is easy for n = 1.

Proof (of Claim 14). Since for n ≥ 1 the right-hand side of (30) counts rooted partition trees on [n]—recall, these are rooted labelled trees whose vertex set is a partition of [n]—we will obtain the claim by exhibiting a bijection from labelled quasi-loop-threshold graphs on vertex set [n] that have at least one looped dominating vertex, to rooted partition trees on [n].

The bijection is defined inductively (and is illustrated in Figure 7). On a vertex set of size one there is just one labelled quasi-loop-threshold graph with a looped dominating vertex, and just one possible rooted tree, so there is nothing to do for n = 1. Given a labelled quasiloop-threshold graph G on vertex set [n], n ≥ 2, that has at least one looped dominating vertex, let A be the set of looped dominating vertices. We begin constructing the tree T′(G) associated with G by letting the root of T′(G) have label A.

By the definition of quasi-loop-threshold graphs, on deleting A from G the result is a graph G′ that has a number of components, some of which might themselves have looped dominating vertices, and some of which might not (and note that components that do not have a looped dominating vertex must be isolated vertices—components of size 1 that are not looped). It is possible that G′ may have only one component, and in this case that component must be isolated (if not, then any looped dominating vertex of the sole component of G′ would in fact be an element of A). From this it follows that if G′ has no components that are isolated vertices, than G′ must have at least two components (all of which have looped dominating vertices). This is the crucial fact that gets used in the tree construction below, that allows us to distinguish between isolated vertices in G′ and components that consist of a single looped vertex.

Specifically, if G′ has some isolated vertices, let B be the set of such vertices, and let the root A of T′(G) have one child whose label is B. Each of the remaining components of G′, say C_{1}, …, C_{ℓ}, has at least one looped dominating vertex, and so by induction has an associated rooted partition tree. Complete the construction of T′(G) by joining each of T′(C_{1}), …, T′(C_{ℓ}) to B via edges from the roots of the T′(C_{i}).

If, on the other hand, G′ has no isolated vertices, then G′ must have at least two components, each of which has a looped dominating vertex. Let C_{1}, …, C_{ℓ} be these components. Complete the construction of T′(G) by joining each of T′(C_{1}), …, T′(C_{ℓ}) to A via edges from the roots of the T′(C_{i}).

This process associates a rooted partition tree on [n] to each labelled quasi-loop-threshold graph on vertex set [n] with at least one looped dominating vertex (see Figure 7), and the process is invertible. This completes the verification that the the right-hand side of (30) counts labelled quasi-loop-threshold graphs on vertex set [n] with at least one looped dominating vertex.

We now turn to (29). The right-hand side of (29) counts partition trees on [n + 1]—that is, labelled (but not rooted) trees whose vertices form a partition of [n + 1]. Thus our goal now is to describe a bijective correspondence from labelled quasi-threshold graphs on vertex set [n] to partition trees on [n + 1].

So, let a labelled quasi-loop-threshold graph G on vertex set [n] be given. There are three possibilities.

(a) If G has some isolated vertices, let B be the set of isolated vertices, and let C_{1}, …, C_{ℓ} be the components of G that have looped dominating vertices. We construct an associated tree T (G) as follows. The tree T (G) has a vertex with label {n + 1}. Vertex {n + 1} has one neighbour, whose label is B. Vertex B is also joined to the root of the tree T′(C_{i}), for each i, where T′(C_{i}) (whose vertices form a partition of the vertex set of T_{i}) is the rooted tree constructed in proof of Claim 14. (See Figure 8.) Note that no special property of the set [n] was used in the proof of Claim 14, so we could have replaced [n] there with an arbitrary finite set.

(b) If G has no isolated vertices, and also has no looped dominating vertex, then G is 2 5 1 7 9 4 11 10 3 12 8 6

\begin{matrix}\{6, 8\} \\ \{9\} \\ \{3, 12\} \\ \{1, 7\} \\ \{2, 5\} \\ \{10\} \\ \{11\} \\ \{4\} \end{matrix}

Figure 7: A labelled quasi-loop-threshold graph with looped dominating vertex (larger nodes are looped, smaller nodes are unlooped), and its associated rooted partition tree.

\begin{matrix}1 \\ 5 \\ 2 \\ 3 \\ 4 \\ \{6\} \\ \{2, 3\} \\ \{1, 5\} \\ \{4\} \end{matrix}

Figure 8: A labelled quasi-loop-threshold graph of type (a) (left), and its associated partition tree. Here and in Figures 9 and 10, larger nodes indicate looped vertices.

the union of components C_{1}, …, C_{ℓ} (ℓ ≥ 2) each of which has a looped dominating vertices. We construct T (G) as follows. The tree T (G) has a vertex with label {n+1}. Vertex {n + 1} is joined to the root of the tree T′(C_{i}) (from Claim 14), for each i. (See Figure 9.)

(c) Finally, if G has some looped dominating vertices, then we construct T (G) as follows. Add n + 1 to the set that labels the root of T′(G) (from Claim 14), and view the resulting tree (whose vertex set is a partition of [n + 1]) as an unrooted tree. (See

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ \{6\} \\ \{1, 2\} \\ \{4\} \\ \{3\} \\ \{5\} \end{matrix}

Figure 9: A labelled quasi-loop-threshold graph of type (b) (left), and its associated partition tree.

Figure 10.)

\begin{matrix}1 \\ 3 \\ 2 \\ 4 \\ 5 \\ \{1, 3, 6\} \\ \{2, 4, 5\} \end{matrix}

Figure 10: A labelled quasi-loop-threshold graph of type (c) (left), and its associated partition tree.

This process associates a partition tree on [n+1] to each labelled quasi-loop-threshold graph on vertex set [n], and the association is invertible. This completes the verification of (29).

References

[1] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK (6th edition), Springer, 2018.

[2] Janet Simpson Beissinger and Uri N. Peled, Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials, Graphs Combin. 3 (1987), 213–219.

[3] Miklós Bóna, Combinatorics of Permutations (2nd edition), CRC Press, 2012.

[4] Arthur T. Benjamin and Jennifer J. Quinn, An alternate approach to alternating sums: a method to DIE for, College Math. J. 39 (2008), 191–202.

[5] Vacláv Chvátal and Peter L. Hammer, Set packing problems and threshold graphs, Technical Report CORR 73-21, University of Waterloo, 1973.

[6] Vacláv Chvátal and Peter L. Hammer, Aggregation of inequalities in integer programming, in P. Hammer, E. Johnson, and B. Korte et al. (eds.), Studies in Integer Programming (Proc. Workshop Bonn 1975), Annals of Discrete Mathematics 1 (1977), 145–162.

[7] Jonathan Cutler and A. J. Radcliffe, Extremal graphs for homomorphisms, J. Graph Theory 67 (2011), 261–284.

[8] Jonathan Cutler and A. J. Radcliffe, Extremal graphs for homomorphisms II, J. Graph Theory 76 (2014), 42–59.

[9] G. Frobenius, Über die Bernoullischen Zahlen und die Eulerschen Polynome, Sitzungsberichte der Preussische Akademie der Wissenschaften (1910), 809–847.

[10] Martin Charles Golumbic, Trivially perfect graphs, Discrete Math. 24 (1978), 105–107.

[11] Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97–117.

[12] N. V. R. Mahadev and U. N. Peled, Threshold Graphs and Related Topics (Annals of Discrete Mathematics 56), North-Holland, 1995.

[13] Stavros D. Nikolopoulos and Charis Papadopoulos, A formula for the number of spanning trees in quasi-threshold graphs, retrieved from http://www.cs.uoi.gr/~charis/

    files/192nikpap.pdf, March 1 2022.

[14] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, retrieved March 1 2022.

[15] Sam Spiro, Counting labeled threshold graphs with Eulerian numbers, Australas. J. Combin. 77 (2020), 249–255.

[16] Herbert S. Wilf, generatingfunctionology (2nd edition), Academic Press, Boston, 1994.

[17] E. S. Wolk, The comparability graph of a tree, Proc. Amer. Math. Soc. 13 (1962), 789–795.

2020 Mathematics Subject Classification: Primary 05C30. Secondary 05A18, 05A19. Keywords: threshold graph, quasi-threshold graph, loop-threshold graph, quasi-loop-threshold graph, Stirling number of the second kind, Eulerian number, set partition.

(Concerned with sequences \underline{A000629}, \underline{A000670}, \underline{A005840}, \underline{A008277}, \underline{A008292}, \underline{A038052}, \underline{A048802}, \underline{A053525}, \underline{A058863}, \underline{A058864}, \underline{A154921}, \underline{A317057}, \underline{A348436}, \underline{A348576}, \underline{A350060}, \underline{A350528}, \underline{A350531}, \underline{A350745}, and \underline{A350746}.)

Received January 13 2022; revised version received March 2 2022. Published in Journal of Integer Sequences, March 2 2022.

Return to Journal of Integer Sequences home page.