Integer sequences from ๐‘˜ -iterated line digraphs D. Zรกvackรก1 , C. Dalfรณ2 and M. A. Fiol3 1 Comenius University, Faculty of Mathematics, Physics and Informatics, Department of Applied Informatics, Bratislava, Slovakia 2 Dept. de Matemร tica, Universitat de Lleida, Igualada (Barcelona), Catalonia 3 Dept. de Matemร tiques, Universitat Politรจcnica de Catalunya, Barcelona Graduate School of Mathematics, and Institut de Matemร tiques de la UPC-BarcelonaTech (IMTech), Barcelona, Catalonia Abstract In this paper, we focus on integer sequences corresponding to the number of vertices in ๐‘˜-iterated line digraphs. We begin by introducing the core concepts related to digraphs. Then, we describe a method, proposed by Dalfรณ and Fiol, for calculating the order of ๐‘˜-iterated line digraphs. We explore various families of digraphs, such as De Bruijn, Kautz, Cyclic Kautz, and Square-free digraphs. To generate integer sequences representing the number of vertices in ๐‘˜-iterated line digraphs, we implement an algorithm that constructs induced subdigraphs by not allowing vertices containing forbidden subwords. The results include comparisons of the obtained integer sequences with those in the OEIS database and identification of new integer sequences. Our algorithm is implemented in the computational system GAP. Keywords digraph, line digraph, integer sequence, words 1. Introduction integer sequences that we obtained and compare them to those in the OEIS database. We list new integer sequences This article primarily focuses on digraphs (directed not found there. graphs), which consist of vertices connected by directed edges. These directed edges indicate a one-way rela- tionship between the vertices. By iteratively applying 2. Preliminaries a specific method to obtain new digraphs, we can cre- ate a sequence of digraphs and, consequently, an integer We introduce fundamental concepts related to digraphs, sequence representing the numbers of vertices in these which are utilized throughout this paper. A digraph ๐บ = digraphs. In our work, this method involves creating (๐‘‰, ๐ธ) consists of a (finite) set of vertices ๐‘‰ = ๐‘‰ (๐บ) and line digraphs and forming sequences of ๐‘˜-iterated line a multiset of arcs (directed edges) ๐ธ = ๐ธ(๐บ) between digraphs. vertices of ๐บ. An arc is an ordered pair of vertices (๐‘ข, ๐‘ฃ), Section 2 covers the preliminary concepts related to where ๐‘ข is adjacent to vertex ๐‘ฃ and vertex ๐‘ฃ is adjacent digraphs. We define the essential terms, such as line from vertex ๐‘ข. We allow loops and multiple arcs in di- digraph and its iterations, regular partitions, and quo- graphs. A loop is an arc from vertex ๐‘ฃ to itself, that is, tient digraphs. We also describe a method introduced an arc (๐‘ฃ, ๐‘ฃ). Multiple arcs are present in digraph ๐บ if by Dalfรณ and Fiol in [1] for computing the orders of ๐‘˜- there is more than one arc (๐‘ข, ๐‘ฃ) in ๐ธ(๐บ). The in-degree iterated line digraphs. In Section 3, we present definitions of a vertex ๐‘ฃ in ๐บ, denoted ๐›ฟ โˆ’ (๐‘ฃ), is the number of arcs and examples of some families of digraphs, including De in ๐บ adjacent to vertex ๐‘ฃ. The out-degree of a vertex ๐‘ฃ Bruijn digraphs, Kautz digraphs, Cyclic Kautz digraphs, in ๐บ, denoted ๐›ฟ + (๐‘ฃ), is the number of arcs in ๐บ adja- and Square-free digraphs, whose vertices are represented cent from vertex ๐‘ฃ. We say a digraph ๐บ is ๐›ฟ-regular if by words over some alphabet. Section 4 discusses the ๐›ฟ โˆ’ (๐‘ฃ) = ๐›ฟ + (๐‘ฃ) = ๐›ฟ for all ๐‘ฃ โˆˆ ๐‘‰ (๐บ). The line digraph main algorithm for obtaining integer sequences of the ๐ฟ(๐บ) of a digraph ๐บ is a digraph in which each vertex numbers of vertices of ๐‘˜-iterated line digraphs. This al- represents an arc of ๐บ. The vertex set of ๐ฟ(๐บ) is defined gorithm constructs an induced subdigraphs by removing as ๐‘‰ (๐ฟ(๐บ)) = {๐‘ข๐‘ฃ : (๐‘ข, ๐‘ฃ) โˆˆ ๐ธ(๐บ)}. Two vertices ๐‘ข๐‘ฃ vertices (containing forbidden subwords) from a digraph and ๐‘ค๐‘ง of ๐ฟ(๐บ) are adjacent if and only if ๐‘ฃ = ๐‘ค, mean- of a given family. In Section 5, we present the various ing that the arc (๐‘ข, ๐‘ฃ) in ๐บ is adjacent to arc (๐‘ค, ๐‘ง) in ๐บ. The ๐‘˜-iterated line digraph ๐ฟ๐‘˜ (๐บ) is recursively defined as follows: ๐ฟ0 (๐บ) = ๐บ and ๐ฟ๐‘˜ (๐บ) = ๐ฟ(๐ฟ๐‘˜โˆ’1 (๐บ)) for ITATโ€™24: Computational Aspects of Large-Scale Problems in Discrete Mathematics, September 20โ€“24, 2024, Drienica, Slovakia ๐‘˜ โ‰ฅ 0. A regular partition of ๐‘‰ (๐บ) is a partition of the * Corresponding author. vertices into ๐‘š subsets ๐‘‰1 , ๐‘‰2 , . . . , ๐‘‰๐‘š such that every $ dominika.mihalova@fmph.uniba.sk (D. Zรกvackรก); vertex ๐‘ฃ โˆˆ ๐‘‰๐‘– is adjacent to the same number of vertices cristina.dalfo@udl.cat (C. Dalfรณ); miguel.angel.fiol@upc.edu in ๐‘‰๐‘— , where ๐‘– and ๐‘— belong to {1, 2, . . . , ๐‘š}. Given a (M. A. Fiol) ยฉ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License digraph ๐บ and and one of its regular partition of vertex CEUR Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 set {๐‘‰1 , ๐‘‰2 , . . . , ๐‘‰๐‘š }, a quotient matrix โ„ฌ is an ๐‘š ร— ๐‘š CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings matrix, where โ„ฌ๐‘–๐‘— = ๐‘๐‘–๐‘— if there are ๐‘๐‘–๐‘— arcs from parti- [2] apply the method by [1] to determine the number of tions ๐‘‰๐‘– to ๐‘‰๐‘— , otherwise โ„ฌ๐‘–๐‘— = 0. A quotient digraph of words of length โ„“ over a given alphabet in some digraphs. digraph ๐บ, denoted ๐œ‹(๐บ), has its adjacency matrix equal Their approach involves constructing a digraph ๐บ that to the quotient matrix of ๐บ. represents the connections between words of length โ„“ We focus on integer sequences of the orders of the (excluding specific subwords) over the alphabet. By ap- ๐‘˜-iterated line digraphs. Dalfรณ and Fiol [1] introduced a plying Theorem 1 to such digraphs, they determine the method to compute the order of ๐‘˜-iterated line digraph number of valid words. The resulting number of words ๐ฟ๐‘˜ (๐บ) of digraph ๐บ. They explained that each vertex in a of length โ„“ + ๐‘˜ corresponds to the number of vertices ๐‘˜-iterated line digraph is a directed walk ๐‘ฃ0 , ๐‘ฃ1 , . . . ๐‘ฃ๐‘˜ of ๐‘›๐‘˜ in the ๐‘˜-iterated line digraph of ๐บ, where ๐บ is the length ๐‘˜ in ๐บ, where (๐‘ฃ๐‘–โˆ’1 , ๐‘ฃ๐‘– ) โˆˆ ๐ธ(๐บ) for ๐‘– = 1, . . . , ๐‘˜. digraph with vertices represented by words of length โ„“. Taking the ๐‘˜ power of the adjacency matrix ๐’œ๐บ of ๐บ, the We discuss the problem in the following sections. ๐‘ข๐‘ฃ-entry in ๐’œ๐‘˜๐บ corresponds to the number of ๐‘˜-walks from vertex ๐‘ข to vertex ๐‘ฃ in ๐บ. Consequently, the number of vertices ๐‘›๐‘˜ in ๐ฟ๐‘˜ (๐บ) is: 3. Some families of digraphs ๐‘›๐‘˜ = ๐‘—๐’œ๐‘˜๐บ ๐‘— ๐‘‡ Part of our research is to develop an efficient method for computing the number of words of length โ„“ over an where ๐‘— = (1, . . . , 1). In the case where ๐บ is a ๐›ฟ-regular alphabet of ๐‘‘ symbols, where words do not contain any of order ๐‘›, the ๐ฟ๐‘˜ (๐บ) is also a ๐›ฟ-regular digraph, and subword from a given set ๐’ฎ. To simulate this problem the computation of its order can be simplified to: on digraphs, we decided to choose families of digraphs whose vertices are represented by words over some al- ๐‘›๐‘˜ = ๐›ฟ ๐‘˜ ๐‘› phabet. Each family has its specific restrictions about the words, represented by vertices and connections (arcs) However, if ๐บ is not a ๐›ฟ-regular digraph, the complexity between them. We swiftly introduce four known families of computing the order of ๐ฟ๐‘˜ (๐บ) depends completely on of digraphs and show some examples. the dimension of ๐’œ๐บ , that is, the number of vertices in ๐บ. The De Bruijn digraph ๐ต(๐‘‘, โ„“) has vertices labeled by Dalfรณ and Fiol [1] introduced a method to compute ๐‘›๐‘˜ of all possible words ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ with ๐‘Ž๐‘– โˆˆ {0, 1, . . . , ๐‘‘ โˆ’ ๐ฟ๐‘˜ (๐บ) as shown in Theorem 1. They start by obtaining 1}. There is an arc from vertex ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ to vertex a quotient matrix โ„ฌ based on a regular partition of the ๐‘Ž2 . . . ๐‘Žโ„“ ๐‘Žโ„“+1 . An example of the De Bruijn digraph is vertex set of ๐บ. The size of โ„ฌ is the same or smaller than shown in Figure 1. that of ๐’œ๐บ based on the partition of vertices. The quo- The Kautz digraph ๐พ(๐‘‘, โ„“) has vertices labeled by all tient matrix is used to compute the initial values ๐‘›๐‘˜ for possible words ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ with ๐‘Ž๐‘– โˆˆ {0, 1, . . . , ๐‘‘ โˆ’ 1}, the recurrence equation depending on the minimal poly- where ๐‘Ž๐‘– ฬธ= ๐‘Ž๐‘–+1 for ๐‘– = 1, . . . , โ„“ โˆ’ 1.There is an arc nomial of the quotient matrix. The subsequent values of from vertex ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ to vertex ๐‘Ž2 . . . ๐‘Žโ„“ ๐‘Žโ„“+1 , when- ๐‘›๐‘˜ are determined by the recurrence equation. ever ๐‘Žโ„“ ฬธ= ๐‘Žโ„“+1 . An example of a Kautz digraph is shown Theorem 1 ([1]). Let ๐บ = (๐‘‰, ๐ธ) be a digraph on ๐‘› ver- in Figure 2. tices, and consider a regular partition ๐œ‹ = (๐‘‰1 , . . . , ๐‘‰๐‘š ) with quotient matrix โ„ฌ. Let ๐‘š(๐‘ฅ) = ๐‘ฅ๐‘Ÿ โˆ’ ๐›ผ๐‘Ÿโˆ’1 ๐‘ฅ๐‘Ÿโˆ’1 โˆ’ ยท ยท ยท โˆ’ ๐›ผ0 be the minimal polynomial of โ„ฌ. Then, the num- ber of vertices ๐‘›๐‘˜ of the ๐‘˜-iterated line digraph ๐ฟ๐‘˜ (๐บ) satisfies the recurrence ๐‘›๐‘˜ = ๐›ผ๐‘Ÿโˆ’1 ๐‘›๐‘˜โˆ’1 + ยท ยท ยท + ๐›ผ0 ๐‘›๐‘˜โˆ’๐‘Ÿ , for ๐‘˜ = ๐‘Ÿ, ๐‘Ÿ + 1, . . . initialized with the values ๐‘›๐‘˜ , for ๐‘˜ = 0, 1, . . . , ๐‘Ÿ โˆ’ 1, Figure 1: ๐ต(2, 3) on the left and one of its quotient digraphs given by on the right. ๐‘š โˆ‘๏ธ ๐‘š โˆ‘๏ธ ๐‘›๐‘˜ = |๐‘‰๐‘– | (โ„ฌ๐‘˜ )๐‘–๐‘— = ๐‘ โ„ฌ๐‘˜ ๐‘— ๐‘‡ , The Cyclic Kautz digraph ๐ถ๐พ(๐‘‘, โ„“) was introduced ๐‘–=1 ๐‘—=1 by Bรถhmovรก, Dalfรณ, and Huemer in [3]. The Cyclic Kautz digraph has vertices labeled by all possible words where ๐‘  = (|๐‘‰1 |, . . . , |๐‘‰๐‘š |) and ๐‘— = (1, . . . , 1). ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ with ๐‘Ž๐‘– โˆˆ {0, 1, . . . , ๐‘‘โˆ’1}, where ๐‘Ž๐‘– ฬธ= ๐‘Ž๐‘–+1 The recurrence equation in Theorem 1 is an efficient for ๐‘– = 1, . . . , โ„“ โˆ’ 1, and ๐‘Ž1 ฬธ= ๐‘Žโ„“ . There is an arc way of calculating the order of a ๐‘˜-iterated line digraph from vertex ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ to vertex ๐‘Ž2 . . . ๐‘Žโ„“ ๐‘Žโ„“+1 , when- for digraphs that are not ๐›ฟ-regular. Moreover, it allows us ever ๐‘Žโ„“+1 ฬธ= ๐‘Žโ„“ and ๐‘Žโ„“+1 ฬธ= ๐‘Ž2 . An example of a Cyclic to solve other problems more effectively. The authors in Kautz digraph is shown in Figure 3. suggested by the authors in [2]. We programmed the algorithm in the system for computational discrete alge- bra - GAP [4]. It is a widely used, free, and open-source system with its own programming language and various importable packages containing numerous functions. It is particularly effective for computational problems involv- ing groups, graphs, and other combinatorial structures. For the implementation of our algorithm, we imported the packages Digraphs and GRAPE. The Digraphs pack- Figure 2: ๐พ(3, 3) on the left and one of its quotient digraphs age [5] was implemented to create, store, and compute on the right. various properties of digraphs. The digraph structure can be a mutable or immutable structure. The GRAPE package [6] is automatically imported with the Digraphs package. The package is intended for the construction, computation, and analysis of graphs in relation to groups. The algorithms were implemented in GAP with version 4.12.2. The main goal of our computational method is to de- termine all possible integer sequences of values of ๐‘›๐‘˜ up to a given ๐‘˜, where ๐‘›๐‘˜ represents the number of words of length โ„“ + ๐‘˜ over an alphabet of size ๐‘‘ avoiding all possi- ble combinations of subwords (forbidden subwords) from a set of subwords ๐’ฎ. Initially, we employed the method Figure 3: ๐ถ๐พ(3, 4) on the left with one of its quotient di- described in [2] in a for-cycle and evaluated all possi- graphs on the right. ble combinations of forbidden subwords. However, this method was computationally very challenging as the al- gorithm required significant processing time to evaluate all the combinations, and it frequently produced numer- ous identical digraphs. To address these challenges, we opted to examine all possible induced subdigraphs in- stead. This alternative approach allows us to efficiently generate all integer sequences and determine the set of forbidden subwords based on forbidden and allowed ver- tices. Algorithm 1 Pseudocode: obtaining integer sequences for all subdigraphs of a given digraph ๐บ Figure 4: ๐‘†๐น (3, 4) on the left with one of its quotient di- SequencesForAllSubdigraphs(๐บ, ๐‘˜๐‘š๐‘Ž๐‘ฅ ) graphs on the right. for all combination of ๐‘‰ (๐บ) do forbiddenSubwords = Difference(vertices of ๐บ, com- bination) subdigraph = InducedSubdigraph(๐บ, combination) The Square-free digraph ๐‘†๐น (๐‘‘, โ„“) has vertices la- sequence = LGSequence(subdigraph, ๐‘˜๐‘š๐‘Ž๐‘ฅ ) beled by all possible words ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ with ๐‘Ž๐‘– โˆˆ print (forbiddenSubwords, sequence, subdigraph) {0, 1, . . . , ๐‘‘ โˆ’ 1}, that does not contain an adjacent rep- end for etition of any subword of length at most 2. There is an end function arc from ๐‘Ž1 ๐‘Ž2 . . . ๐‘Žโ„“ to ๐‘Ž2 . . . ๐‘Žโ„“ ๐‘Žโ„“+1 when ๐‘Žโ„“+1 ฬธ= ๐‘Žโ„“ and, if ๐‘Žโ„“โˆ’2 = ๐‘Žโ„“ , then ๐‘Žโ„“+1 ฬธ= ๐‘Žโ„“โˆ’1 . An example of a Square-free digraph is shown in Figure 4. Our Algorithm 1 takes two input parameters: a digraph structure (๐บ) and ๐‘˜๐‘š๐‘Ž๐‘ฅ . The digraph is cho- sen from one of the families of digraphs discussed in Sec- 4. Algorithm tion 3, with each family imposing its own specific restric- tions on the possible words and the connections between To compute the number of vertices in a ๐‘˜-iterated line them. The vertices of digraph represent words of length โ„“ digraph of digraph ๐บ, we decided to implement an al- over an alphabet of ๐‘‘ symbols. The parameter ๐‘˜๐‘š๐‘Ž๐‘ฅ spec- gorithm based mostly on Theorem 1 and the method ifies the maximum value of ๐‘˜. The algorithm begins with a for-cycle that iterates over all combinations of vertices Table 1 ๐‘‰ (๐บ), as this method has been demonstrated to be more Forbidden subwords in the ๐‘†๐น (3, 4) digraphs with 16 vertices effective. The set of forbidden subwords is obtained and and the integer sequence of the numbers of vertices ๐‘›๐‘˜ of ๐‘˜- stored in the parameter forbiddenSubwords. We con- iterated line digraphs. struct an induced subdigraph of ๐บ based on the current Forbidden subwords Sequence combination of ๐‘‰ (๐บ). The subdigraph structure and 1201, 2102 16, 22, 28, 36, 46, 58, 72, 90, . . . the required ๐‘˜๐‘š๐‘Ž๐‘ฅ parameter are subsequently passed 2012, 2102 16, 22, 28, 38, 52, 70, 92, 124, . . . to the LGSequence() function. The function returns 0120, 2120 16, 23, 31, 43, 60, 82, 112, 155, . . . the integer sequence of ๐‘›๐‘˜ for ๐‘˜ = 0, . . . , ๐‘˜๐‘š๐‘Ž๐‘ฅ , where 0120, 0212 16, 23, 31, 43, 60, 83, 114, 157, . . . 2101, 2120 16, 23, 31, 43, 61, 85, 118, 165, . . . ๐‘›๐‘˜ represents the order of a ๐‘˜-iterated line digraph of 1021, 1210 16, 23, 32, 45, 63, 87, 121, 170, . . . subdigraph. In the context of the previously mentioned 0102, 1201 16, 23, 32, 46, 67, 97, 139, 200, . . . problem concerning the number of words of length โ„“ over 0210, 1021 16, 23, 33, 48, 68, 96, 137, 196, . . . some alphabet, the value of ๐‘›๐‘˜ corresponds to the num- 1202, 2010 16, 24, 34, 48, 68, 96, 136, 194, . . . ber of words of length โ„“ + ๐‘˜ over alphabet of ๐‘‘ symbols 0102, 0121 16, 24, 34, 48, 69, 97, 137, 196, . . . avoiding subwords in forbiddenSubwords. At the end 1020, 1202 16, 24, 34, 48, 70, 100, 142, 206, . . . of the for-cycle, the algorithm prints a triple consisting of 0201, 1202 16, 24, 34, 49, 70, 100, 144, 207, . . . 1201, 2010 16, 24, 34, 49, 71, 102, 146, 211, . . . an example of forbidden subwords, the integer sequence 0121, 1020 16, 24, 34, 50, 74, 108, 158, 232, . . . with values of ๐‘›๐‘˜ and the subdigraph. The set of all 0102, 0212 16, 24, 35, 50, 74, 109, 158, 233, . . . possible combination of forbidden subwords generating 1012, 1210 16, 24, 36, 54, 80, 120, 180, 268, . . . the subdigraph can be computed by a separate function, 0212, 2021 16, 25, 36, 54, 81, 120, 180, 269, . . . which is not described here. 0201, 1020 16, 25, 38, 59, 90, 139, 214, 329, . . . of the orders of ๐‘˜-iterated line digraphs and their pres- ence in the database of integer sequences. Specifically, we compared the obtained integer sequences with the OEIS [7] database (On-Line Encyclopedia of Integer Se- quences). It is a comprehensive database of integer se- quences, where each sequence is uniquely identified by an ID number and accompanied by information such as definitions, references, links, and examples. We use ID numbers from OEIS database to identify the found integer sequences. Figure 5: ๐‘†๐น (3, 4) on the left and ๐‘†๐น (3, 4) without sub- First, we applied our algorithm to some digraphs from words 021, 120 on the right. the De Bruijn digraph family. For an alphabet of two sym- bols (the first non-trivial case), the number of distinct in- We demonstrate our algorithm using the Square-free teger sequences increased as the word lengths increased. digraph ๐‘†๐น (3, 4) shown in Figure 5. The input for our Table 2 presents all the obtained integer sequences along algorithm was the digraph ๐‘†๐น (3, 4) with ๐‘˜๐‘š๐‘Ž๐‘ฅ set to with examples of forbidden subwords. Additionally, we 10. One of the combinations in the for-cycle included list the OEIS ID number and the type of each integer the vertices represented by the words: 0102, 0121, 0201, sequence. 1012, 1020, 1210, 2010, 2012, 2101 and 2102. We identified Next, we ran the algorithm on some digraphs from the the forbidden subwords as 0120, 0210, 0212, 1021, 1201, Kautz digraph family. For an alphabet of two symbols, 1202, 2021 and 2120 in forbiddenSubwords. These we mostly obtained two integer sequences: A000007 and forbidden subwords can be simplified to forbidden sub- A007395 (all 2โ€™s sequence). The number of distinct integer words 021 and 120. The induced subdigraph is shown sequences increased with an alphabet of three or more in Figure 5. Subsequently, we obtained the integer se- symbols. quence of value ๐‘›๐‘˜ for ๐‘˜ = 0, . . . , 10, which in this case Similarly, for digraphs from the Cyclic Kautz family, is 10, 12, 14, 18, 22, 26, 32, 40, 48, 58, 72. with an alphabet of two symbols, two cases occurred: no integer sequences were found if the word lengths were odd, whereas the sequences A000007 and A007395 (all 5. Results 2โ€™s sequence) were found if the word lengths were even. With an alphabet of three symbols, we obtained more We ran our algorithm on various types of digraphs dis- integer sequences, where most of them were already cussed in Section 3. We focused on the integer sequences known. Lastly, we ran our algorithm on some digraphs from the Square-free digraph family. Similar to the Kautz di- graph family, for the alphabet of two symbols, integer sequences were found only for the digraphs ๐‘†๐น (2, 1), ๐‘†๐น (2, 2), and ๐‘†๐น (2, 3). With an alphabet of three sym- bols, the results were more interesting as we found vari- ous integer sequences that were not in the OEIS database. For ๐‘†๐น (3, 4), we found a total of 4947 integer sequences. Table 1 shows all integer sequences from digraphs of ๐‘†๐น (3, 4) with 16 vertices that were not in the OEIS database. Acknowledgments D. Zรกvackรกโ€™s research was partially supported by G-24- 158-00 and VEGA 1/0437/23. She would like to thank her supervisor Tatiana Jajcayovรก for her guidance and suggestions. C. Dalfรณ and M. A. Fiolโ€™s research has been supported by AGAUR from the Catalan Government un- der project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. M. A. Fiolโ€™s research was also supported by a grant from the Universitat Politรจcnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023. References [1] C. Dalfรณ, M. A. Fiol, A note on the order of iter- ated line digraphs, Journal of Graph Theory 85 (2017) 395โ€“399. doi:https://doi.org/10.1002/ jgt.22068. [2] N. H. Bong, C. Dalfรณ, M. A. Fiol, D. Zรกvackรก, The inner diameters of a digraph and its iterated line digraphs, 2024. [3] K. Bรถhmovรก, C. Dalfรณ, C. Huemer, The diameter of cyclic Kautz digraphs, Filomat 31 (2017) 6551โ€“6560. doi:10.2298/FIL1720551B. [4] T. G. Group, GAP - Groups, Algorithms, and Programming, Version 4.12.2, url: https://www. gap-system.org, 2024. [5] J. De Beule, J. Jonusas, J. Mitchell, W. A. Wil- son, M. Young, Digraphs, Version 1.7.1, url: https: //gap-packages.github.io/digraphs/, 2024. Refereed GAP package. [6] L. H. Soicher, GRAPE, graph algorithms using permutation groups, Version 4.9.0, url: https:// gap-packages.github.io/grape/, 2022. Refereed GAP package. [7] O. F. Inc., The on-line encyclopedia of integer se- quencesโ€ž 2024. URL: http://oeis.org. Table 2 Forbidden subwords in the ๐ต(2, 3) digraphs, the integer sequence of the numbers of vertices ๐‘›๐‘˜ of ๐‘˜-iterated line digraphs with the number and type of sequence in the OEIS database of sequences. Forbidden subwords Sequence OEIS[7] Type of sequence 11, 10, 000 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, . . . A000007 ๐‘Ž(๐‘›) = 0๐‘› 00, 01, 10 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, . . . A000012 All 1โ€™s sequence 00, 101, 110, 111 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, . . . A000038 ๐‘Ž(๐‘›) = 2 * 0๐‘› 11, 000, 010 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, . . . A130713 for ๐‘› โ‰ฅ 1 ๐‘Ž(0) = ๐‘Ž(2) = 1, ๐‘Ž(1) = 2; ๐‘Ž(๐‘›) = 0 for ๐‘›>2 10, 000, 011 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, . . . A054977 ๐‘Ž(0) = 2; ๐‘Ž(๐‘›) = 1 for ๐‘› โ‰ฅ 1 00, 01 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, . . . A007395 All 2โ€™s sequence 00, 000, 101, 111 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, . . . A143090 for ๐‘› โ‰ฅ 5 Aliquot sequence starting at 12 000, 001, 010, 011, 110 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, . . . A121273 for ๐‘› โ‰ฅ 4 Number of different ๐‘›-dimensional convex reg- ular polytopes that can tile ๐‘›-dimensional space 000, 001, 010, 011, 111 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, . . . not in OEIS 000, 001, 010, 101, 111 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, . . . A114348 for ๐‘› โ‰ฅ 16 The integer difference between the ๐‘›- dimensional unit sphere surface area minus the (๐‘› + 1)-dimensional unit sphere volume and the (๐‘› + 2)-dimensional unit sphere volume 000, 001, 011, 101, 110 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, . . . A261143 for ๐‘› โ‰ฅ 1 ๐‘Ž(๐‘›) = ๐ป๐‘› (1, 2), where ๐ป๐‘› is the ๐‘›-th hy- peroperator 00, 011, 101 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, . . . A072751 for ๐‘› โ‰ฅ 14 Greatest of the most frequent prime factors of squarefree numbers โ‰ค ๐‘›; ๐‘Ž(1) = 1 01, 000 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, . . . A010701 All 3โ€™s sequence 00, 010, 101 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, . . . A113311 for ๐‘› โ‰ฅ 1 Expansion of (1 + ๐‘ฅ)2 /(1 โˆ’ ๐‘ฅ) 000, 010, 011, 110 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, . . . not in OEIS 000, 010, 011, 111 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, . . . A143090 for ๐‘› โ‰ฅ 4 Aliquot sequence starting at 12 000, 011, 100, 101 4, 3, 2, 2, 2, 2, 2, 2, 2, 2,. . . not in OEIS 000, 010, 011, 100 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, . . . not in OEIS 000, 001, 011, 101 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, . . . not in OEIS 000, 001, 010, 011 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, . . . A010709 All 4โ€™s sequence 000, 001, 011, 111 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, . . . A010710 Periodical repetition of 4, 5 001, 010, 100, 101 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, . . . A210032 for ๐‘› โ‰ฅ 4 ๐‘Ž(๐‘›) = ๐‘› for ๐‘› = 1, 2, 3, 4; ๐‘Ž(๐‘›) = 5 for ๐‘›โ‰ฅ5 000, 001, 010, 101 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, . . . A101272 for ๐‘› โ‰ฅ 4 ๐‘Ž(๐‘›) = ๐‘› for ๐‘› โ‰ค 6; ๐‘Ž(๐‘›) = 6 for ๐‘› > 6 01 4, 5, 6, 7, 8, 9, 10, 11, 12, . . . A000027 for ๐‘› โ‰ฅ 4 Positive integers 11, 000 4, 5, 7, 9, 12, 16, 21, 28, . . . A000931 for ๐‘› โ‰ฅ 11 Padovan sequence 00, 010 4, 6, 9, 13, 19, 28, 41, 60, . . . A000930 for ๐‘› โ‰ฅ 5 Narayanaโ€™s cows sequence 000, 010, 011 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, . . . A010716 All 5โ€™s sequence 000, 001, 101 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, . . . A101101 for ๐‘› โ‰ฅ 2 ๐‘Ž(1) = 1, ๐‘Ž(2) = 5; ๐‘Ž(๐‘›) = 6 for ๐‘› โ‰ฅ 3 001, 010, 011 5, 6, 7, 8, 9, 10, 11, 12, . . . A000027 for ๐‘› โ‰ฅ 5 Positive integers 000, 010, 111 5, 6, 7, 9, 11, 13, 16, 20, . . . A164317 for ๐‘› โ‰ฅ 3 Number of binary strings of length ๐‘› with no substrings equal to 000, 010, or 111 000, 011, 110 5, 6, 8, 10, 13, 17, 22, 29, . . . A052954 for ๐‘› โ‰ฅ 8 Expansion of (2 โˆ’ ๐‘ฅ โˆ’ ๐‘ฅ2 โˆ’ ๐‘ฅ3 )/((1 โˆ’ ๐‘ฅ) * (1 โˆ’ ๐‘ฅ2 โˆ’ ๐‘ฅ3 )) 000, 010, 101 5, 7, 10, 14, 19, 26, 36, 50, . . . A003269 for ๐‘› โ‰ฅ 8 ๐‘Ž(0) = 0, ๐‘Ž(1) = ๐‘Ž(2) = ๐‘Ž(3) = 1; ๐‘Ž(๐‘›) = ๐‘Ž(๐‘› โˆ’ 1) + ๐‘Ž(๐‘› โˆ’ 4) 001, 010, 100 5, 7, 10, 14, 20, 29, 42, 61, . . . A020711 Pisot sequences ๐ธ(5, 7), ๐‘ƒ (5, 7) 000, 001, 010 5, 7, 11, 16, 23, 34, 50, 73, . . . A164316 for ๐‘› โ‰ฅ 3 Number of binary strings of length ๐‘› with no substrings equal to 000, 001, or 010 000, 001, 011 5, 7, 8, 10, 11, 13, 14, 16, . . . A001651 for ๐‘› โ‰ฅ 4 Numbers not divisible by 3 001, 010, 101 5, 7, 9, 11, 13, 15, 17, 19, . . . A005408 for ๐‘› โ‰ฅ 2 Odd numbers 000, 001, 111 5, 7, 9, 12, 16, 21, 28, 37, . . . A000931 for ๐‘› โ‰ฅ 12 Padovan sequence 00 5, 8, 13, 21, 34, 55, 89, 144, . . . A000045 for ๐‘› โ‰ฅ 5 Fibonacci numbers 000, 001 6, 10, 16, 26, 42, 68, 110, . . . A090991 Number of meaningful differential operations of the ๐‘›-th order on the space ๐‘…6 010, 011 6, 8, 10, 12, 14, 16, 18, 20, . . . A005843 for ๐‘› โ‰ฅ 3 Nonnegative even numbers 001, 011 6, 9, 12, 16, 20, 25, 30, 36, . . . A002620 for ๐‘› โ‰ฅ 5 Quarter-squares 000, 011 6, 9, 13, 18, 25, 34, 46, 62, . . . A164315 for ๐‘› โ‰ฅ 3 Number of binary strings of length ๐‘› with no substrings equal to 000 or 011 000, 101 6, 9, 13, 19, 28, 41, 60, 88, . . . A000930 for ๐‘› โ‰ฅ 6 Narayanaโ€™s cows sequence 001, 010 6, 9, 14, 21, 31, 46, 68, 100, . . . A038718 for ๐‘› โ‰ฅ 5 Number of permutations ๐‘ƒ of ๐‘›-set such that ๐‘ƒ (1) = 1 and |๐‘ƒ โˆ’1 (๐‘–+1)โˆ’๐‘ƒ โˆ’1 (๐‘–)| equals 1 or 2 for ๐‘– = 1, 2, ..., ๐‘› โˆ’ 1 001, 100 6, 9, 14, 22, 35, 56, 90, 145, . . . A020717 Pisot sequences ๐ฟ(6, 9), ๐ธ(6, 9) 000, 010 6, 9, 15, 25, 40, 64, 104, . . . A006498 for ๐‘› โ‰ฅ 5 ๐‘Ž(0) = ๐‘Ž(1) = ๐‘Ž(2) = 1, ๐‘Ž(3) = 2; ๐‘Ž(๐‘›) = ๐‘Ž(๐‘› โˆ’ 1) + ๐‘Ž(๐‘› โˆ’ 3) + ๐‘Ž(๐‘› โˆ’ 4) 001 7, 12, 20, 33, 54, 88, 143, . . . A020732 for ๐‘› โ‰ฅ 1 Pisot sequence ๐‘‡ (4, 7) 010 7, 12, 21, 37, 65, 114, 200, . . . A010901 for ๐‘› โ‰ฅ 1 Pisot sequences ๐ธ(4, 7), ๐‘ƒ (4, 7) 000 7, 13, 24, 44, 81, 149, 274, . . . A282718 for ๐‘› โ‰ฅ 4 Tribonacci recurrence none 8, 16, 32, 64, 128, 256, 512, . . . A000079 for ๐‘› โ‰ฅ 3 Powers of 2