How to Count k-Paths

Allan Bickle Department of Mathematics Penn State Altoona 3000 Ivyside Park Altoona, PA 16601 USA

                        aub742@psu.edu

Abstract A k-tree is a graph that can be formed by starting with the complete graph K_{k} and iterating the operation of making a new vertex adjacent to all the vertices of a k-clique of the existing graph. For order n > k + 1, a k-path graph is a k-tree with exactly two vertices of degree k. We develop a formula for the number of unlabeled k-paths of order n. In particular, there is a bijection between these graphs and equivalence classes of strings of numbers from {1, 2, …, k} under a relation that treats them as equivalent when they can be made the same by permutation of their numbers and possible reversal of the string.

1 Introduction

In this paper, we seek to count the number of unlabeled k-paths of order n. This work builds on previous papers on maximal k-degenerate graphs with diameter 2 [7] and k-paths of k-trees [6].

Undefined notation and terminology will follow Bickle [5]. In particular, K_{n} is the complete graph with n vertices, and P_{n} is the path with n vertices. The complement of a graph G is denoted \overline{G}, and the join of two graphs G and H is denoted G + H. The neighborhood of a vertex v is denoted N(v).

Definition 1. A k-tree is a graph that can be formed by starting with K_{k} and iterating the operation of making a new vertex adjacent to all the vertices of a k-clique of the existing graph.

A k-leaf is a degree k vertex of a k-tree.

A k-path graph G is an alternating sequence of distinct k-cliques and k + 1-cliques e_{0}, t_{1}, e_{1}, t_{2}, …, t_{p}, e_{p}, starting and ending with a k-clique and such that t_{i} contains exactly two k-cliques e_{i−1} and e_{i}.

An interior k-caterpillar is a k-tree so that there is some k-path such that the k-leaves of the caterpillar are k-leaves of the path or are attached to interior k-cliques (the t_{i}’s) of the k-path.

A dominating vertex of a graph is a vertex adjacent to all other vertices.

Any k-path is a k-tree. An example of a 2-path is shown below.

Figure 1: An example of a 2-path.

Beineke and Pippert [4] introduced k-paths of k-trees, and Proskurowski [16] considered k-paths as graphs. Note that k-paths are also known as linear k-trees [1]. They are closely related to pathwidth [17]; in particular, they are the maximal graphs with proper pathwidth k. They are related to treewidth, zero forcing, and many related parameters [2], and are extremal interval graphs [9]. Note that 2-paths are the 2-trees with the most spanning trees [18] and they characterize the values of three parameters related to linear algebra [11]. Bickle [8] has a survey of k-trees, k-paths, and related graph classes.

There is a simple characterization of these graphs.

Theorem 2. [12] Let G be a k-tree with order n > k + 1. Then G is a k-path graph if and only if G has exactly two k-leaves.

The number of labeled k-paths of order n is \frac{n!}{2·k!}k^{n−k−2}. This was proved by Markenzon et al. [13] using a code for k-paths. Baste et al. [3] have a short proof.

We consider the number of unlabeled k-paths of order n. Eckhoff [9] studied interval graphs that have maximum size for a given clique number, and showed that these graphs are equivalent to interior k-caterpillars. Eckhoff (using ideas from Proskurowski [16]) showed that there is a bijection between interior k-caterpillars of order n and k-paths of order n + 2. Eckhoff used this to prove recurrences for the number of k-paths of order n that depend on smaller values of k and n, and found closed formulas for 2 ≤ k ≤ 4.

One approach to counting k-paths is to prove a bijection between them and strings of numbers (or codes) that satisfy certain conditions. One approach to this was taken by Pereira et al. [15], who defined a code based on the unique k + 1-coloring of a k-path. Thus the code uses integers from {1, 2, …, k + 1}. They define a recurrence by considering dominating vertices and symmetry.

We define a different code for k-paths and show that they correspond to equivalence classes of strings of numbers from {1, 2, …, k} under a relation that treats them as equivalent when they can be made the same by permutation of their numbers and possible reversal of the string. The problem of enumerating such strings was previously studied by Nester [14] using Polya enumeration. This produced a method for calculating small values of these sequences, but did not produce closed formulas for them.

2 Construction strings

To count k-paths, we need a way to describe their construction with a string of numbers. A k-path with vertices v_{1}, …, v_{n} can be constructed from K_{k+1} by successively adding k-leaves so that v_{1} is always a k-leaf, and each v_{i} with k + 1 < i < n is a k-leaf until v_{i+1} is added. We define a labeling of the k-path so that the two k-leaves are unlabeled, and every other vertex receives a label.

Label the k neighbors of v_{1} with {1, 2, …, k} (in any way). Each time a k-leaf v_{i+1} is added adjacent to (old) k-leaf v_{i}, label v_{i} with whatever number in {1, 2, …, k} is not already a label of a neighbor of v_{i+1}. Record each new label added (after the first k) in order.

Definition 3. A construction string of a k-path is the string of n − k − 2 numbers added after the first k using the algorithm above.

An example of constructing a 2-path is shown below. The construction string is recorded below each iteration.

\begin{matrix}u \\ 1 \\ 2 \\ v \\ → \\ 2 \\ u \\ 1 \\ 2 \\ 2 \\ → \\ 21 \\ u \\ 1 \\ 2 \\ 1 \\ 2 \\ → \\ 211 \\ u \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \end{matrix}

Figure 2: Finding the construction string of a 2-path.

Definition 4. Let a k-string be an ordered list of numbers from [k]. The reverse-permute (RP) relation treats k-strings as equivalent when they can be made the same by permutation of their numbers and possible reversal of the string.

For example, the 2-strings 1112, 2221, 2111, and 1222 are equivalent under the RP relation. There are six equivalence classes of 2-strings of length 4, with representatives 1111, 1112, 1121, 1122, 1212, and 1221.

Lemma 5. The number of unlabeled k-paths of order n ≥ k + 3 equals the number of equivalence classes of k-strings of length n − k − 2 under the RP relation.

Proof. Consider constructing a k-path of order n using the algorithm described above, producing a construction string of length n − k − 2. Since the labeling of the first k labeled vertices is arbitrary, any permutation of this string can be produced by the k-path. It can also be constructed starting from the other 2-leaf. Constructing from the other k-leaf reverses the string, since each number in the string corresponds to a copy of P_{4} + K_{k−1} in the k-path. Thus each k-path produces an equivalence class of k-strings of length n − k − 2 under the RP relation.

Alternatively, we can start with a construction string and use it to construct a k-path. Each number specifies a unique way to add each new vertex, so each construction string produces a single k-path. Thus we have a bijection between k-paths of order n ≥ k + 3 and equivalence classes of k-strings of length n − k − 2 under the RP relation.

3 Counting k-strings and k-paths

Thus the problem of counting k-paths reduces to the problem of counting equivalence classes of k-strings under the RP relation. These equivalence classes do not all have equal size.

Definition 6. A k-string has reversal symmetry if it can have its numbers permuted to produce the reverse of the string.

For example, of the 2-strings of length 4, 1111, 1122, 1212, and 1221 have reversal symmetry and 1112 and 1121 don’t. To count k-strings, we must separate them into those with reversal symmetry and those without.

If a string has reversal symmetry, permuting its numbers to reverse the string twice must produce the original string. A permutation that is self-inverse is called an involution. An involution must have cycles of length one or two only. We will need the sequence s(n) of involution numbers. This sequence (\underline{A000085} in OEIS, the On-Line Encyclopedia of Integer Sequences) begins 1, 2, 4, 10, 26, 76, 232, 764, 2620, … The following formula is easily demonstrated:

s(n) = ∑_{k=0}^{⌊n/2⌋} \frac{n!}{2^{k}(n − 2k)!k!}.

Theorem 7. Let a(1, x) = a′(1, x) = 1, and

a(i, x) = s(i) · i^{⌈ \frac{x}{2} ⌉} − ∑_{j=1}^{i−1} \binom{i}{j}a(j, x)s(i − j)

a′(i, x) = s(i − 1) · i^{⌈ \frac{x}{2} ⌉} − ∑_{j=1}^{i−1} \binom{i}{j}a′(j, x)s(i − j)

b(i, x) = ∑_{j=1}^{i}(−1)^{i−j}\binom{i}{j}j^{x}.

\begin{matrix}i & a(i, x) \\ 1 & 1 \\ 2 & 2 · 2^{r} − 2 \\ 3 & 4 · 3^{r} − 6 · 2^{r} \\ 4 & 10 · 4^{r} − 16 · 3^{r} + 8 \\ 5 & 26 · 5^{r} − 50 · 4^{r} + 40 · 2^{r} − 10 \\ 6 & 76 · 6^{r} − 156 · 5^{r} + 160 · 3^{r} − 60 · 2^{r} − 36 \\ 7 & 232 · 7^{r} − 532 · 6^{r} + 700 · 4^{r} − 280 · 3^{r} − 252 · 2^{r} + 112 \end{matrix}

Table 1: Formulas for a(i, x), r = ⌈\frac{x}{2}⌉

\begin{matrix}i & a′(i, x) \\ 1 & 1 \\ 2 & 2^{r} − 2 \\ 3 & 2 · 3^{r} − 3 · 2^{r} \\ 4 & 4 · 4^{r} − 8 · 3^{r} + 8 \\ 5 & 10 · 5^{r} − 20 · 4^{r} + 20 · 2^{r} − 10 \\ 6 & 26 · 6^{r} − 60 · 5^{r} + 80 · 3^{r} − 30 · 2^{r} − 36 \\ 7 & 76 · 7^{r} − 182 · 6^{r} + 280 · 4^{r} − 140 · 3^{r} − 126 · 2^{r} + 112 \end{matrix}

Table 2: Formulas for a′(i, x), r = ⌈\frac{x}{2}⌉

The number of equivalence classes of k-strings of length x under the RP relation is

\begin{cases}∑_{i=1}^{k} \frac{b(i,x)+a(i,x)}{2·i!}, & x even; \\ ∑_{i=1}^{k} \frac{b(i,x)+a′(i,x)}{2·i!}, & x odd. \end{cases}

Proof. We split the strings into those that have reversal symmetry and those that do not. Let the number of strings of length x using exactly i numbers that have reversal symmetry be a(i, x) for x even, and a′(i, x) for x odd. Certainly a(1, x) = a′(1, x) = 1. To find how many strings with reversal symmetry use exactly i numbers, we find how many use at most i numbers and subtract out those that use fewer than i.

Assume x is even. There are ⌈\frac{x}{2}⌉ number in the first half of the string. There are i choices for each position, so there are i^{⌈ \frac{x}{2} ⌉} choices for the first half of the string. Since the string has reversal symmetry, an involution of the first half must produce the second half, which can happen in s(i) ways. Thus there are s(i) · i^{⌈ \frac{x}{2} ⌉} strings with reversal symmetry that use at most i numbers. There are \binom{i}{j} choices of j numbers that appear in a string using exactly j of i numbers. The number of involutions of the remaining j − i numbers is s(j − i), so each string using exactly j of i numbers will appear \binom{i}{j}a(j, x)s(i−j) times in the s(i)·i^{⌈ \frac{x}{2} ⌉} strings. We subtract these out for each j between 1 and i − 1, producing the recursive formula

a(i, x) = s(i) · i^{⌈ \frac{x}{2} ⌉} − ∑_{j=1}^{i−1} \binom{i}{j}a(j, x)s(i − j).

Now let x be odd. As before, to find how many strings with reversal symmetry use exactly i numbers, we find how many use at most i numbers and subtract out those that use fewer than i. A permutation that reverses the string must fix the middle element, so s(i − 1) involutions produce the second half of the string. Thus there are s(i − 1) · i^{⌈ \frac{x}{2} ⌉} strings with reversal symmetry that use at most i numbers. As before, we have the recursive formula

a′(i, x) = s(i − 1) · i^{⌈ \frac{x}{2} ⌉} − ∑_{j=1}^{i−1} \binom{i}{j}a′(j, x)s(i − j).

Let the total number of strings of length x using exactly i specified numbers of k numbers be b(i, x). Equivalently, this is the number of onto functions from {1, 2, …, k} to {1, 2, …, i}. There is a well-known formula for this, proved using inclusion-exclusion ([19, p. 561]), showing b(i, x) = ∑_{j=1}^{i}(−1)^{i−j}\binom{i}{j}j^{x}. Thus the number of strings without reversal symmetry is b(i, x) − a(i, x) or b(i, x) − a′(i, x), depending on parity.

A k-string with reversal symmetry using exactly i of k numbers is part of an equivalence class of i! strings equivalent under the RP relation. A k-string without reversal symmetry using exactly i of k numbers is part of an equivalence class of 2 · i! strings equivalent under the RP relation. Thus the number of equivalence classes of k-strings of even length x under the RP relation is

∑_{i=1}^{k} \frac{a(i, x)}{i!} + ∑_{i=1}^{k} \frac{b(i, x) − a(i, x)}{2 · i!} = ∑_{i=1}^{k} \frac{b(i, x) + a(i, x)}{2 · i!}.

The number of equivalence classes of k-strings of odd length x under the RP relation is

∑_{i=1}^{k} \frac{a′(i, x)}{i!} + ∑_{i=1}^{k} \frac{b(i, x) − a′(i, x)}{2 · i!} = ∑_{i=1}^{k} \frac{b(i, x) + a′(i, x)}{2 · i!}.

Corollary 8. The number of unlabeled k-paths of order n ≥ k + 3 is

\begin{cases}∑_{i=1}^{k} \frac{b(i,n−k−2)+a(i,n−k−2)}{2·i!}, & n − k even; \\ ∑_{i=1}^{k} \frac{b(i,n−k−2)+a′(i,n−k−2)}{2·i!}, & n − k odd. \end{cases}

For small values of k, here are simplified formulas from Theorem 7 for the number N(k, x) of k-paths of order x = n − k − 2.

N(2, x) = \begin{cases}\frac{1}{4}2^{x} + \frac{1}{2}2^{⌈^{\frac{x}{2}}⌉}, & n even; \\ \frac{1}{4}2^{x} + \frac{1}{4}2^{⌈^{\frac{x}{2}}⌉}, & n odd; \end{cases} = 2^{n−6} + 2^{⌊^{\frac{n−6}{2}}⌋}.

N(3, x) = \begin{cases}\frac{1}{12}3^{x} + \frac{1}{6}3^{⌈^{\frac{x}{2}}⌉} + \frac{1}{4}, & n even; \\ \frac{1}{12}3^{x} + \frac{1}{3}3^{⌈^{\frac{x}{2}}⌉} + \frac{1}{4}, & n odd. \end{cases}

N(4, x) = \begin{cases}\frac{1}{48}4^{x} + \frac{5}{24}4^{⌈^{\frac{x}{2}}⌉} + \frac{1}{8}2^{x} + \frac{1}{3}, & n even; \\ \frac{1}{48}4^{x} + \frac{1}{12}4^{⌈^{\frac{x}{2}}⌉} + \frac{1}{8}2^{x} + \frac{1}{3}, & n odd. \end{cases}

N(5, x) = \begin{cases}\frac{5^{x}}{240} + \frac{3^{x}}{24} + \frac{2^{x}}{12} + \frac{5^{⌈^{\frac{x}{2}} ⌉}}{24} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{12} + \frac{5}{16}, & n even; \\ \frac{5^{x}}{240} + \frac{3^{x}}{24} + \frac{2^{x}}{12} + \frac{13·5^{⌈^{\frac{x}{2}} ⌉}}{120} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{6} + \frac{5}{16}, & n odd. \end{cases}

N(6, x) = \begin{cases}\frac{6^{x}}{1440} + \frac{4^{x}}{96} + \frac{3^{x}}{36} + \frac{3·2^{x}}{32} + \frac{19·6^{⌈^{\frac{x}{2}} ⌉}}{360} + \frac{3^{⌈^{\frac{x}{2}} ⌉}}{9} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{8} + \frac{17}{60}, & n even; \\ \frac{6^{x}}{1440} + \frac{4^{x}}{96} + \frac{3^{x}}{36} + \frac{3·2^{x}}{32} + \frac{13·6^{⌈^{\frac{x}{2}} ⌉}}{720} + \frac{3^{⌈^{\frac{x}{2}} ⌉}}{18} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{16} + \frac{17}{60}, & n odd. \end{cases}

N(7, x) = \begin{cases}\frac{7^{x}}{10080} + \frac{5^{x}}{480} + \frac{4^{x}}{144} + \frac{3^{x}}{32} + \frac{11·2^{x}}{120} + \frac{19·7^{⌈^{\frac{x}{2}} ⌉}}{2520} + \frac{4^{⌈^{\frac{x}{2}} ⌉}}{36} + \frac{3^{⌈^{\frac{x}{2}} ⌉}}{24} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{20} + \frac{85}{288}, & n even; \\ \frac{7^{x}}{10080} + \frac{5^{x}}{480} + \frac{4^{x}}{144} + \frac{3^{x}}{32} + \frac{11·2^{x}}{120} + \frac{29·7^{⌈^{\frac{x}{2}} ⌉}}{1260} + \frac{5·4^{⌈^{\frac{x}{2}} ⌉}}{72} + \frac{3^{⌈^{\frac{x}{2}} ⌉}}{12} + \frac{2^{⌈^{\frac{x}{2}} ⌉}}{10} + \frac{85}{288}, & n odd. \end{cases}

In general, the dominant term is always \frac{1}{2·k!}k^{n−k−2}, and for k ≥ 5, the next largest term is \frac{1}{4·(k−2)!}(k − 2)^{n−k−2}. The following table lists the beginnings of the sequences, and their OEIS numbers.

k  Sequence (n ≥ k + 3)  OEIS
2  1, 2, 3, 6, 10, 20, 36, 72, 136, 272, …  \underline{A005418}
3  1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, …  \underline{A001998}
4 1, 2, 4, 11, 31, 107, 379, 1451, 5611, 22187, … \underline{A056323}
5 1, 2, 4, 11, 32, 116, 455, 1993, 9134, 43580, … \underline{A056324}
6 1, 2, 4, 11, 32, 117, 467, 2135, 10480, 55091, … \underline{A056325}
7 1, 2, 4, 11, 32, 117, 468, 2151, 10722, 58071, … \underline{A345207}

Table 3: Sequences counting k-paths

All k-paths with order k + 3 ≤ n ≤ 2k + 1 have diameter 2, and so have a dominating vertex. If there are N k-paths with order 2k + 2, then there are N k + t-paths with order 2k + 2 + t, since they have at least t dominating vertices. Thus the sequences in the table above approach a limiting sequence of 1, 2, 4, 11, 32, 117, 468, 2152, 10743, … which is \underline{A103293}.

The formula for the number of 2-paths of order n ≥ 5 simplifies to 2^{n−6} + 2^{⌊ \frac{n−6}{2} ⌋}. Harary and Schwenk [10] showed that there are 2^{n−4} + 2^{⌊ \frac{n−4}{2} ⌋} caterpillars of order n ≥ 3 using a similar proof technique. Eckhoff [9] and Pereira et al. [15] both showed that the number of 2-paths of order n equals the number of caterpillars of order n − 2 using a natural bijection.

References

[1] A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martinez-Rivera, S. O, S. Song, and J. Williford, On the Wiener index, distance cospectrality and transmission regular graphs, Discrete Appl. Math. 230 (2017), 1–10.

[2] F. Barioli, W. Barrett, S. Fallat, H. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013), 146–177.

[3] J. Baste, M. Noy, and I. Valls, On the number of labeled graphs of bounded treewidth, European J. Combin. 71 (2018), 12–21.

[4] L. W. Beineke and R. E. Pippert, Properties and characterizations of k-trees, Mathematika 18 (1971), 141–151.

[5] A. Bickle, Fundamentals of Graph Theory, American Mathematical Society, 2020.

[6] A. Bickle, k-paths of k-trees, Congr. Numer., to appear.

[7] A. Bickle, Maximal k-degenerate graphs with diameter 2, Int. J. Math. Comb. 2 (2021), 67–78.

[8] A. Bickle, A survey of maximal k-degenerate graphs and k-trees, 2021. Submitted.

[9] J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 (1993), 117–127.

[10] F. Harary and A. Schwenk, The number of caterpillars, Discrete Math. 6 (1973), 359– 365.

[11] L. Hogben and H. van der Holst, Forbidden minors for the class of graphs g with ξ(g) ≤ 2, Linear Algebra Appl. 423 (2007), 42–52.

[12] L. Markenzon, C. M. Justel, and N. Paciornik, Subclasses of k-trees: characterization and recognition, Discrete Appl. Math. 154 (2006), 818–825.

[13] L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216–3222.

[14] M. R. Nester, Mathematical investigations of some plant interaction designs. PhD Thesis, University of Queensland, Brisbane, Australia (1999).

[15] P. Pereira, A. Garcia, and L. Markenzon, Generating and counting unlabeled k-path graphs, Discrete Appl. Math., 164 (2014), 297–303.

[16] A. Proskurowski, Separating subgraphs in k-trees: cables and caterpillars, Discrete Math. 49 (1984), 275–285.

[17] A. Proskurowski and J. Telle, Classes of graphs with restricted interval models, Discrete Math. Theoret. Comput. Sci. 3 (1999), 167–176.

[18] P. Renjith, N. Sadagopan, and D. B. West, Spanning trees in 2-trees, Arxiv preprint,

    2016. Available at https://arxiv.org/abs/1607.05817.

[19] K. Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill, 2011.

2020 Mathematics Subject Classification: Primary 05C30. Keywords: k-path, k-tree, recurrence, involution, caterpillar.

(Concerned with sequences \underline{A000085}, \underline{A001998}, \underline{A005418}, \underline{A056323}, \underline{A056324}, \underline{A056325}, \underline{A103293}, and \underline{A345207}.)

Received June 11 2021; revised versions received June 17 2021; March 28 2022; April 2 2022. Published in Journal of Integer Sequences, June 21 2022.

Return to Journal of Integer Sequences home page.