Search

Given an undirected multigraph G = (V , E) with no self-loops, and one of its nodes s ∈ V , we consider the #P-complete problem of counting the number E T s (e) (G) of its Eulerian tours starting and ending at node s. We provide lower and upper bounds on the size of E T s (e) (G) . Namely, let d(v) denote the degree of a node v ∈ V ; we show that max { L 1 (e) , L 2 (e) } ≤ | E T s (e) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! where L 1 (e) = (d (s) - 1) ! ! ∏ v ∈ V \ s (d (v) - 2) ! ! and L 2 (e) = 2 1 - | V | + | E | . We also consider the notion of node-distinct Eulerian tours. Indeed, the classical Eulerian tours are edge-distinct sequences. Node-distinct Eulerian tours, denoted E T s (n) (G) , should instead be different as node sequences. Let Δ (u) be the number of distinct neighbors of a node u, D ⊆ E be the set of distinct edges in the multigraph G, and m(e) for an edge e ∈ E be its multiplicity (i.e. | E | = ∑ e ∈ D m (e) ). We prove that max { L 1 (n) , L 2 (n) , L 3 (n) } ≤ | E T s (n) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! · ∏ e ∈ D m (e) ! - 1 , where L 1 (n) = L 1 (e) / (∏ e ∈ D m (e) !) , L 2 (n) = (Δ (s) - 1) ! ! ∏ v ∈ V \ s (Δ (v) - 2) ! ! , and L 3 (n) = 2 1 - | V | + | D | . We also extend all of our results to graphs having self-loops. [ABSTRACT FROM AUTHOR]

For an integer q ≥ 2 , a q-recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of q. In this article, q-recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. It is shown that every q-recursive sequence is q-regular in the sense of Allouche and Shallit and that a q-linear representation of the sequence can be computed easily by using the coefficients from the recurrence relations. Detailed asymptotic results for q-recursive sequences are then obtained based on a general result on the asymptotic analysis of q-regular sequences. Three particular sequences are studied in detail: We discuss the asymptotic behavior of the summatory functions of Stern's diatomic sequence, the number of non-zero elements in some generalized Pascal's triangle and the number of unbordered factors in the Thue–Morse sequence. For the first two sequences, our analysis even leads to precise formulæ without error terms. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and # W [ 1 ] -complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota's NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs. [ABSTRACT FROM AUTHOR]

In this article, q-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail: sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input; the amount of esthetic numbers in the first N natural numbers; and the number of odd entries in the rows of Pascal's rhombus. For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known. [ABSTRACT FROM AUTHOR]