bluuebunny/crossref_metadata_2025_split huggingface dataset:
Acyclic colourings of graphs with bounded degree
Authors: Borowiecki Mieczyslaw , Fiedorowicz Anna , Jesse-Jozefczyk Katarzyna , Sidorowicz Elzbieta 
Published: August 2021

Graphs and Algorithms
A k-colouring of a graph G is called acyclic if for every two distinct colours i and j, the subgraph induced in G by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, there are no bichromatic alternating cycles. In 1999 Boiron et al. conjectured that a graph G with maximum degree at most 3 has an acyclic 2-colouring such that the set of vertices in each colour induces a subgraph with maximum degree at most 2. In this paper we prove this conjecture and show that such a colouring of a cubic graph can be determined in polynomial time. We also prove that it is an NP-complete problem to decide if a graph with maximum degree 4 has the above mentioned colouring.
Split-critical and uniquely split-colorable graphs
Authors: Ekim Tınaz , Ries Bernard , De Werra Dominique 
Published: August 2021

Graphs and Algorithms
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic.
Some properties of semiregular cages
Authors: Balbuena Camino , Marcote Xavier , Gonzalez-Moreno Diego 
Published: August 2021

Graphs and Algorithms
A graph with degree set \r, r + 1\ is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be maximally connected when the girth g >= 7 is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every semiregular cage with degree set \r, r + 1\ is proved to be maximally connected for g is an element of \6, 8\, and when g = 12 for r >= 7 and r not equal 20. Finally it is also shown that every (\r, r + 1\; g)-cage is 3-connected.
Lower Bounds on the Area Requirements of Series-Parallel Graphs
Authors: Frati Fabrizio 
Published: August 2021

Graphs and Algorithms
We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K(2,n), one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or poly-line grid drawing. Combining the two results, the Omega(n2(root log n)) area lower bound is achieved.
Deciding whether the ordering is necessary in a Presburger formula
Authors: Choffrut Christian , Frigeri Achille 
Published: August 2021

Automata, Logic and Semantics
We characterize the relations which are first-order definable in the model of the group of integers with the constant 1. This allows us to show that given a relation defined by a first-order formula in this model enriched with the usual ordering, it is recursively decidable whether or not it is first-order definable without the ordering.
On the support of the free Lie algebra: the Schutzenberger problems
Authors: Michos Ioannis C. 
Published: August 2021

Combinatorics
M.-P. Schutzenberger asked to determine the support of the free Lie algebra L(Zm) (A) on a finite alphabet A over the ring Z(m) of integers mod m and all pairs of twin and anti-twin words, i.e., words that appear with equal (resp. opposite) coefficients in each Lie polynomial. We characterize the complement of the support of L(Zm) (A) in A* as the set of all words w such that m divides all the coefficients appearing in the monomials of l* (w), where l* is the adjoint endomorphism of the left normed Lie bracketing l of the free Lie ring. Calculating l* (w) via the shuffle product, we recover the well known result of Duchamp and Thibon (Discrete Math. 76 (1989) 123-132) for the support of the free Lie ring in a much more natural way. We conjecture that two words u and v of common length n, which lie in the support of the free Lie ring, are twin (resp. anti-twin) if and only if either u = v or n is odd and u = (v) over tilde (resp. if n is even and u = (v) over tilde), where (v) over tilde denotes the reversal of v and we prove that it suffices to show this for a two-lettered alphabet. These problems can be rephrased, for words of length n, in terms of the action of the Dynkin operator l(n) on lambda-tabloids, where lambda is a partition of n. Representing a word w in two letters by the subset I of [n] = \1, 2, ... , n\ that consists of all positions that one of the letters occurs in w, the computation of l* (w) leads us to the notion of the Pascal descent polynomial p(n)(I), a particular commutative multi-linear polynomial which is equal to the signed binomial coefficient when vertical bar I vertical bar = 1. We provide a recursion formula for p(n) (I) and show that if m inverted iota Sigma(i is an element of I)(1)(i-1) (n - 1 i - 1), then w lies in the support of L(Zm) (A).
Nordhaus-Gaddum Type Results for Total Domination
Authors: Henning Michael , Joubert Ernst , Southey Justin 
Published: August 2021

Graph Theory
A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we study Nordhaus-Gaddum-type results for total domination. We examine the sum and product of γt(G1) and γt(G2) where G1 ⊕G2 = K(s,s), and γt is the total domination number. We show that the maximum value of the sum of the total domination numbers of G1 and G2 is 2s+4, with equality if and only if G1 = sK2 or G2 = sK2, while the maximum value of the product of the total domination numbers of G1 and G2 is max{8s,⌊(s+6)2/4 ⌋}.
Cycle transversals in bounded degree graphs
Authors: Groshaus Marina , Hell Pavol , Klein Sulamita , Nogueira Loana Tito , Protti Fábio 
Published: August 2021

Graphs and Algorithms
In this work we investigate the algorithmic complexity of computing a minimum C(k)-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k \textgreater= 3. For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when k \textless= 4, and NP-hard otherwise. For graphs of maximum degree at most four, we prove that this problem is NP-hard for any fixed k \textgreater= 3. We also discuss polynomial-time approximation algorithms for computing C(3)-transversals in graphs of maximum degree at most four, based on a new decomposition theorem for such graphs that leads to useful reduction rules.
The largest singletons in weighted set partitions and its applications
Authors: Sun Yidong , Xu Yanjie 
Published: August 2021

Combinatorics
Recently, Deutsch and Elizalde studied the largest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let A (n,k) (t) denote the total weight of partitions on [n + 1] = \1,2,..., n + 1\ with the largest singleton \k + 1\. In this paper, explicit formulas for A (n,k) (t) and many combinatorial identities involving A (n,k) (t) are obtained by umbral operators and combinatorial methods. In particular, the permutation case leads to an identity related to tree enumerations, namely, [GRAPHICS] where D-k is the number of permutations of [k] with no fixed points.
The extended equivalence and equation solvability problems for groups
Authors: Horvath Gabor , Szabo Csaba 
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
We prove that the extended equivalence problem is solvable in polynomial time for finite nilpotent groups, and coNP-complete, otherwise. We prove that the extended equation solvability problem is solvable in polynomial time for finite nilpotent groups, and NP-complete, otherwise.
On packing of two copies of a hypergraph
Authors: Pilsniak Monika , WoźniaK Mariusz 
Published: August 2021

Graphs and Algorithms
A 2-packing of a hypergraph H is a permutation sigma on V (H) such that if an edge e belongs to epsilon(H), then sigma(e) does not belong to epsilon(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n - 2. We prove that if H has at most n - 2 edges then it is 2-packable.
A Combinatorial Approach to the Tanny Sequence
Authors: Das Anita 
Published: August 2021

Combinatorics
The Tanny sequence T (i) is a sequence defined recursively as T(i) = T(i - 1 - T(i - 1)) + T(i - 2 - T(i - 2)), T(0) = T(1) = T(2) = 1. In the first part of this paper we give combinatorial proofs of all the results regarding T(i), that Tanny proved in his paper "A well-behaved cousin of the Hofstadter sequence", Discrete Mathematics, 105(1992), pp. 227-239, using algebraic means. In most cases our proofs turn out to be simpler and shorter. Moreover, they give a "visual" appeal to the theory developed by Tanny. We also generalize most of Tanny's results. In the second part of the paper we present many new results regarding T(i) and prove them combinatorially. Given two integers n and k, it is interesting to know if T(n) = k or not. In this paper we characterize such numbers.
On the sensitivity of cyclically-invariant Boolean functions
Authors: Chakraborty Sourav 
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
In this paper we construct a cyclically invariant Boolean function whose sensitivity is Theta(n(1/3)). This result answers two previously published questions. Turan (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Omega(root n). Kenyon and Kutin (2004) asked whether for a "nice" function the product of 0-sensitivity and 1-sensitivity is Omega(n). Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is Omega(n(1/3)). Hence for this class of functions sensitivity and block sensitivity are polynomially related.
Digital search trees with m trees: Level polynomials and insertion costs
Authors: Prodinger Helmut 
Published: August 2021

Analysis of Algorithms
We adapt a novel idea of Cichon's related to Approximate Counting to the present instance of Digital Search Trees, by using m (instead of one) such trees. We investigate the level polynomials, which have as coefficients the expected numbers of data on a given level, and the insertion costs. The level polynomials can be precisely described, thanks to formulae from q-analysis. The asymptotics of expectation and variance of the insertion cost are fairly standard these days and done with Rice's method.
Avoidance colourings for small nonclassical Ramsey numbers
Authors: Burger Alewyn Petrus , Vuuren Jan H. 
Published: August 2021

Graphs and Algorithms
The irredundant Ramsey number s - s(m, n) [upper domination Ramsey number u - u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that IR(B) \textgreater= m or IR(R) \textgreater= n [Gamma (B) \textgreater= m or Gamma(R) \textgreater= n, respectively], where Gamma and IR denote respectively the upper domination number and the irredundance number of a graph. Furthermore, the mixed irredundant Ramsey number t = t(m, n) [mixed domination Ramsey number v = v(m, n), respectively] is the smallest natural number t [v, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order t [v, respectively], it holds that IR(B) \textgreater= m or beta(R) \textgreater= n [Gamma(B) \textgreater= m or beta(R) \textgreater= n, respectively], where beta denotes the independent domination number of a graph. These four classes of non-classical Ramsey numbers have previously been studied in the literature. In this paper we introduce a new Ramsey number w = w(m, n), called the irredundant-domination Ramsey number, which is the smallest natural number w such that in any red-blue edge colouring (R, B) of the complete graph of order w, it holds that IR(B) \textgreater= m or Gamma(R) \textgreater= n. A computer search is employed to determine complete sets of avoidance colourings of small order for these five classes of nonclassical Ramsey numbers. In the process the fifteen previously unknown Ramsey numbers t(4, 4) = 14, t(6, 3) = 17, u(4, 4) = 13, v(4, 3) = 8, v(4, 4) = 14, v(5, 3) = 13, v(6, 3) = 17, w(3, 3) = 6, w(3, 4) = w(4, 3) = 8, w(4, 4) = 13, w(3, 5) = w(5, 3) = 12 and w(3, 6) = w(6, 3) = 15 are established.
New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree
Authors: Zhang Xin , Wu Jian-Liang , Liu Guizhen 
Published: August 2021

Combinatorics
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K 4 is light in the family of 1-planar graphs of minimum degree 7, with its height at most 11.
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
Authors: Gaspers Serge , Liedloff Mathieu 
Published: August 2021

Graphs and Algorithms
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
On hamiltonian chain saturated uniform hypergraphs
Authors: Dudek Aneta , Zak Andrzej 
Published: August 2021

Graphs and Algorithms
We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family of k-uniform hamiltonian chain saturated hypergraphs with O(n(k-1/2)) edges.
Adaptive Identification of Sets of Vertices in Graphs
Authors: Junnila Ville 
Published: August 2021

Combinatorics
In this paper, we consider a concept of adaptive identification of vertices and sets of vertices in different graphs, which was recently introduced by Ben-Haim, Gravier, Lobstein and Moncel (2008). The motivation for adaptive identification comes from applications such as sensor networks and fault detection in multiprocessor systems. We present an optimal adaptive algorithm for identifying vertices in cycles. We also give efficient adaptive algorithms for identifying sets of vertices in different graphs such as cycles, king lattices and square lattices. Adaptive identification is also considered in Hamming spaces, which is one of the most widely studied graphs in the field of identifying codes.
Random Horn formulas and propagation connectivity for directed hypergraphs
Authors: Sloan Robert H. , Stasi Despina , Turán György 
Published: August 2021

Combinatorics
We consider the property that in a random definite Horn formula of size-3 clauses over n variables, where every such clause is included with probability p, there is a pair of variables for which forward chaining produces all other variables. We show that with high probability the property does not hold for p <= 1/(11n ln n), and does hold for p >= (5 1n ln n)/(n ln n).
A note on planar Ramsey numbers for a triangle versus wheels
Authors: Zhou Guofei , Chen Yaojun , Miao Zhengke , Pirzada Shariefuddin 
Published: August 2021

Graph Theory
For two given graphs G and H , the planar Ramsey number P R ( G; H ) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G , or its complement contains a copy of H . In this paper, we determine all planar Ramsey numbers for a triangle versus wheels.
On paths, trails and closed trails in edge-colored graphs
Authors: Gourvès Laurent , Lyra Adria , Martinhon Carlos A. , Monnot Jérôme 
Published: August 2021

Graph Theory
In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G(c) is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.
Random graphs with bounded maximum degree: asymptotic structure and a logical limit law
Authors: Koponen Vera 
Published: August 2021

General
For any fixed integer R≥2 we characterise the typical structure of undirected graphs with vertices 1,...,n and maximum degree R, as n tends to infinity. The information is used to prove that such graphs satisfy a labelled limit law for first-order logic. If R≥5 then also an unlabelled limit law holds.
The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree
Authors: Szymańska Edyta 
Published: August 2021

Discrete Algorithms
In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem, for every r≥q 3 we determine a threshold value depending on r such that the problem is NP-complete for c below the threshold, while for c strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity O(n^\lfloor 4/ε\rfloor+2\log n) with some ε>0. This algorithm becomes more efficient in the case of r=3,4,5 due to known Turán numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong k-coloring of 3-uniform hypergraphs H with minimum vertex degree at least c\binom|V(H)|-12, for some c, leaving a gap for k≥q 5 which vanishes as k→ ∞.
Probe interval graphs and probe unit interval graphs on superclasses of cographs
Authors: Bonomo Flavia , Durán Guillermo , Grippo Luciano N. , Safe Martın D. 
Published: August 2021

Graph Theory
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe G) graphs with disconnected complement for every graph class G with a companion.
Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs
Authors: Gosselin Shonda , Szymański Andrzej , Wojda Adam Pawel 
Published: August 2021

Combinatorics
A \em cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form \F,F^θ,F^θ², \ldots, F^θ^q-1\ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of V_n-1, we let \mathcalKₙ^(K) denote the hypergraph ≤ft(Vₙ, \bigcup_k∈ K Vₙ\choose k\right). In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic q-partition of \mathcalKₙ^(V_k). In particular, we prove that if p is prime then there is a cyclic p^α-partition of \mathcalK^(Vₖ)ₙ if and only if p^α + β divides n, where β = \lfloor \logₚ k\rfloor. As an application of this result, we obtain two sufficient conditions on n₁,n₂,\ldots,n_t, k, α and a prime p for the existence of a cyclic p^α-partition of the complete t-partite k-uniform hypergraph \mathcal K^(k)_n₁,n₂,\ldots,n_t.