bluuebunny/crossref_metadata_2025 huggingface dataset:
On-Line List Colouring of Complete Multipartite Graphs
Authors: Kim Seog-Jin , Kwon Young Soo , Liu Daphne Der-Fen , Zhu Xuding
Published: January 2020

The Ohba Conjecture says that every graph $G$ with $|V(G)| \le 2 \chi(G)+1$ is chromatic choosable. This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for $k \ge 3$, the complete multipartite graph $K_{2\star (k-1), 3}$ is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph $G$ with $|V(G)| \le 2 \chi(G)$ is on-line chromatic choosable. We present an explicit strategy to show  that for any positive integer $k$, the graph $K_{2\star k}$ is on-line chromatic-choosable.  We then present a minimal function $g$ for which the graph $K_{2 \star (k-1), 3}$ is on-line $g$-choosable.
On the Number of $F$-Matchings in a Tree
Authors: Law Hiu-Fai
Published: January 2020

We prove that for any integers $k,m>0$ and any tree $F$ with at least one edge, there exists a tree whose number of $F$-matchings is congruent to $k$ modulo $m$ as well as an analogous result for induced $F$-matchings. This answers a question of Alon, Haber and Krivelevich (The number of $F$-matchings in almost every tree is a zero residue, Electron. J. Combin. 18 (2011), #P30).
Integral Sets and Cayley Graphs of Finite Groups
Authors: Alperin Roger C. , Peterson Brian L.
Published: January 2020

Integral sets of finite groups are discussed and related to the integral Cayley graphs. The Boolean algebra of integral sets are determined for dihedral group and finite abelian groups. We characterize the finite abelian groups as those finite groups where the Boolean algebra generated by  integral sets equals  the Boolean algebra generated by its subgroups.
Sequences Containing No 3-Term Arithmetic Progressions
Authors: Dybizbański Janusz
Published: January 2020

A subsequence of the sequence $(1,2,...,n)$ is called a 3-$AP$-free sequence if it does not contain any three term arithmetic progression. By $r(n)$ we denote the length of the longest such 3-$AP$-free sequence. The exact values of the function $r(n)$ were known, for $n\leq 27$ and $41\leq n \leq 43$. In the present paper we determine, with a use of computer, the exact values, for all $n\leq 123$. The value $r(122)=32$ shows that the Szekeres' conjecture holds for $k=5$.
Rainbow Matchings in $r$-Partite $r$-Graphs
Authors: Aharoni Ron , Berger Eli
Published: January 2020

Given a collection of matchings ${\cal M} = (M_1, M_2, \ldots, M_q)$ (repetitions allowed), a matching $M$ contained in $\bigcup {\cal M}$ is said to be $s$-rainbow for ${\cal M}$ if it contains representatives from $s$ matchings $M_i$ (where each edge is allowed to represent just one $M_i$). Formally, this means that there is a function $\phi: M \to [q]$ such that $e \in M_{\phi(e)}$ for all $e \in M$, and $|Im(\phi)|\ge s$. Let $f(r,s,t)$ be the maximal $k$ for which there exists a set of $k$ matchings of size $t$ in some $r$-partite hypergraph, such that there is no $s$-rainbow matching of size $t$. We prove that $f(r,s,t)\ge 2^{r-1}(s-1)$, make the conjecture that equality holds for all values of $r,s$ and $t$ and prove the conjecture when $r=2$ or $s=t=2$. In the case $r=3$, a stronger conjecture is that in a $3$-partite $3$-graph if all vertex degrees in one side (say $V_1$) are strictly larger than all vertex degrees in the other two sides, then there exists a matching of $V_1$. This conjecture is at the same time also a strengthening of a famous conjecture, described below, of Ryser, Brualdi and Stein. We prove a weaker version, in which the degrees in $V_1$ are at least twice as large as the degrees in the other sides. We also formulate a related conjecture on edge colorings of $3$-partite $3$-graphs and prove a similarly weakened version.
Identifying Vertex Covers in Graphs
Authors: Henning Michael A , Yeo Anders
Published: January 2020

An identifying vertex cover in a graph $G$ is a subset $T$ of vertices in $G$ that has a nonempty intersection with every edge of $G$ such that $T$ distinguishes the edges, that is, $e \cap T \ne \emptyset$ for every edge $e$ in $G$ and $e \cap T \ne f \cap T$ for every two distinct edges $e$ and $f$ in $G$. The identifying vertex cover number $\tau_D(G)$ of $G$ is the minimum size of an identifying vertex cover in $G$. We observe that $\tau_D(G) + \rho(G) = |V(G)|$, where $\rho(G)$ denotes the packing number of $G$. We conjecture that if $G$ is a graph of order $n$ and size $m$ with maximum degree $\Delta$, then $\tau_D(G) \le \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m$. If the conjecture is true, then the bound is best possible for all $\Delta \ge 1$. We prove this conjecture when $\Delta \ge 1$ and $G$ is a $\Delta$-regular graph. The three known Moore graphs of diameter two, namely the $5$-cycle, the Petersen graph and the Hoffman-Singleton graph, are examples of regular graphs that achieves equality in the upper bound. We also prove this conjecture when $\Delta \in \{2,3\}$.
On $Q$-Polynomial Association Schemes of Small Class
Authors: Suda Sho
Published: January 2020

We show an inequality involving the third largest or second smallest dual eigenvalues of $Q$-polynomial association schemes of class at least three. Also we characterize dual-tight $Q$-polynomial association schemes of class three. Our method is based on tridiagonal matrices and can be applied to distance-regular graphs as well.
Uniquely $K_r$-Saturated Graphs
Authors: Hartke Stephen G. , Stolee Derrick
Published: January 2020

A graph $G$ is uniquely $K_r$-saturated if it contains no clique with $r$ vertices and if for all edges $e$ in the complement, $G+e$ has a unique clique with $r$ vertices. Previously, few examples of uniquely $K_r$-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs.  We find several new uniquely $K_r$-saturated graphs with $4 \leq r \leq 7$, as well as two new infinite families based on Cayley graphs for $\mathbb{Z}_n$ with a small number of generators.
Biembeddings of Metacyclic Groups and Triangulations of Orientable Surfaces by Complete Graphs
Authors: Grannell Michael John , Knor Martin
Published: January 2020

For each integer $n\ge 3$, $n\ne 4$, for each odd integer $m\ge 3$, and for any $\lambda\in\Bbb Z_n$ of (multiplicative) order $m'$ where $m'\mid m$, we construct a biembedding of Latin squares in which one of the squares is the Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$. This extends the spectrum of Latin squares known to be biembeddable.The best existing lower bounds for the number of triangular embeddings of a complete graph $K_z$ in an orientable surface are of the form $z^{z^2(a-o(1))}$ for suitable positive constants $a$ and for restricted infinite classes of $z$. Using embeddings of $\mathbb{Z}_3\ltimes_{\lambda}\mathbb{Z}_n$, we extend this lower bound to a substantially larger class of values of $z$.
Further Analysis on the Total Number of Subtrees of Trees
Authors: Li Shuchao , Wang Shujing
Published: January 2020

When considering the total number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts that correlate to some other graphical indices in applications. Along this line, it is interesting to study that over some types of trees with a given order, which trees minimize or maximize this number.  Here are our main results:  (1) The extremal tree which minimizes the total number of subtrees among $n$-vertex trees with $k$ pendants is characterized.  (2) The extremal tree which maximizes (resp. minimizes) the total number of subtrees among $n$-vertex trees with a given bipartition is characterized.  (3) The extremal tree which minimizes the total number of subtrees among the set of all $q$-ary trees with $n$ non-leaf vertices is identified.  (4) The extremal $n$-vertex tree with given domination number maximizing the total number of subtrees is characterized.
On Log-concavity of a Class of Generalized Stirling Numbers
Authors: Zhao Feng-Zhen
Published: January 2020

This paper considers the generalized Stirling numbers of the first and second kinds. First, we show that the sequences of the above generalized Stirling numbers are both log-concave under some mild conditions. Then, we show that some polynomials related to the above generalized Stirling numbers are $q$-log-concave or $q$-log-convex under suitable conditions. We further discuss the log-convexity of some linear transformations related to generalized Stirling numbers of the first kind.
The Valuations of the Near Polygon ${\Bbb G}_n$
Authors: De Bruyn Bart
Published: January 2020

We show that every valuation of the near $2n$-gon ${\Bbb G}_n$, $n \geq 2$, is induced by a unique classical valuation of the dual polar space $DH(2n-1,4)$ into which ${\Bbb G}_n$ is isometrically embeddable.
Perfect 1-Factorisations of Circulants with Small Degree
Authors: Herke Sarada , Maenhaut Barbara
Published: January 2020

A $1$-factorisation of a graph $G$ is a decomposition of $G$ into edge-disjoint $1$-factors (perfect matchings), and a perfect $1$-factorisation is a $1$-factorisation in which the union of any two of the $1$-factors is a Hamilton cycle.  We consider the problem of the existence of perfect $1$-factorisations of even order circulant graphs with small degree.  In particular, we characterise the $3$-regular circulant graphs that admit a perfect $1$-factorisation and we solve the existence problem for a large family of $4$-regular circulants.  Results of computer searches for perfect  $1$-factorisations of $4$-regular circulant graphs of orders up to $30$ are provided and some problems are posed.
Generalized Ramsey Numbers for Graphs with Three Disjoint Cycles Versus a Complete Graph
Authors: Fujita Shinya
Published: January 2020

Let $\mathcal{F},\mathcal{G}$ be families of graphs. The generalized Ramsey number $r(\mathcal{F},\mathcal{G})$ denotes the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $F\in\mathcal{F}$ or a blue $G\in \mathcal{G}$. Let $\mathcal{F}(k)$ be a family of graphs with $k$ vertex-disjoint cycles.In this paper, we deal with the case where $\mathcal{F}=\mathcal{F}(3),\mathcal{G}=\{K_t\}$ for some fixed $t$ with $t\ge 2$, and prove that $r(\mathcal{F}(3),\mathcal{G})=2t+5$.
Mixing Time for a Random Walk on Rooted Trees
Authors: Fulman Jason
Published: January 2020

We define an analog of Plancherel measure for the set of rooted unlabeled trees on $n$ vertices, and a Markov chain which has this measure as its stationary distribution. Using the combinatorics of commutation relations, we show that order $n^2$ steps are necessary and suffice for convergence to the stationary distribution.
Distinguishing Trees in Linear Time
Authors: Seara Carlos , Lozano Antoni , Mora Mercè
Published: January 2020

A graph is said to be $d$-distinguishable if there exists a $d$-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph $G$ is the smallest number $d$ for which $G$ is $d$-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known $O(n\log n)$ time algorithm.
On the Cartesian Product of Non Well-Covered Graphs
Authors: Hartnell Bert L , Rall Douglas F
Published: January 2020

A graph is well-covered if every maximal independent set has the same cardinality, namely the vertex independence number.  We answer a question of Topp and Volkmann and prove that if the Cartesian product of two graphs is well-covered, then at least one of them must be well-covered.
Isosceles Sets
Authors: Ionin Yury J.
Published: January 2020

In 1946, Paul Erdős posed a problem of determining the largest possible cardinality of an isosceles set, i.e., a set of points in plane or in space, any three of which form an isosceles triangle. Such a question can be asked for any metric space, and an upper bound ${n+2\choose 2}$ for the Euclidean space ${\Bbb E}^{n}$ was found by Blokhuis. This upper bound is known to be sharp for $n=1$, 2, 6, and 8. We will consider Erdős' question for the binary Hamming space $H_{n}$ and obtain the following upper bounds on the cardinality of an isosceles subset $S$ of $H_{n}$: if there are at most two distinct nonzero distances between points of $S$, then $|S|\leq{n+1\choose 2}+1$; if, furthermore, $n\geq 4$, $n\ne 6$, and, as a set of vertices of the $n$-cube, $S$ is contained in a hyperplane, then $|S|\leq{n\choose 2}$; if there are more than two distinct nonzero distances between points of $S$, then $|S|\leq{n\choose 2}+1$. The first bound is sharp if and only if $n=2$ or $n=5$; the other two bounds are sharp for all relevant values of $n$, except the third bound for $n=6$, when the sharp upper bound is 12. We also give the exact answer to the Erdős problem for ${\Bbb E}^{n}$ with $n\leq 7$ and describe all isosceles sets of the largest cardinality in these dimensions.
$(2,m,n)$-groups with Euler characteristic equal to $-2^as^b$
Authors: Gill Nick
Published: January 2020

We study those $(2,m,n)$-groups which are almost simple and for which the absolute value of the Euler characteristic is a product of two prime powers. All such groups which are not isomorphic to $PSL_2(q)$ or $PGL_2(q)$ are completely classified.
Combinatorial Logarithm and Point-Determining Cographs
Authors: Li Ji
Published: January 2020

We obtain the reduced form of the “combinatorial logarithm” Ω by looking at bijections related to connected point-determining cographs and connected co-point-determining graphs.
Application of graph combinatorics to rational identities of type $A$
Authors: Boussicault Adrien , Féray Valentin
Published: January 2020

To a word $w$, we associate the rational function $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. The main object, introduced by C. Greene to generalize identities linked to the Murnaghan-Nakayama rule, is a sum of its images by certain permutations of the variables. The sets of permutations that we consider are the linear extensions of oriented graphs. We explain how to compute this rational function, using the combinatorics of the graph $G$. We also establish a link between an algebraic property of the rational function (the factorization of the numerator) and a combinatorial property of the graph (the existence of a disconnecting chain).
On Commuting Graphs for Elements of Order 3 in Symmetric Groups
Authors: Nawawi Athirah , Rowley Peter
Published: January 2020

The commuting graph $\mathcal{C}(G,X)$, where $G$ is a group and $X$ is a subset of $G$, is the graph with vertex set $X$ and distinct vertices being joined by an edge whenever they commute. Here the diameter of $\mathcal{C}(G,X)$ is studied when $G$ is a symmetric group and $X$ a conjugacy class of elements of order $3$.
Improved Upper Bounds for Planarization and Series-Parallelization of Degree-Bounded Graphs
Authors: Edwards Keith , Farr Graham
Published: January 2020

We study the number of vertices which must be removed from a graph in order to make it planar or series-parallel. We give improved upper bounds on the number of vertices required to planarize graphs of bounded average degree $d$, and for small $d$ also an improved bound for series-parallelization. The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. The above bounds on planarization yield improved bounds for the coefficient of fragmentability of the class of connected graphs of average degree at most $d$.As an application we give an improved bound on the size of regular expressions representing deterministic finite automata.
A Positive Combinatorial Formula for the Complexity of the $q$-Analog of the $n$-Cube
Authors: Srinivasan Murali Krishna
Published: January 2020

The number of spanning trees of a graph $G$ is called the complexity of $G$. A classical result in algebraic graph theory explicitly diagonalizes the Laplacian of the $n$-cube $C(n)$  and yields, using the Matrix-Tree theorem, an explicit formula for $c(C(n))$. In this paper we explicitly block diagonalize the Laplacian of the $q$-analog $C_q(n)$ of $C(n)$ and use this, along with the Matrix-Tree theorem, to give a positive combinatorial formula for $c(C_q(n))$. We also explain how setting $q=1$ in the formula for $c(C_q(n))$ recovers the formula for $c(C(n))$.
Landau's and Rado's Theorems and Partial Tournaments
Authors: Brualdi Richard A. , Kiernan Kathleen
Published: January 2020

Using Rado's theorem for the existence of an independent transversal of family of subsets of a set on which a matroid is defined, we give a proof of Landau's theorem for the existence of a tournament with a prescribed degree sequence. A similar approach is used to determine when a partial tournament can be extended to a tournament with a prescribed degree sequence.
Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms
Authors: Sawada Joe , Li Roy
Published: January 2020

By considering a permutation representation for  stamp-foldings and semi-meanders we construct tree-like data structures that will allow us to generate these objects in constant amortized time.  Additionally, by maintaining the wind-factor and applying an additional optimization, the algorithm for semi-meanders can be modified to produce the fastest known algorithm to generate open meanders.
Graphs with Large Distinguishing Chromatic Number
Authors: Cavers Michael , Seyffarth Karen
Published: January 2020

The distinguishing chromatic number $\chi_D(G)$ of a graph $G$ is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. For a graph $G$ of order $n$, it is clear that $1\leq\chi_D(G)\leq n$, and it has been shown that $\chi_D(G)=n$ if and only if $G$ is a complete multipartite graph. This paper characterizes the graphs $G$ of order $n$ satisfying $\chi_D(G)=n-1$ or $\chi_D(G)=n-2$.
Distance-Regular Graphs with a Relatively Small Eigenvalue Multiplicity
Authors: Koolen Jack H. , Kim Joohyung , Park Jongyook
Published: January 2020

Godsil showed that if $\Gamma$ is a distance-regular graph with diameter $D \geq 3$ and valency $k \geq 3$, and $\theta$ is an eigenvalue of $\Gamma$ with multiplicity $m \geq 2$, then $k \leq\frac{(m+2)(m-1)}{2}$.In this paper we will give a refined statement of this result. We show that if $\Gamma$ is a distance-regular graph with diameter $D \geq 3$, valency $k \geq 2$ and an eigenvalue $\theta$ with multiplicity $m\geq 2$, such that $k$ is close to $\frac{(m+2)(m-1)}{2}$, then $\theta$ must be a tail. We also characterize the distance-regular graphs with diameter $D \geq 3$, valency $k \geq 3$ and an eigenvalue $\theta$ with multiplicity $m \geq 2$ satisfying $k= \frac{(m+2)(m-1)}{2}$.
A Method for Determining the Mod-$2^k$ Behaviour of Recursive Sequences, with Applications to Subgroup Counting
Authors: Kauers M. , Krattenthaler C. , Müller T. W.
Published: January 2020

We present a method to obtain congruences modulo powers of $2$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fuß--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of $2$.
The Enumeration of Three Pattern Classes using Monotone Grid Classes
Authors: Albert Michael , Atkinson Mike , Brignall Robert
Published: January 2020

The structure of the three pattern classes defined by the sets of forbidden permutations $\{2143, 4321\}$, $\{2143, 4312\}$ and $\{1324, 4312\}$ is determined using the machinery of monotone grid classes. This allows the permutations in these classes to be described in terms of simple diagrams and regular languages and, using this, the rational generating functions which enumerate these classes are determined.
Rainbow Matchings of Size $\delta(G)$ in Properly Edge-Colored Graphs
Authors: Diemunsch Jennifer , Ferrara Michael , Lo Allan , Moffatt Casey , Pfender Florian , Wenger Paul S
Published: January 2020

A rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function $f(\delta)$ such that a properly edge-colored graph $G$ with minimum degree $\delta$ and order at least $f(\delta)$ must have a rainbow matching of size $\delta$. We answer this question in the affirmative; an extremal approach yields that $f(\delta) = 98\delta/23< 4.27\delta$ suffices. Furthermore, we give an $O(\delta(G)|V(G)|^2)$-time algorithm that generates such a matching in a properly edge-colored graph of order at least $6.5\delta$.
The Canada Day Theorem
Authors: Gomez Daniel , Lundmark Hans , Szmigielski Jacek
Published: January 2020

The Canada Day Theorem is an identity involving sums of $k \times k$ minors of an arbitrary $n \times n$ symmetric matrix. It was discovered as a by-product of the work on so-called peakon solutions of an integrable nonlinear partial differential equation proposed by V. Novikov. Here we present another proof of this theorem, which explains the underlying mechanism in terms of the orbits of a certain abelian group action on the set of all $k$-edge matchings of the complete bipartite graph $K_{n,n}$.
The Rotor-Router Group of Directed Covers of Graphs
Authors: Huss Wilfried , Sava Ecaterina
Published: January 2020

A rotor-router walk is a deterministic version of a random walk, in which the walker is routed to each of the neighbouring vertices in some fixed cyclic order. We consider here directed covers of graphs (called also periodic trees) and we study several quantities related to rotor-router walks on directed covers. The quantities under consideration are: order of the rotor-router group, order of the root element in the rotor-router group and the connection with random walks.
Traces of Uniform Families of Sets
Authors: Patkós Balázs
Published: January 2020

The trace of a set $F$ on a another set $X$ is $F|_X=F \cap X$ and the trace of a family ${\cal F}$ of sets on $X$ is ${\cal F}_X=\{F|_X: F \in {\cal F}\}$. In this note we prove that if a $k$-uniform family ${\cal F} \subset {[n] \choose k}$ has the property that for any $k$-subset $X$ the trace ${\cal F}|_X$ does not contain a maximal chain (a family $C_0 \subset C_1 \subset ... \subset C_k$ with $|C_i|=i$), then $|{\cal F}| \leq {n-1 \choose k-1}$. This bound is sharp as shown by $\{F \in {[n] \choose k}, 1 \in F\}$. Our proof gives also the stability of the extremal family.
Matchings, Cycle Bases, and the Maximum Genus of a Graph
Authors: Kotrbčík Michal , Škoviera Martin
Published: January 2020

We study the interplay between the maximum genus of a graph and bases of its cycle space via the corresponding intersection graph. Our main results show that the matching number of the intersection graph is independent of the basis precisely when the graph is upper-embeddable, and completely describe the range of matching numbers when the graph is not upper-embeddable. Particular attention is paid to cycle bases consisting of fundamental cycles with respect to a given spanning tree. For $4$-edge-connected graphs, the intersection graph with respect to any spanning tree (and, in fact, with respect to any basis) has either a perfect matching or a matching missing exactly one vertex. We show that if a graph is not $4$-edge-connected, different spanning trees may lead to intersection graphs with different matching numbers. We also show that there exist $2$-edge connected graphs for which the set of values of matching numbers of their intersection graphs contains arbitrarily large gaps.
An Enumeration of Flags in Finite Vector Spaces
Authors: Vinroot C. Ryan
Published: January 2020

By counting flags in finite vector spaces, we obtain a $q$-multinomial analog of a recursion for $q$-binomial coefficients proved by Nijenhuis, Solow, and Wilf.  We use the identity to give a combinatorial proof of a known recurrence for the generalized Galois numbers.
Barred Preferential Arrangements
Authors: Ahlbach Connor , Usatine Jeremy , Pippenger Nicholas
Published: January 2020

A preferential arrangement of a set is a total ordering of the elements of that set with ties allowed. A barred preferential arrangement is one in which the tied blocks of elements are ordered not only amongst themselves but also with respect to one or more bars. We present various combinatorial identities for $r_{m,\ell}$, the number of barred preferential arrangements of $\ell$ elements with $m$ bars, using both algebraic and combinatorial arguments. Our main result is an expression for $r_{m,\ell}$ as a linear combination of the $r_k$ ($= r_{0,k}$, the number of unbarred preferential arrangements of $k$ elements) for  $\ell\le k\le\ell+m$. We also enumerate those arrangements in which the sections, into which the blocks are segregated by the bars, must be nonempty. We conclude with an expression of $r_\ell$ as an infinite series that is both convergent and asymptotic.
The (Signless Laplacian) Spectral Radii of Connected Graphs with Prescribed Degree Sequences
Authors: Liu Muhuo
Published: January 2020

In this paper, some new properties are presented to the extremal graphs with largest (signless Laplacian) spectral radii in the set of all the connected graphs with prescribed degree sequences, via which we determine all the extremal tricyclic graphs. in the class of connected tricyclic graphs with prescribed degree sequences, and  we also prove some majorization theorems of tricyclic graphs with special restrictions.
Hamilton Saturated Hypergraphs of Essentially Minimum Size
Authors: Ruciński Andrzej , Żak Andrzej
Published: January 2020

For $1\leq \ell< k$,  an $\ell$-overlapping cycle is a $k$-uniform hypergraph in which, for some cyclic vertex ordering, every edge consists of $k$ consecutive vertices and every two consecutive edges share exactly $\ell$ vertices. A $k$-uniform hypergraph $H$ is $\ell$-Hamiltonian saturated, $1\le \ell\le k-1$, if $H$ does not contain an $\ell$-overlapping Hamiltonian cycle $C^{(k)}_n(\ell)$ but every hypergraph obtained from $H$ by adding one more edge does contain $C^{(k)}_n(\ell)$. Let $sat(n,k,\ell)$ be the smallest number of edges in an $\ell$-Hamiltonian saturated $k$-uniform hypergraph on $n$ vertices. Clark and Entringer proved in 1983 that $sat(n,2,1)=\lceil \tfrac{3n}2\rceil$ and the second author showed recently that $sat(n,k,k-1)=\Theta(n^{k-1})$ for every $k\ge2$. In this paper we prove that $sat(n,k,\ell)=\Theta(n^{\ell})$ for $\ell=1$ as well as for all $k\ge5$ and $\ell\ge0.8k$.
Partially Ordinal Sums and $P$-partitions
Authors: Du Daniel K. , Hou Qing-Hu
Published: January 2020

We present a method of computing the generating function $f_P(\textbf{x})$ of $P$-partitions of a poset $P$. The idea is to introduce two kinds of transformations on posets and compute $f_P(\textbf{x})$ by recursively applying these transformations. As an application, we consider the partially ordinal sum $P_n$ of $n$ copies of a given poset, which generalizes both the direct sum and the ordinal sum. We show that the sequence $\{f_{P_n}(\textbf{x})\}_{n\ge 1}$ satisfies a finite system of recurrence relations with respect to $n$. We illustrate the method by several examples, including a kind of $3$-rowed posets and the multi-cube posets.
A Note on Forbidding Clique Immersions
Authors: DeVos Matt , McDonald Jessica , Mohar Bojan , Scheide Diego
Published: January 2020

Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of the corresponding rough structure theorem for graphs without $K_t$-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without $\vec{K}_t$-immersions, where $\vec{K}_t$ denotes the bidirected complete digraph of order $t$.
Statistical Distributions and $q$-Analogues of $k$-Fibonacci Numbers
Authors: Goyt Adam M , Keller Brady L , Rue Jonathan E
Published: January 2020

We study q-analogues of k-Fibonacci numbers that arise from weighted tilings of an $n\times1$ board with tiles of length at most k.  The weights on our tilings arise naturally out of distributions of permutations statistics and set partitions statistics.  We use these q-analogues to produce q-analogues of identities involving k-Fibonacci numbers.  This is a natural extension of results of the first author and Sagan on set partitions and the first author and Mathisen on permutations.  In this paper we give general q-analogues of k-Fibonacci identities for arbitrary weights that depend only on lengths and locations of tiles.  We then determine weights for specific permutation or set partition statistics and use these specific weights and the general identities to produce specific identities.
The Complexity of Generalized Domino Tilings
Authors: Pak Igor , Yang Jed
Published: January 2020

Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial.  We prove a variety of hardness results (both NP- and #P-completeness) for different generalizations of dominoes in three and higher dimensions.
Two Permutation Classes related to the Bubble Sort Operator
Authors: Barnabei Marilena , Bonetti Flavio , Silimbani Matteo
Published: January 2020

We introduce the Dual Bubble Sort operator $\hat{B}$ (a sorting algorithm such that, if $\sigma=\alpha\,1\,\beta$ is a permutation, then $\hat{B}(\sigma)=1\,\alpha\,\hat{B} (\beta)$) and consider the set of permutations sorted by the composition $\hat{B}B$, where $B$ is the classical Bubble Sort operator. We show that this set is a permutation class and we determine the generating function of the descent and fixed point distributions over this class. Afterwards, we characterize the same distributions over the set of permutations that are sorted by both $\hat{B}^2$ and $B^2$.
Congruences for $q$-Lucas Numbers
Authors: Pan Hao
Published: January 2020

For $\alpha,\beta,\gamma,\delta\in{\mathbb Z}$ and ${\rm\nu}=(\alpha,\beta,\gamma,\delta)$, the $q$-Fibonacci numbers are given by$$F_0^{{\rm\nu}}(q)=0,\ F_1^{{\rm\nu}}(q)=1\text{ and }F_{n+1}^{{\rm\nu}}(q)=q^{\alpha n-\beta}F_{n}^{{\rm\nu}}(q)+q^{\gamma n-\delta}F_{n-1}^{{\rm\nu}}(q)\text{ for }n\geq 1.$$And define the $q$-Lucas number $L_{n}^{{\rm\nu}}(q)=F_{n+1}^{{\rm\nu}}(q)+q^{\gamma-\delta}F_{n-1}^{{\rm\nu}_*}(q)$, where ${\rm\nu}_*=(\alpha,\beta-\alpha,\gamma,\delta-\gamma)$. Suppose that $\alpha=0$ and $\gamma$ is prime to $n$, or $\alpha=\gamma$ is prime to $n$. We prove that$$L_{n}^{{\rm\nu}}(q)\equiv(-1)^{\alpha(n+1)}\pmod{\Phi_n(q)}$$for $n\geq 3$, where $\Phi_n(q)$ is the $n$-th cyclotomic polynomial. A similar congruence for $q$-Pell-Lucas numbers is also established.
Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters
Authors: Barrett Wayne , Fallat Shaun M. , Hall H. Tracy , Hogben Leslie
Published: January 2020

We establish the bounds $\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are  the Nordhaus-Gaddum sum upper bound multipliers, i.e., $\nu(G)+\nu(\overline{G})\le b_\nu |G|$ and $\xi(G)+\xi(\overline{G})\le b_\xi | G|$ for all graphs $G$, and $\nu$ and $\xi$ are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for $\nu$ and $\xi$ is conjectured to be $|G| - 2$, and if these parameters are replaced by the maximum nullity $M(G)$, this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.
Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness
Authors: Bender Edward A. , Canfield E. Rodney , Gao Zhicheng
Published: January 2020

We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity $k$, all accurate to $o(1)$.
Degrees in Oriented Hypergraphs and Ramsey p-Chromatic Number
Authors: Caro Yair , Hansberg Adriana
Published: January 2020

The family $D(k,m)$ of graphs having an orientation such that for every vertex $v \in V(G)$ either (outdegree) $\deg^+(v) \le k$ or (indegree) $\deg^-(v) \le m$ have been investigated recently in several papers because of the role $D(k,m)$ plays in the efforts to estimate the maximum directed cut in digraphs and the minimum cover of digraphs by directed cuts. Results concerning the chromatic number of graphs in the family $D(k,m)$ have been obtained via the notion of $d$-degeneracy of graphs. In this paper we consider a far reaching generalization of the family $D(k,m)$, in a complementary form, into the context of $r$-uniform hypergraphs, using a generalization of Hakimi's theorem to $r$-uniform hypergraphs and by showing some tight connections with the well known Ramsey numbers for hypergraphs.
Roman Domination Number of the Cartesian Products of Paths and Cycles
Authors: Pavlič Polona , Žerovnik Janez
Published: January 2020

Roman domination is an historically inspired variety of domination in graphs, in which vertices are assigned a value from the set $\{0,1,2\}$ in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. Using an algebraic approach we  present an $O(C)$-time algorithm for computing the Roman domination numbers of special classes of graphs called polygraphs, which include rotagraphs and fasciagraphs. Using this algorithm we determine formulas for the Roman domination numbers of the Cartesian products of the form $P_n\Box P_k$, $P_n\Box C_k$, for $k\leq8$ and $n \in {\mathbb N}$, and $C_n\Box P_k$ and $C_n\Box C_k$, for $k\leq 6$ and $n \in {\mathbb N}$, for paths $P_n$ and cycles $C_n$. We also find all special graphs called Roman graphs in these families of graphs.
Symmetry in Gardens of Eden
Authors: Hartman Christiaan , Heule Marijn J. H. , Kwekkeboom Kees , Noels Alain
Published: January 2020

Conway's Game of Life has inspired enthusiasts to search for a wide range of patterns for this classic cellular automaton. One important challenge in this context is finding the smallest Garden of Eden (GoE), a state without a predecessor. We take up this challenge by applying two techniques. First, we focus on GoEs that contain a symmetry. This significantly reduces the size of the search space for interesting sizes of the grid. Second, we implement the search using incremental satisfiability solving to check thousands of states per second. By combining these techniques, we broke several records regarding GoEs: the fewest defined cells, the smallest bounding box, and the lowest living density. Furthermore, we established a new lower bound for the smallest GoE.
Sudoku Graphs are Integral
Authors: Sander Torsten
Published: January 2020

Sudoku graphs have only 5 or 6 distinct eigenvalues and all of them are integers. Moreover, the associated eigenspaces admit bases with entries from the set $\{0, 1, -1\}$.
A Note on $K_{\Delta+1}^-$-Free Precolouring with $\Delta$ Colours
Authors: Rackham Tom
Published: January 2020

Let $G$ be a simple graph of maximum degree $\Delta \geq 3$, not containing $K_{\Delta + 1}$, and ${\cal L}$ a list assignment to $V(G)$ such that $|{\cal L}(v)| = \Delta$ for all $v \in V(G)$. Given a set $P \subset V(G)$ of pairwise distance at least $d$ then Albertson, Kostochka and West (2004) and Axenovich (2003) have shown that every ${\cal L}$-precolouring of $P$ extends to a ${\cal L}$-colouring of $G$ provided $d \geq 8$. Let $K_{\Delta + 1}^-$ denote the graph $K_{\Delta + 1}$ with one edge removed. In this paper, we consider the problem above and the effect on the pairwise distance required when we additionally forbid either $K_{\Delta + 1}^-$ or $K_{\Delta}$ as a subgraph of $G$. We have the corollary that an extra assumption of 3-edge-connectivity in the above result is sufficient to reduce this distance from $8$ to $4$. This bound is sharp with respect to both the connectivity and distance. In particular, this corrects the results of Voigt (2007, 2008) for which counterexamples are given.
On the Sprague-Grundy Values of the $\mathcal{F}$-Wythoff Game
Authors: Jiao Yang
Published: January 2020

We examine the Sprague-Grundy values of $\mathcal{F}$-Wythoff, a restriction of Wythoff's game introduced by Ho, where the integer ratio of the pile sizes must be preserved if the same number of tokens is removed from both piles. We answer two conjectures raised by Ho. First, we show that each column of Sprague-Grundy values is ultimately additively periodic. Second, we prove that every diagonal of Sprague-Grundy values contains all the nonnegative integers. We also investigate the asymptotic behavior of the sequence of positions attaining a given Sprague-Grundy value.
A Note on Packing Graphs Without Cycles of Length up to Five
Authors: Görlich Agnieszka , Żak Andrzej
Published: January 2020

The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster: if a graph $G$ is a non-star graph without cycles of length $m \leq 4$ then $G$ is a subgraph of its complement. So far the best result concerning this conjecture is that every non-star graph $G$ without cycles of length $m \leq 6$ is a subgraph of its complement. In this note we show that $m\leq 6$ can be replaced by $m \leq 5$.
Unit Distance Graphs with Ambiguous Chromatic Number
Authors: Payne Michael S.
Published: January 2020

First László Székely and more recently Saharon Shelah and Alexander Soifer have presented examples of infinite graphs whose chromatic numbers depend on the axioms chosen for set theory. The existence of such graphs may be relevant to the Chromatic Number of the Plane problem. In this paper we construct a new class of graphs with ambiguous chromatic number. They are unit distance graphs with vertex set ${\Bbb R}^n$, and hence may be seen as further evidence that the chromatic number of the plane might depend on set theory.
Counting Families of Mutually Intersecting Sets
Authors: Brouwer A. E. , Mills C. F. , Mills W. H. , Verbeek A.
Published: January 2020

We show that the number of maximal intersecting families on a 9-set equals 423295099074735261880, that the number of independent sets of the Kneser graph K(9,4) equals 366996244568643864340, and that the number of intersecting families on an 8-set and on a 9-set is 14704022144627161780744368338695925293142507520 and 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328 (roughly 1.255 . 10^91), respectively.
Product Dimension of Forests and Bounded Treewidth Graphs
Authors: Chandran L. Sunil , Mathew Rogers , Rajendraprasad Deepak , Sharma Roohani
Published: January 2020

The product dimension of a graph $G$ is defined as the minimum natural number $l$ such that $G$ is an induced subgraph of a direct product of $l$ complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and $k$-degenerate graphs. We show that every forest on $n$ vertices has product dimension at most $1.441 \log n + 3$. This improves the best known upper bound of $3 \log n$ for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on $n$ vertices with treewidth at most $t$ has product dimension at most $(t+2)(\log n + 1)$. We also show that every $k$-degenerate graph on $n$ vertices has product dimension at most $\lceil 5.545 k \log n \rceil + 1$. This improves the upper bound of  $32 k \log n$ for the same by Eaton and  Rődl.
The Hitting Time of Rainbow Connection Number Two
Authors: Heckel Annika , Riordan Oliver
Published: January 2020

In a graph $G$ with a given edge colouring, a rainbow path is a path all of whose edges have distinct colours. The minimum number of colours required to colour the edges of $G$ so that every pair of vertices is joined by at least one rainbow path is called the rainbow connection number $\mathrm{rc}(G)$ of the graph $G$. For any graph $G$, $\mathrm{rc}(G) \geqslant \mathrm{diam}(G)$. We will show that for the Erdős-Rényi random graph $\mathcal{G}(n,p)$ close to the diameter $2$ threshold, with high probability if $\mathrm{diam}(G)=2$ then $\mathrm{rc}(G)=2$. In fact, further strengthening this result, we will show that in the random graph process, with high probability the hitting times of diameter $2$ and of rainbow connection number $2$ coincide.
On Optimality of Designs with Three Distinct Eigenvalues
Authors: Faghihi M. R. , Ghorbani E. , Khosrovshahi G. B. , Tat S.
Published: January 2020

Let ${\cal D}_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$. Let $d\in{\cal D}_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$. The matrix $C(d)=R(d)-\frac{1}{k}N(d)N(d)^\top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $\mu_1(d),\ldots,\mu_{v-1}(d)$.Let ${\cal D}$ be the class of all binary designs of ${\cal D}_{v,b,k}$. We prove that if there is a design $d^*\in{\cal D}$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $d\in{\cal D}$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $d\in{\cal D}$, then for all $p>0$, $d^*$ minimizes $\left(\sum_{i=1}^{v-1}\mu_i(d)^{-p}\right)^{1/p}$ over $d\in{\cal D}$. In the context of optimal design theory, this means that if there is a design $d^*\in{\cal D}$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in ${\cal D}$, then $d^*$ is $\Phi_p$-optimal in ${\cal D}$ for all $p>0$. As an application, we demonstrate the $\Phi_p$-optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming.
Making a Graph Crossing-Critical by Multiplying its Edges
Authors: Beaudou Laurent , Hernández-Vélez César , Salazar Gelasio
Published: January 2020

A graph is crossing-critical if the removal of any of its edges decreases its crossing number. This work is motivated by the following question: to what extent is crossing-criticality a property that is inherent to the structure of a graph, and to what extent can it be induced on a noncritical graph by multiplying (all or some of) its edges? It is shown that if a nonplanar graph $G$ is obtained by adding an edge to a cubic polyhedral graph, and $G$ is sufficiently connected, then $G$ can be made crossing-critical by a suitable multiplication of edges.
On a Matrix Representation for Polynomially Recursive Sequences
Authors: Reutenauer Christophe
Published: January 2020

In this article we derive several consequences of a matricial characterization of P-recursive sequences. This characterization leads to canonical representations of these sequences. We show their uniqueness for a given sequence, up to similarity. We study their properties: operations, closed forms, d'Alembertian sequences, field extensions, positivity, extension of the sequence to $\mathbb Z$, difference Galois group.
Asymptotics of Some Convolutional Recurrences
Authors: Bender Edward A. , Daalhuis Adri B. Olde , Gao Zhicheng , Richmond L. Bruce , Wormald Nicholas
Published: January 2020

We study the asymptotic behavior of the terms in sequences satisfying recurrences of the form $a_n = a_{n-1} + \sum_{k=d}^{n-d} f(n,k) a_k a_{n-k}$ where, very roughly speaking, $f(n,k)$ behaves like a product of reciprocals of binomial coefficients. Some examples of such sequences from map enumerations, Airy constants, and Painlevé I equations are discussed in detail.
Graphs on Affine and Linear Spaces and Deuber Sets
Authors: Gunderson David S. , Lefmann Hanno
Published: January 2020

If $G$ is a large $K_k$-free graph, by Ramsey's theorem, a large set of vertices is independent. For graphs whose vertices are positive integers, much recent work has been done to identify what arithmetic structure is possible in an independent set. This paper addresses  similar problems: for graphs whose vertices are affine or linear spaces over a finite field,  and when the vertices of the graph are elements of an arbitrary Abelian group.
Constructing $5$-Configurations with Chiral Symmetry
Authors: Berman Leah Wrenn , Ng Laura
Published: January 2020

A $5$-configuration is a collection of points and straight lines in the Euclidean plane so that each point lies on five lines and each line passes through five points. We describe how to construct the first known family of $5$-configurations with chiral (that is, only rotational) symmetry, and prove that the construction works; in addition, the construction technique produces the smallest known geometric 5-configuration.
The Lowest-Degree Polynomial with Nonnegative Coefficients Divisible by the $n$-th Cyclotomic Polynomial
Authors: Steinberger John P.
Published: January 2020

We pose the question of determining the lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial $\Phi_n(x)$. We show this polynomial is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ where $p$ is the smallest prime dividing $n$ whenever $2/p > 1/q_1 + \cdots + 1/q_k$, where $q_1, \ldots, q_k$ are the other (distinct) primes besides $p$ dividing $n$. Determining the lowest-degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ remains open in the general case, though we conjecture the existence of values of $n$ for which this degree is, in fact, less than $(p-1)n/p$.
Circular Nim Games
Authors: Dufour Matthieu , Heubach Silvia
Published: January 2020

A circular Nim game is a two player impartial combinatorial game consisting of  $n$ stacks of tokens placed in a circle. A move consists of choosing $k$ consecutive stacks, and taking at least one token from one or more of the $k$ stacks.  The last player able to make a move wins.  We prove results on the structure of the losing positions for small $n$ and $k$ and pose some open questions for further investigations.
Enumeration of Unlabeled Directed Hypergraphs
Authors: Qian Jianguo
Published: January 2020

We consider the enumeration of unlabeled directed hypergraphs by using Pólya's counting theory and Burnside's counting lemma. Instead of characterizing the cycle index of the permutation group acting on the hyperarc set $A$, we treat each cycle in the disjoint cycle decomposition of a permutation $\rho$ acting on $A$ as an equivalence class (or orbit) of $A$ under the operation of the group generated by $\rho$. Compared to the cycle index method, our approach is  more effective in  dealing with the enumeration of directed hypergraphs. We deduce the explicit counting formulae for the unlabeled $q$-uniform and unlabeled general directed hypergraphs. The former generalizes the well known result for 2-uniform directed hypergraphs, i.e., for the ordinary directed graphs introduced by Harary and Palmer.