bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.
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.
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.
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$.
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))$.
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.
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.
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.
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.
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$.
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)$.
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.
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.
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.
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.
Constructions of Bipartite and Bipartite-regular Hypermaps
Authors: Duarte Rui 
Published: January 2020

A hypermap is bipartite if its set of flags can be divided into two parts A and B so that both A and B are the union of vertices, and consecutive vertices around an edge or a face are contained in alternate parts. A bipartite hypermap is bipartite-regular if its set of automorphisms is transitive on A and on B.In this paper we see some properties of the constructions of bipartite hypermaps described algebraically by Breda and Duarte in 2007 which generalize the construction induced by the Walsh representation of hypermaps. As an application we show that all surfaces have bipartite-regular hypermaps.
A Bijection Proving the Aztec Diamond Theorem by Combing Lattice Paths
Authors: Bosio Frédéric , Van Leeuwen Marc A. A. 
Published: January 2020

We give a bijective proof of the Aztec diamond theorem, stating that there are $2^{n(n+1)/2}$ domino tilings of the Aztec diamond of order $n$. The proof in fact establishes a similar result for non-intersecting families of $n+1$ Schröder paths, with horizontal, diagonal or vertical steps, linking the grid points of two adjacent sides of an $n\times n$ square grid; these families are well known to be in bijection with tilings of the Aztec diamond. Our bijection is produced by an invertible "combing'' algorithm, operating on families of paths without non-intersection condition, but instead with the requirement that any vertical steps come at the end of a path, and which are clearly $2^{n(n+1)/2}$ in number; it transforms them into non-intersecting families.