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.
integer sequences that we obtained and compare them to those in the OEIS database. We list new integer sequences not found there.
This article primarily focuses on digraphs (directed graphs), which consist of vertices connected by directed edges. These directed edges indicate a one-way relationship between the vertices. By iteratively applying 2. Preliminaries a specific method to obtain new digraphs, we can create 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 didigraph 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 adjaand 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 = , meanof 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 ≥ 0. A regular partition of () is a partition of the vertices into subsets 1, 2, . . . , such that every vertex ∈ is adjacent to the same number of vertices in , where and belong to {1, 2, . . . , }. Given a ITAT’24: Computational Aspects of Large-Scale Problems in Discrete Mathematics, September 20–24, 2024, Drienica, Slovakia * Corresponding author. $ dominika.mihalova@fmph.uniba.sk (D. Závacká); cristina.dalfo@udl.cat (C. Dalfó); miguel.angel.fiol@upc.edu (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 CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) set {1, 2, . . . , }, a quotient matrix ℬ is an × 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 = where = (1, . . . , 1). In the case where is a -regular of order , the () is also a -regular digraph, and the computation of its order can be simplified to:
= However, if is not a -regular digraph, the complexity of computing the order of () depends completely on the dimension of , that is, the number of vertices in .
Dalfó and Fiol [1] introduced a method to compute of () as shown in Theorem 1. They start by obtaining a quotient matrix ℬ based on a regular partition of the vertex set of . The size of ℬ is the same or smaller than that of based on the partition of vertices. The quotient matrix is used to compute the initial values for the recurrence equation depending on the minimal polynomial of the quotient matrix. The subsequent values of are determined by the recurrence equation.
Theorem 1 ([1]). Let = (, ) be a digraph on vertices, and consider a regular partition = (1, . . . , ) with quotient matrix ℬ. Let () = − − 1− 1 − · · · − 0 be the minimal polynomial of ℬ. Then, the number of vertices of the -iterated line digraph () satisfies the recurrence = − 1− 1 + · · · + 0− , for = , + 1, . . .
Part of our research is to develop an eficient method for computing the number of words of length ℓ over an alphabet of symbols, where words do not contain any subword from a given set . To simulate this problem on digraphs, we decided to choose families of digraphs whose vertices are represented by words over some alphabet. Each family has its specific restrictions about the words, represented by vertices and connections (arcs) between them. We swiftly introduce four known families of digraphs and show some examples.
The De Bruijn digraph (, ℓ) has vertices labeled by all possible words 12 . . . ℓ with ∈ {0, 1, . . . , − 1}. There is an arc from vertex 12 . . . ℓ to vertex 2 . . . ℓℓ+1. An example of the De Bruijn digraph is shown in Figure 1.
The Kautz digraph (, ℓ) has vertices labeled by all
possible words 12 . . . ℓ with ∈ {0, 1, . . . , − 1},
where ̸= +1 for = 1, . . . , ℓ − 1.There is an arc
from vertex 12 . . . ℓ to vertex 2 . . . ℓℓ+1,
whenever ℓ ̸= ℓ+1. An example of a Kautz digraph is shown
in Figure 2.
initialized with the values , for = 0, 1, . . . , − 1, Figure 1: (
= ∑︁ || ∑︁(ℬ) = ℬ ,
=1 =1 where = (|1|, . . . , ||) and = (1, . . . , 1).
The recurrence equation in Theorem 1 is an eficient way of calculating the order of a -iterated line digraph for digraphs that are not -regular. Moreover, it allows us to solve other problems more efectively. The authors in
The Cyclic Kautz digraph (, ℓ) was introduced by Böhmová, Dalfó, and Huemer in [3]. The Cyclic Kautz digraph has vertices labeled by all possible words 12 . . . ℓ with ∈ {0, 1, . . . , − 1}, where ̸= +1 for = 1, . . . , ℓ − 1, and 1 ̸= ℓ. There is an arc from vertex 12 . . . ℓ to vertex 2 . . . ℓℓ+1, whenever ℓ+1 ̸= ℓ and ℓ+1 ̸= 2. An example of a Cyclic Kautz digraph is shown in Figure 3.
The Square-free digraph (, ℓ) has vertices labeled by all possible words 12 . . . ℓ with ∈ {0, 1, . . . , − 1}, that does not contain an adjacent repetition of any subword of length at most 2. There is an arc from 12 . . . ℓ 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 chosen from one of the families of digraphs discussed in Sec4. Algorithm tion 3, with each family imposing its own specific restrictions 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 specgorithm based mostly on Theorem 1 and the method ifies the maximum value of . The algorithm begins with suggested by the authors in [2]. We programmed the algorithm in the system for computational discrete algebra - 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 efective for computational problems involving groups, graphs, and other combinatorial structures.
For the implementation of our algorithm, we imported the packages Digraphs and GRAPE. The Digraphs package [5] was implemented to create, store, and compute 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 determine 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 possible combinations of subwords (forbidden subwords) from a set of subwords . Initially, we employed the method described in [2] in a for-cycle and evaluated all possible combinations of forbidden subwords. However, this method was computationally very challenging as the algorithm required significant processing time to evaluate all the combinations, and it frequently produced numerous identical digraphs. To address these challenges, we opted to examine all possible induced subdigraphs instead. This alternative approach allows us to eficiently generate all integer sequences and determine the set of forbidden subwords based on forbidden and allowed vertices.
Algorithm 1 Pseudocode: obtaining integer sequences for all subdigraphs of a given digraph
SequencesForAllSubdigraphs(, )
for all combination of () do
forbiddenSubwords = Diference(vertices of ,
combination)
subdigraph = InducedSubdigraph(, combination)
sequence = LGSequence(subdigraph, )
print (forbiddenSubwords, sequence, subdigraph)
end for
end function
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 (
Figure 5: (
We demonstrate our algorithm using the Square-free teger sequences increased as the word lengths increased.
digraph (
Lastly, we ran our algorithm on some digraphs from
the Square-free digraph family. Similar to the Kautz
digraph family, for the alphabet of two symbols, integer
sequences were found only for the digraphs (
For (
Table 1 shows all integer sequences from digraphs of
(
D. Závacká’s research was partially supported by G-24158-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 under 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. 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, . . . 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, . . . 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, . . . 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, . . . 4, 3, 2, 2, 2, 2, 2, 2, 2, 2,. . . 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, . . . 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, . . . 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, . . . 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, . . . 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, . . . 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, . . . 4, 5, 6, 7, 8, 9, 10, 11, 12, . . . 4, 5, 7, 9, 12, 16, 21, 28, . . . 4, 6, 9, 13, 19, 28, 41, 60, . . . 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, . . . 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, . . . 5, 6, 7, 8, 9, 10, 11, 12, . . . 5, 6, 7, 9, 11, 13, 16, 20, . . . 5, 6, 8, 10, 13, 17, 22, 29, . . . 5, 7, 10, 14, 19, 26, 36, 50, . . . 5, 7, 10, 14, 20, 29, 42, 61, . . . 5, 7, 11, 16, 23, 34, 50, 73, . . . A001651 for ≥ 4 A005408 for ≥ 2 A000931 for ≥ 12 A000045 for ≥ 5 A090991 A000930 for ≥ 6 A038718 for ≥ 5
Type of sequence
() = 0
All 1’s sequence
() = 2 * 0
(0) = (
ular polytopes that can tile -dimensional space
dimensional unit sphere surface area minus the
( + 1)-dimensional unit sphere volume and
the ( + 2)-dimensional unit sphere volume
() = (
Expansion of (1 + )2/(1 − )
() = for = 1, 2, 3, 4; () = 5 for ≥ 5 () = for ≤ 6; () = 6 for > 6 Positive integers Padovan sequence Narayana’s cows sequence
(
substrings equal to 000, 010, or 111
Expansion of (2 − − 2 − 3)/((1 − ) *
(1 − 2 − 3))
(0) = 0, (
substrings equal to 000, 001, or 010
Odd numbers Padovan sequence Fibonacci numbers Number of meaningful diferential operations of the -th order on the space 6 Nonnegative even numbers Quarter-squares
substrings equal to 000 or 011 Narayana’s cows sequence
(
Pisot sequences (