bluuebunny/crossref_metadata_2025_split huggingface dataset:
Convex Partitions of Graphs induced by Paths of Order Three
Authors: Centeno C. C. , Dantas S. , Dourado M. C. , Rautenbach Dieter , Szwarcfiter Jayme Luiz 
Published: August 2021

Graphs and Algorithms
A set C of vertices of a graph G is P(3)-convex if v is an element of C for every path uvw in G with u, w is an element of C. We prove that it is NP-complete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p non-empty disjoint P(3)-convex sets. Furthermore, we study such partitions for a variety of graph classes.
Synchronizing random automata
Authors: Skvortsov Evgeny , Zaks Yulia 
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications
Conjecture that any synchronizing automaton with n states has a reset word of length (n - 1)(2) was made by. Cerny in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. In this paper we study a random automaton that is sampled uniformly at random from the set of all automata with n states and m(n) letters. We show that for m(n) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n(beta), beta > 1/2 we also show that any random automaton with high probability satisfies the. Cerny conjecture.
The cluster and dual canonical bases of Z[x(11), ..., x(33)] are equal
Authors: Rhoades Brendon 
Published: August 2021

Combinatorics
The polynomial ring Z[x(11), ..., x(33)] has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group U-q(sl(3) (C)). On the other hand, Z[x(1 1), ... , x(33)] inherits a basis from the cluster monomial basis of a geometric model of the type D-4 cluster algebra. We prove that these two bases are equal. This extends work of Skandera and proves a conjecture of Fomin and Zelevinsky.
On the existence of block-transitive combinatorial designs
Authors: Huber Michael 
Published: August 2021

Combinatorics
Block-transitive Steiner t-designs form a central part of the study of highly symmetric combinatorial configurations at the interface of several disciplines, including group theory, geometry, combinatorics, coding and information theory, and cryptography. The main result of the paper settles an important open question: There exist no non-trivial examples with t = 7 (or larger). The proof is based on the classification of the finite 3-homogeneous permutation groups, itself relying on the finite simple group classification.
On uniform recurrence of a direct product
Authors: Salimov Pavel Vadimovich 
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications
The direct product of two words is a naturally defined word on the alphabet of pairs of symbols. An infinite word is uniformly recurrent if each its subword occurs in it with bounded gaps. An infinite word is strongly recurrent if the direct product of it with each uniformly recurrent word is also uniformly recurrent. We prove that fixed points of the expanding binary symmetric morphisms are strongly recurrent. In particular, such is the Thue-Morse word.
Deterministic Recurrent Communication and Synchronization in Restricted Sensor Network
Authors: Fernández Anta Antonio , Mosteiro Miguel , Thraves Caro Christopher 
Published: August 2021

Distributed Computing and Networking
Monitoring physical phenomena in Sensor Networks requires guaranteeing permanent communication between nodes. Moreover, in an effective implementation of such infrastructure, the delay between any two consecutive communications should be minimized. The problem is challenging because, in a restricted Sensor Network, the communication is carried out through a single and shared radio channel without collision detection. Dealing with collisions is crucial to ensure effective communication between nodes. Additionally, minimizing them yields energy consumption minimization, given that sensing and computational costs in terms of energy are negligible with respect to radio communication. In this work, we present a deterministic recurrent-communication protocol for Sensor Networks. After an initial negotiation phase of the access pattern to the channel, each node running this protocol reaches a steady state, which is asymptotically optimal in terms of energy and time efficiency. As a by-product, a protocol for the synchronization of a Sensor Network is also proposed. Furthermore, the protocols are resilient to an arbitrary node power-up schedule and a general node failure model.
On the metric dimension of Grassmann graphs
Authors: Bailey Robert F. , Meagher Karen 
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
The metric dimension of a graph Gamma is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph G(q)(n, k) (whose vertices are the k-subspaces of F-q(n), and are adjacent if they intersect in a (k 1)-subspace) for k \textgreater= 2. We find an upper bound on its metric dimension, which is equal to the number of 1-dimensional subspaces of F-q(n). We also give a construction of a resolving set of this size in the case where k + 1 divides n, and a related construction in other cases.
Random 2-SAT Solution Components and a Fitness Landscape
Authors: Pitman Damien 
Published: August 2021

Graphs and Algorithms
We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of variables. Thus, our result implies that exponentially many solutions are organized into a stochastically bounded number of components. We also describe an application to biological evolution; in particular, to a type of fitness landscape where satisfying assignments represent viable genotypes and connectivity of genotypes is limited by single site mutations. The biological result is that, with probability approaching 1, each viable genotype is connected by single site mutations to an exponential number of other viable genotypes while the number of viable clusters is finite.
Negative bases and automata
Authors: Frougny Christiane , Lai Anna Chiara 
Published: August 2021

Automata, Logic and Semantics
We study expansions in non-integer negative base -beta introduced by Ito and Sadahiro. Using countable automata associated with (-beta)-expansions, we characterize the case where the (-beta)-shift is a system of finite type. We prove that, if beta is a Pisot number, then the (-beta)-shift is a sofic system. In that case, addition (and more generally normalization on any alphabet) is realizable by a finite transducer. We then give an on-line algorithm for the conversion from positive base beta to negative base -beta. When beta is a Pisot number, the conversion can be realized by a finite on-line transducer.
Recursions and divisibility properties for combinatorial Macdonald polynomials
Authors: Loehr Nicholas A. , Niese Elizabeth 
Published: August 2021

Combinatorics
For each integer partition mu, let e (F) over tilde (mu)(q; t) be the coefficient of x(1) ... x(n) in the modified Macdonald polynomial (H) over tilde (mu). The polynomial (F) over tilde (mu)(q; t) can be regarded as the Hilbert series of a certain doubly-graded S(n)-module M(mu), or as a q, t-analogue of n! based on permutation statistics inv(mu) and maj(mu) that generalize the classical inversion and major index statistics. This paper uses the combinatorial definition of (F) over tilde (mu) to prove some recursions characterizing these polynomials, and other related ones, when mu is a two-column shape. Our result provides a complement to recent work of Garsia and Haglund, who proved a different recursion for two-column shapes by representation-theoretical methods. For all mu, we show that e (F) over tilde (mu)(q, t) is divisible by certain q-factorials and t-factorials depending on mu. We use our recursion and related tools to explain some of these factors bijectively. Finally, we present fermionic formulas that express e (F) over tilde ((2n)) (q, t) as a sum of q, t-analogues of n!2(n) indexed by perfect matchings.
Parameterized Problems Related to Seidel's Switching
Authors: Jelinkova Eva , Suchy Ondrej , Hlineny Petr , Kratochvil Jan 
Published: August 2021

Graphs and Algorithms
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum Likelihood Decoding of graph theoretic codes based on complete graphs.
Irregular edge coloring of 2-regular graphs
Authors: Cichacz Sylwia , Przybylo Jakub 
Published: August 2021

Graphs and Algorithms
Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular coloring number for almost all 2-regular graphs. The results obtained provide new examples demonstrating that a conjecture by Burris is false. As another consequence, we also determine the value of a graph invariant called the point distinguishing index (where sets, instead of multisets, are required to be distinct) for the same family of graphs.
The generalized 3-connectivity of Cartesian product graphs
Authors: Li Hengzhe , Li Xueliang , Sun Yuefang 
Published: August 2021

Graph Theory
The generalized connectivity of a graph, which was introduced by Chartrand et al. in 1984, is a generalization of the concept of vertex connectivity. Let S be a nonempty set of vertices of G, a collection \T-1, T (2), ... , T-r\ of trees in G is said to be internally disjoint trees connecting S if E(T-i) boolean AND E(T-j) - empty set and V (T-i) boolean AND V(T-j) = S for any pair of distinct integers i, j, where 1 <= i, j <= r. For an integer k with 2 <= k <= n, the k-connectivity kappa(k) (G) of G is the greatest positive integer r for which G contains at least r internally disjoint trees connecting S for any set S of k vertices of G. Obviously, kappa(2)(G) = kappa(G) is the connectivity of G. Sabidussi's Theorem showed that kappa(G square H) >= kappa(G) + kappa(H) for any two connected graphs G and H. In this paper, we prove that for any two connected graphs G and H with kappa(3) (G) >= kappa(3) (H), if kappa(G) > kappa(3) (G), then kappa(3) (G square H) >= kappa(3) (G) + kappa(3) (H); if kappa(G) = kappa(3)(G), then kappa(3)(G square H) >= kappa(3)(G) + kappa(3) (H) - 1. Our result could be seen as an extension of Sabidussi's Theorem. Moreover, all the bounds are sharp.
The competition number of a generalized line graph is at most two
Authors: Park Boram , Sano Yoshio 
Published: August 2021

Graph Theory
In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this paper, we generalize this result to the competition numbers of generalized line graphs, that is, we show that the competition number of a generalized line graph is at most two, and give necessary conditions and sufficient conditions for the competition number of a generalized line graph being one.
The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis
Authors: Louchard Guy , Prodinger Helmut 
Published: August 2021

Analysis of Algorithms
We study a leader election protocol that we call the Swedish leader election protocol. This name comes from a protocol presented by L. Bondesson, T. Nilsson, and G. Wikstrand (2007). The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one player remaining, the protocol stops and the player is declared the leader. Otherwise, all remaining players flip a biased coin; with probability q the player survives to the next round, with probability p = 1 - q the player loses (is killed) and plays no further ... unless all players lose in a given round (null round), so all of them play again. In the classical leader election protocol, any number of null rounds may take place, and with probability 1 some player will ultimately be elected. In the Swedish leader election protocol there is a maximum number tau of consecutive null rounds, and if the threshold is attained the protocol fails without declaring a leader. In this paper, several parameters are asymptotically analyzed, among them: Success Probability, Number of rounds R-n, Number of null rounds T-n. This paper is a companion paper to Louchard, Martinez and Prodinger (2011) where De-Poissonization was used, together with the Mellin transform. While this works fine as far as it goes, there are limitations, in particular of a computational nature. The approach chosen here is similar to earlier efforts of the same authors - Louchard and Prodinger (2004,2005,2009). Identifying some underlying distributions as Gumbel (type) distributions, one can start with approximations at a very early stage and compute (at least in principle) all moments asymptotically. This is in contrast to the companion work, where only expected values were considered. In an appendix, it is shown that, whereever results are given in both papers, they coincide, although they are presented in different ways.
On 4-valent Frobenius circulant graphs
Authors: Zhou Sanming 
Published: August 2021

Graph Theory
A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1, h) = Cay(Zn, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and H = {[1], [h], −[1], −[h]} with h a solution to the congruence equation x 2 + 1 ≡ 0 (mod n). In [A. Thomson and S. Zhou, Frobenius circulant graphs of valency four, J. Austral. Math. Soc. 85 (2008), 269-282] it was proved that such graphs admit 'perfect ' routing and gossiping schemes in some sense, making them attractive candidates for modelling interconnection networks. In the present paper we prove that DLn(1, h) has the smallest possible broadcasting time, namely its diameter plus two, and we explicitly give an optimal broadcasting in DLn(1, h). Using number theory we prove that it is possible to recursively construct larger 4-valent first-kind Frobenius circulants from smaller ones, and we give a methodology for such a construction. These and existing results suggest that, among all 4-valent circulant graphs, 4-valent first-kind Frobenius circulants are extremely efficient in terms of routing, gossiping, broadcasting and recursive construction.
Secure frameproof codes through biclique covers
Authors: Hajiabolhassan Hossein , Moazami Farokhlagha 
Published: August 2021

Graph Theory
For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{w1i,...,wri} . We call a code r-secure frameproof of size t if |Γ|=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these sets is nonempty. A d-biclique cover of size v of a graph G is a collection of v-complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w;d) cover-free family is a family of subsets of a finite set such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. Also, we present an upper bound for 1-biclique covering number of Kneser graphs.
Upper k-tuple domination in graphs
Authors: Chang Gerard Jennhwa , Dorbec Paul , Kim Hye Kyung , Raspaud André , Wang Haichao , Zhao Weiliang 
Published: August 2021

Graph Theory
For a positive integer k, a k-tuple dominating set of a graph G is a subset S of V (G) such that |N [v] ∩ S| ≥ k for every vertex v, where N [v] = {v} ∪ {u ∈ V (G) : uv ∈ E(G)}. The upper k-tuple domination number of G, denoted by Γ×k (G), is the maximum cardinality of a minimal k-tuple dominating set of G. In this paper we present an upper bound on Γ×k (G) for r-regular graphs G with r ≥ k, and characterize extremal graphs achieving the upper bound. We also establish an upper bound on Γ×2 (G) for claw-free r-regular graphs. For the algorithmic aspect, we show that the upper k-tuple domination problem is NP-complete for bipartite graphs and for chordal graphs.
Descent variation of samples of geometric random variables
Authors: Brennan Charlotte , Knopfmacher Arnold 
Published: August 2021

Combinatorics
In this paper, we consider random words ω1ω2ω3⋯ωn of length n, where the letters ωi ∈ℕ are independently generated with a geometric probability such that Pωi=k=pqk-1 where p+q=1 . We have a descent at position i whenever ωi+1 < ωi. The size of such a descent is ωi-ωi+1 and the descent variation is the sum of all the descent sizes for that word. We study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities, and find the probability generating functions for descent variation of such words.
Efficient repeat finding in sets of strings via suffix arrays
Authors: Barenbaum Pablo , Becher Verónica , Deymonnaz Alejandro , Halsband Melisa , Heiber Pablo Ariel 
Published: August 2021

Discrete Algorithms
We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O(m) memory, where m is the length of the longest input string, and O(n &log;m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive part of our algorithms is the computation of several suffix arrays. We give an implementation and experimental results that evidence the efficiency of our algorithms in practice, even for very large inputs.
Derivatives of approximate regular expressions
Authors: Champarnaud Jean-Marc , Jeanne Hadrien , Mignot Ludovic 
Published: August 2021

Automata, Logic and Semantics
Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular expressions extended to similarity operators, that we call AREs (Approximate Regular Expressions). We set formulae to compute the Brzozowski derivatives and the Antimirov derivatives of an ARE, which allows us to give a solution to the ARE membership problem and to provide the construction of two recognizers for the language denoted by an ARE. As far as we know, the family of approximative regular expressions is introduced for the first time in this paper. Classical approximate regular expression matching algorithms are approximate matching algorithms on regular expressions. Our approach is rather to process an exact matching on approximate regular expressions.
A stronger recognizability condition for two-dimensional languages
Authors: Anselmo Marcella , Madonia Maria 
Published: August 2021

Automata, Logic and Semantics
The paper presents a condition necessarily satisfied by (tiling system) recognizable two-dimensional languages. The new recognizability condition is compared with all the other ones known in the literature (namely three conditions), once they are put in a uniform setting: they are stated as bounds on the growth of some complexity functions defined for two-dimensional languages. The gaps between such functions are analyzed and examples are shown that asymptotically separate them. Finally the new recognizability condition results to be the strongest one, while the remaining ones are its particular cases. The problem of deciding whether a two-dimensional language is recognizable is here related to the one of estimating the minimal size of finite automata recognizing a sequence of (one-dimensional) string languages.
Removable edges in near-bricks
Authors: Wang Xiumei , He Cheng , Lin Yixun 
Published: August 2021

Graph Theory
For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. This paper generalizes the result obtained by Carvalho et al. to the case of irreducible near-brick, where a graph is irreducible if it contains no induced odd path of length 3 or more. Meanwhile, a lower bound on the number of removable edges of matching-covered bipartite graphs is presented.
A note on the NP-hardness of two matching problems in induced subgrids
Authors: Demange Marc , Ekim Tınaz 
Published: August 2021

Graph Theory
Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids.