On the Number of Labeled k-arch Graphs

Saverio Caminiti and Emanuele G. Fusco Department of Computer Science University of Rome “La Sapienza” Via Salaria 113 00198 Rome Italy

                    caminiti@di.uniroma1.it
                     fusco@di.uniroma1.it

Abstract In this paper we deal with k-arch graphs, a superclass of trees and k-trees. We give a recursive function counting the number of labeled k-arch graphs. Our result relies on a generalization of the well-known Prüfer code for labeled trees. In order to guarantee the generalized code to be a bijection, we characterize the valid code strings.

A previous attempt at counting the number of labeled k-arch graphs was made by Lamathe. We point out an error in his work, and prove it by giving a counterexample.

1 Introduction

The problem of counting labeled trees has been widely studied, and there exists a variety of proofs for the well-known Cayley formula [1], which states that the number of labeled trees of n nodes is n^{n−2} (for a survey, see [4]). Among these proofs, the one given by Prüfer [5] is based on a one-to-one correspondence between labeled trees and strings of length n − 2 over the alphabet {1, …, n}. This bijection is known as the Prüfer code.

In 1970 Rényi and Rényi [6] generalized the Prüfer bijective proof of Cayley’s formula to count labeled k-trees, i.e., one of the most natural generalizations of trees.

The class of k-trees, introduced by Harary and Palmer [2], can be defined in the following recursive way:

1. A complete graph on k nodes is a k-tree.

2. If T′_{k} = (V, E) is a k-tree, K ⊆ V is a k-clique and v ∉ V, then T_{k} = (V ∪ {v}, E ∪ {(v, x) | x ∈ K}) is also a k-tree.

A labeled k-tree is a k-tree whose nodes are assigned distinct labels. They showed the number of labeled k-trees of n nodes to be \binom{n}{k} (k(n − k) + 1)^{n−k−2}. This result gave birth to sequences \underline{A036361}, \underline{A036362}, and \underline{A036506} in Sloane’s On-line Encyclopedia of Integer Sequences [7].

The class of k-trees can be further generalized by relaxing the constraint in item 2 asking for the node set K to be a clique. Graphs belonging to this class, introduced by Todd [8], are known as the k-arch graphs.

A k-arch graph can be defined in the following recursive way:

1. A complete graph on k nodes is a k-arch graph.

2. If A′_{k} = (V, E) is a k-arch graph, K ⊆ V of cardinality k and v ∉ V, then A_{k} = (V ∪ {v}, E ∪ {(v, x) | x ∈ K}) is also a k-arch graph.

The class of k-arch graphs can be equivalently defined as the smallest class such that:

1. A complete graph on k nodes is a k-arch graph;

2. If A′_{k}, obtained by removing a node of degree k from A_{k}, is a k-arch graph, then A_{k} is a k-arch graph.

A labeled k-arch graph is a k-arch graph whose nodes are assigned distinct labels. In this paper we deal with labeled k-arch graphs; we use integers in [1, n] as node labels, where n always refers to |V |. When no confusion arises we identify a node with its label. An example of a labeled 3-arch graph on 10 nodes is given in Figure 1.

Note that when k = 1 both k-trees and k-arch graphs are Cayley trees.

An attempt to generalize the Prüfer bijective proof of Cayley’s formula to count labeled k-arch graphs has been made by Lamathe [3]. He established a correspondence relating k-arch graphs and strings over the alphabet whose symbols are all k-subsets of the vertex set of a given k-arch graph. He claimed this correspondence to be a bijection and derived the number of labeled k-arch graphs of n nodes to be \binom{n}{k}^{n−k−1}. Unfortunately this result is wrong, as the majority of the strings do not represent any k-arch graph, meaning that the shown correspondence is not a bijection (see Section 3 for an example of an invalid string). Indeed, Lamathe’s formula produces a serious overestimation of the number of labeled k-arch graphs. In the following table we show the overestimation ratio for certain values of n and k:

\begin{matrix}n\k & 2 & 3 & 4 \\ 10 & 1.6311 & 3.9045 & 5.4925 \\ 15 & 4.8581 & 85.8627 & 806.9044 \\ 20 & 18.8593 & 3699.9280 & 434531.3726 \end{matrix}

The ratio dramatically increases when n and k increase; this implies that almost all strings do not correspond to k-arch graphs. As an example, consider that when n = 200 and k = 185, the ratio is 1.6681 × 10^{104}.

The error made by Lamathe is to consider every possible string as the encoding of some k-arch graph. Instead the subset of strings resulting from encoding k-arch graphs needs to be correctly characterized, in the same way that Rényi and Rényi did for k-trees.

In this paper we exhibit the flaw in the Lamathe’s formula by showing a simple counterexample. We provide a characterization of valid strings, and then we exploit properties of those strings in order to define a recursive function that computes the number of labeled k-arch graphs of n nodes, for any given n and k.

2 Encoding k-arch Graphs

Let A_{k}^{n} be the set of all k-arch graphs of n nodes, let \binom{[1,n]}{k} be the set of all k-subset of the integer interval [1, n], and let B_{k}^{n} be the set of all possible strings of length n − k − 1 over the alphabet \binom{[1,n]}{k}. We use the notation adj(v) to identify the set of all nodes adjacent to a given node v, and the term k-leaf to mean a node u such that |adj(u)| = k; any other node v has |adj(v)| > k and is called internal.

Let us define the following function:

ρ(A_{k}^{n}) = \{ \begin{matrix}ε, & if A_{k}^{n} is a single k + 1 clique; \\ adj(min\{v ∈ A_{k}^{n} : |adj(v)| = k\}) :: ρ(A_{k}^{n} \ \{v\}), & otherwise. \end{matrix}

The function ρ is the injective function between A_{k}^{n} and B_{k}^{n} used by Lamathe, i.e., the generalization made by Rényi and Rényi of the Prüfer bijection applied to k-arch graphs. The recursion described by ρ embodies a pruning of the k-arch graph A_{k}^{n} that starts from the smallest k-leaf v; as v is removed from A_{k}^{n}, its adjacent set constitutes the first symbol of the string. This symbol is concatenated (by string concatenation operator ::) to the string obtained by recursively applying the function to the pruned graph. The recursion terminates when the pruning gives a clique on k + 1 nodes, as ρ applied to a clique gives the empty string ε.

Note that, by definition of k-arch graphs, every subgraph produced during the pruning process is a k-arch graph.

It is worth remarking that we are assuming n > k, as well as the Prüfer code assumes the tree to have at least 2 nodes. When n = k, the only admissible k-arch graph is a single clique with |A_{k}^{k}| = 1. When n < k, obviously |A_{k}^{n}| = 0.

Let us show an example of the encoding process realized by the function ρ. Starting from the 3-arch graph of Figure 1, we prune it by recursively removing the smallest k-leaf. At each step the set of nodes adjacent to the removed k-leaf is added to the string.

The smallest k-leaf of the initial graph is v_{1} = 2 and its adjacent nodes are B_{1} = {1, 6, 9}. Then node 2 is removed from the graph, and the smallest k-leaf in the resulting graph is v_{2} = 3, implying B_{2} = {1, 5, 8}. Iterating this procedure we obtain v_{3} = 6, v_{4} = 4, v_{5} = 7, v_{6} = 9 and B_{3} = {4, 8, 10}, B_{4} = {1, 5, 9}, B_{5} = {5, 8, 10}, B_{6} = {1, 5, 8} respectively. The remaining graph is a single clique of 4 nodes {1, 5, 8, 10}. Therefore the resulting string is (B_{1}, B_{2}, B_{3}, B_{4}, B_{5}, B_{6}) = ({1, 6, 9}, {1, 5, 8}, {4, 8, 10}, {1, 5, 9}, {5, 8, 10}, {1, 5, 8}).

For a given k-arch graph A_{k}^{n}, we say a node v ∈ V (A_{k}^{n}) appears in ρ(A_{k}^{n}) if ∃B_{i} ∈ ρ(A_{k}^{n}) such that v ∈ B_{i}.

Lemma 1. v is an internal node in A_{k}^{n} if and only if it appears in ρ(A_{k}^{n}).

Figure 1: A labeled 3-arch graph on 10 nodes.

Proof. Consider an internal node v in A_{k}^{n}: its initial degree is strictly greater than k. The pruning process embodied by ρ ends with a (k + 1)-clique, where each node has degree k, so either v has been eliminated in some step or it belongs to the remaining clique; in both cases its degree must decrease to k. Since the degree of an internal node v can decrease only if in some step i a k-leaf adjacent to v is removed, v must belong to B_{i}.

Let us now show that if an element appears in ρ(A_{k}^{n}), then it is an internal node. Consider a k-leaf v, and suppose by contradiction that there exists some value i such that v ∈ B_{i}. This means that after removing a k-leaf on step i, in the resulting graph node v has degree k − 1. This contradicts the fact that each subgraph produced during the encoding process is k-arch graph.

Proposition 2. Function ρ is injective.

Proof. We have to show that, given two k-arch graphs A_{k}^{n}′ and A_{k}^{n}′′, if ρ(A_{k}^{n}′) = ρ(A_{k}^{n}′′) = (B_{1}, …, B_{n−k−1}) then A_{k}^{n}′ = A_{k}^{n}′′.

Let us proceed by induction on n − k. If n − k = 1, ρ(A_{k}^{n}′) = ρ(A_{k}^{n}′′) = ε, then A_{k}^{n}′ = A_{k}^{n}′′ as the only k-arch graph on k + 1 nodes is a (k + 1)-clique.

For inductive hypothesis, assume the hypothesis holds when n−k < h. We have to prove that it holds when n − k = h.

In order to have ρ(A_{k}^{n}′) = ρ(A_{k}^{n}′′), for Lemma 1, the sets of internal nodes and the sets of k-leaves in A_{k}^{n}′ and A_{k}^{n}′′ must coincide. It follows that the minimum k-leaf v_{1} in A_{k}^{n}′ coincides with the minimum k-leaf in A_{k}^{n}′′ and both are adjacent to the same node set B_{1}. Moreover, the graphs obtained by pruning v_{1} from A_{k}^{n}′ and A_{k}^{n}′′, in order to produce the same substring (B_{2}, …, B_{n−k−1}), have to be the same graph by inductive hypothesis. This implies A_{k}^{n}′ = A_{k}^{n}′′, as removing the same node and the same edge set from them results in the same graph.

3 Decoding k-arch Graphs

In this section we show how to revert function ρ in order to rebuild an encoded k-arch graph.

Starting from a string (B_{1}, …, B_{l}) that is the encoding of an unknown k-arch graph A_{k}^{n}, at first we need to recover values n and k: k = |B_{1}| = |B_{2}| = ⋯ = |B_{l}| and, since l = n − k − 1, we can derive n = l + k + 1. The node set of A_{k}^{n} is [1, n] so, to complete the decoding process, we need to reconstruct its edge set.

In view of Lemma 1, it is easy to derive the set of all k-leaves of A_{k}^{n} as [1, n] \ ⋃ B_{i}. We can compute v_{1} (the first k-leaf removed during the encoding process) as the minimum of this set. We also know adj(v_{1}) = B_{1}.

Now, v_{2} is the smallest k-leaf of A_{k}^{n} \ {v_{1}} and we know both the node set of this k-arch graph (i.e., [1, n] \ {v_{1}}) and its code string (B_{2}, …, B_{l}). Then v_{2} = min{v ∈ [1, n] \ {v_{1}} \ ⋃_{i=2}^{l} B_{i}}.

Generalizing this idea it is possible to derive a formula analogous to the one given by Prüfer for trees:

v_{i} = min {v ∈ [1, n] \ {v_{h}}_{h<i} \ ⋃_{j≥i} B_{j}} ∀i ∈ [1, l]

Knowing the k-leaf removed at each step of the encoding process it is easy to rebuild the edge set of A_{k}^{n}. Indeed, all the k + 1 nodes not in {v_{1}, …, v_{l}} form a clique and each v_{i} should be connected with all nodes in B_{i}. We will refer to this decoding process as ρ^{−1}. It is easy to see that the codomain of ρ^{−1} is A_{k}^{n}.

Obviously not all strings in B_{k}^{n} are eligible for this decoding procedure. Indeed, it requires the set from which each v_{i} is chosen to be not empty. To better explain this fact we now show a simple string that does not correspond to the encoding of any k-arch graph; this is in fact the easiest counterexample that proves Lamathe’s formula to be not correct.

Consider the string ({1, 2}, {3, 4}, {5, 6}): in this case k = 2 and n = 3 + 2 + 1 = 6. Since the set [1, 6] \ ({1, 2} ∪ {3, 4} ∪ {5, 6}) is empty, there is no value for v_{1}, so there can not exist any k-arch graph whose encoding is ({1, 2}, {3, 4}, {5, 6}).

It is quite easy to see, from definition of ρ^{−1}, that ρ^{−1}(ρ(A_{k}^{n})) = A_{k}^{n} for each k-arch graph A_{k}^{n}. We now characterize all those strings in B_{k}^{n} resulting by the encoding of some k-arch graph. Let us call the set of these strings C_{k}^{n} ⊆ B_{k}^{n}. Notice that C_{k}^{n} is the image of A_{k}^{n} under function ρ, i.e., C_{k}^{n} = ρ(A_{k}^{n}).

Theorem 3. Given (B_{1}, …, B_{l}) ∈ B_{k}^{n} if ∃\{v_{1}, …, v_{l}\} ∈ \binom{[1,n]}{l} such that v_{i} ∉ ⋃_{j=i}^{l} B_{j} then (B_{1}, …, B_{l}) ∈ C_{k}^{n}.

Proof. The existence of \{v_{1}, …, v_{l}\} ∈ \binom{[1,n]}{l} ensures that the decoding process can be applied, but this is not enough to ensure (B_{1}, …, B_{l}) ∈ C_{k}^{n}. Indeed there is a reasonable doubt that the k-arch graph A_{k}^{n} = ρ^{−1}(B_{1}, …, B_{l}) obtained by decoding an arbitrary string in B_{k}^{n}, can produce a different string (B′_{1}, …, B′_{l}) = ρ(A_{k}^{n}) when encoded. We will show this is not the case.

Without loss of generality assume that v_{1}, …, v_{l} coincides with the sequence of nodes chosen by ρ^{−1} at each step during the decoding process. Now, by induction on l, we prove that ρ(ρ^{−1}(B_{1}, …, B_{l})) = (B_{1}, …, B_{l}).

\binom{3}{2}\binom{4}{1} \binom{3}{1}\binom{4}{2} \binom{3}{0}\binom{4}{3}  \binom{4}{3}\binom{3}{0} \binom{4}{2}\binom{3}{1} \binom{4}{1}\binom{3}{2}  \binom{5}{3}\binom{2}{0} \binom{5}{2}\binom{2}{1}^{\binom{7}{3}}^{\binom{3}{2}\binom{4}{1}}  ^{\binom{3}{1}\binom{4}{2}}^{\binom{3}{3}\binom{4}{0}} \binom{3}{3}\binom{4}{0}  0  2 0  1  2  3  0  1  2  0  1 max = 5 max = 4 max = 6  1

Figure 2: Recursion tree for counting 3-arch graphs on 7 nodes.

When l = 0, the string can only be ε, the resulting graph is a (k + 1)-clique and its encoding is again ε. We assume, by inductive hypothesis, the thesis holds for any string of length l < h and we prove it holds for strings of length l = h. First note that if the string (B_{1}, …, B_{l}) is decoded as the k-arch graph A_{k}^{n}, then the substring B_{2}, …, B_{l} is decodable and results in the graph A_{k}^{n−1} = A_{k}^{n} \ {v_{1}}. By inductive hypothesis ρ(A_{k}^{n−1}) = (B_{2}, …, B_{l}) (here the node set does not contain v_{1}). The degree of v_{1} in A_{k}^{n} is |B_{1}| = k, so it is a k-leaf. Any other node with label smaller than v_{1} appears in (B_{1}, …, B_{l}), as otherwise ρ^{−1} would have done a different choice for v_{1}. This implies that v_{1} is the minimum k-leaf in A_{k}^{n}. Then ρ(A_{k}^{n}) = adj(v_{1}) :: ρ(A_{k}^{n−1}) = (B_{1}, …, B_{l}).

Since in proof of Theorem 3 we proved that ρ(ρ^{−1}(B_{1}, …, B_{l})) = (B_{1}, …, B_{l}) for each string in C_{k}^{n}, we can state that ρ^{−1} : C_{k}^{n} → A_{k}^{n} is exactly the inverse function of ρ : A_{k}^{n} → C_{k}^{n}.

4 Counting k-arch Graphs

We are interested in finding the number of k-arch graphs on n nodes, i.e., |A_{k}^{n}|. Since |A_{k}^{n}| = |C_{k}^{n}|, in order to count labeled k-arch graphs we will count valid code strings. The condition for a string (B_{1}, …, B_{l}) to be a valid encoding of a k-arch graph (stated in Theorem 3) can be easily reformulated as:

∀i : 1 ≤ i ≤ l, | ⋃_{h=i}^{l} B_{h}| ≤ n − i  (1)

Exploiting condition of Equation 1, it possible to define a recursive function to count the number of labeled k-arch graphs on n nodes. Before providing this general formula let us show an example of our approach applied to |C_{3}^{7}|.

The basic idea is to simulate the generation of a valid code string (B_{1}, B_{2}, B_{3}), from right to left, and count how many choices we have at each step. The choice for B_{3} gives \binom{7}{3} alternatives, as Equation 1 requires that no more than 4 different numbers appear in substring (B_{3}); this substring always contains 3 distinct numbers, then the requirement is always satisfied.

Now consider B_{2}. Equation 1 requires at most 5 distinct numbers to appear in substring (B_{2}, B_{3}), thus imposing some limits on choices for B_{2}. In fact valid choices are those selecting 3, 2 or 1 numbers appearing in B_{3} and respectively 0, 1 or 2 unused numbers, giving \binom{3}{3}\binom{4}{0}, \binom{3}{2}\binom{4}{1} and \binom{3}{1}\binom{4}{2} distinct alternatives. Similar arguments hold for B_{1} and constraints depend on how many distinct numbers appear in (B_{2}, B_{3}). More explicitly, since Equation 1 imposes to have at most 6 distinct numbers, if u distinct numbers appear in (B_{2}, B_{3}), then B_{1} can introduce up to min(3, 6 − u) unused numbers.

Figure 2 gives the complete recursion tree for the described process. The root represents choices for B_{3}; children of the root represent choices for B_{2} and leaves choices for B_{1}. For each level, on the left the bound given by Equation 1 is reported; labels on edges represent how many new numbers are introduced. |C_{3}^{7}| = 34405 is given by the sum of the products of labels given by each leaf-to-root path in the tree:

\binom{7}{3}( \binom{3}{3}\binom{4}{0} (\binom{3}{3}\binom{4}{0} + \binom{3}{2}\binom{4}{1} + \binom{3}{1}\binom{4}{2} + \binom{3}{0}\binom{4}{3})+
\binom{3}{2}\binom{4}{1} (\binom{4}{3}\binom{3}{0} + \binom{4}{2}\binom{3}{1} + \binom{4}{1}\binom{3}{2})+
\binom{3}{1}\binom{4}{2} (\binom{5}{3}\binom{2}{0} + \binom{5}{2}\binom{2}{1}) )

Now we introduce the main result of this paper.

Theorem 4. The number of labeled k-arch graph on n > k + 1 nodes is |A_{k}^{n}| = f_{k}^{n}(n − k − 1, 0, k) where f_{k}^{n} is the recursive function defined as:

f_{k}^{n}(i, u, j) = \{ \begin{matrix}\binom{n−u}{j}\binom{u}{k−j}, & if i = 1; \\ \binom{n−u}{j}\binom{u}{k−j}∑_{c=0} f_{k}^{n}(i − 1, u + j, c)^{min(k,n−(i−1)−(u+j))}, & otherwise. \end{matrix}

When n = k or n = k + 1 |A_{k}^{n}| = 1; when n < k |A_{k}^{n}| = 0.

Proof. Given the string (B_{1}, …, B_{l}) ∈ C_{k}^{n}, we call characteristic of this string the vector \overline{c} = (c_{1}, …, c_{l−1}) such that c_{i} = |B_{i} \ ⋃_{j>i} B_{j}|, i.e., the number of elements in B_{i} that do not appear in the substring (B_{i+1}, …, B_{l}).

Consider the recursion tree generated by applying the function f_{k}^{n} to (n − k − 1, 0, k). This tree is a generalization of the one presented in Fig. 2 for the special case n = 7 and k = 3: node labels correspond to the binomials product and edge labels correspond to the value of the variable c discriminating recursive applications of function f_{k}^{n}.

Notice that, considering the edge labels in any leaf to root path of this tree, we obtain a vector (c_{1}, …, c_{n−k−2}) which represents the sequence of newly inserted numbers (from right to left), and so it coincides with the characteristic of some string in C_{k}^{n}. It is also true that if \overline{c} is the characteristic of a string in C_{k}^{n}, then a leaf to root path whose edge labels vector is \overline{c} must exist.

|C_{k}^{n}| can be obtained by summing cardinalities of disjoint sets of strings sharing the same characteristic. The size of any such set is given by the product of node labels following the corresponding leaf to root path in the recursion tree. By summing those products, we thus obtain |C_{k}^{n}|, i.e., the value computed by f_{k}^{n}(n − k − 1, 0, k).

4.1 Experimental Results

We implemented the recursive function to enumerate the labeled k-arch graphs on n nodes using the open source algebraic system PARI/GP (http://pari.math.u-bordeaux.fr/). The code performing the counting is given in Figure 3.

f(n,k,i,u,j)={
    local(s=0);
    if (i==1,
        binomial(n-u,j)*binomial(u,k-j),
        for (c=0, min(k,n-(i-1)-(u+j)),
            s+=f(n,k,i-1,u+j,c)
        );
        binomial(n-u,j)*binomial(u,k-j)*s
    )
}

Figure 3: Code implementing the recursive function f_{k}^{n}.

The size of the recursion tree is exponential in the order of (k + 1)^{n−k−2} so the value can only be computed if the difference between n and k is small. As done by Lamathe we report values of |A_{k}^{n}| for n ∈ [1, 10] and k ∈ [1, 7] in the following table:

\begin{matrix}k\n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 1 & 3 & 16 & 125 & 1296 & 16807 & 262144 & 4782969 & 100000000 \\ 2 & 0 & 1 & 1 & 6 & 100 & 3285 & 177471 & 14188888 & 1569185136 & 229087571625 \\ 3 & 0 & 0 & 1 & 1 & 10 & 380 & 34405 & 5919536 & 1709074584 & 764754595200 \\ 4 & 0 & 0 & 0 & 1 & 1 & 15 & 1085 & 216230 & 92550276 & 74358276300 \\ 5 & 0 & 0 & 0 & 0 & 1 & 1 & 21 & 2576 & 982926 & 898027452 \\ 6 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 28 & 5376 & 3568950 \\ 7 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 36 & 10200 \end{matrix}

The first row of this table gives exactly the well-known Cayley’s formula, as 1-arch graphs are trees. Apart from this row (reported as Sequence \underline{A000272}) no other row of the table is listed in the on-line Encyclopedia of Integer Sequences [7]. Moreover Sequences \underline{A098721}, \underline{A098722}, \underline{A098723}, and \underline{A098724} should be updated to reflect our correction of Lamathe’s results (rows 2, 3, 4 of above table respectively).

5 Conclusion and Open Problems

In this paper we have presented a recursive function that computes the number of labeled karch graphs of n nodes, for any given n and k. In order to obtain this function, we have used a code that maps labeled k-arch graphs to strings and we have derived the counting function by characterizing valid code strings. Moreover, we have proved the counting function for k-arch graphs provided by Lamathe to be incorrect by showing a counterexample.

It remains an open problem to find, provided that it exists, a closed-form solution for the recursive function computing |A_{k}^{n}|, when k > 1, perhaps exploiting generating functions. When k = 1, from Cayley’s formula, we have |A_{1}^{n}| = n^{n−2}. Furthermore, it would be interesting to investigate the case of rooted and unlabeled k-arch graphs.

Acknowledgments

We want to thank Prof. Rossella Petreschi for her support and her useful comments.

References

[1] A. Cayley, A theorem on trees, Quarterly J. Math. 23 (1889), 376–378.

[2] F. Harary and E. M. Palmer, On acyclic simplicial complexes, Mathematika 15 (1968), 115–122.

[3] C. Lamathe, The number of labelled k-arch graphs, J. Integer Sequences 7 (2004), Article 04.3.1.

[4] J. W. Moon, Various proofs of Cayley’s formula for counting trees, In F. Harary, ed., A Seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967, Chapter 11, pp. 70–78.

[5] H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Archiv der Mathematik und Physik 27 (1918), 142–144.

[6] C. Rényi and A. Rényi, The Prüfer code for k-trees, P. Erdős et al., editors, Combinatoral Theory and its Applications (Proc. Colloq. Balatonfured, 1969), North-Holland (1970), 945–971.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2007,

    http://www.research.att.com/∼njas/sequences.

[8] P. Todd, A k-tree generalization that characterizes consistency of dimensioned engineering drawings, SIAM J. Disc. Math. 2 (1989), 255–261.

2000 Mathematics Subject Classification: Primary 05A15, 05C30; Secondary 05A10. Keywords: k-arch graphs, trees, k-trees, coding, Prüfer code, Cayley’s formula.

(Concerned with sequences \underline{A000272}, \underline{A098721}, \underline{A098722}, \underline{A098723} and \underline{A098724}.)

Received November 3 2006; revised version received July 16 2007. Published in Journal of Integer Sequences, July 17 2007.

Return to Journal of Integer Sequences home page.