Search

Let $G$ be a connected graph. The eccentricity of a path $P$, denoted by ecc$_G(P)$, is the maximum distance from $P$ to any vertex in $G$. In the \textsc{Central path} (CP) problem our aim is to find a path of minimum eccentricity. This problem was introduced by Cockayne et al., in 1981, in the study of different centrality measures on graphs. They showed that CP can be solved in linear time in trees, but it is known to be NP-hard in many classes of graphs such as chordal bipartite graphs, planar 3-connected graphs, split graphs, etc. We investigate the path eccentricity of a connected graph~$G$ as a parameter. Let pe$(G)$ denote the value of ecc$_G(P)$ for a central path $P$ of $G$. We obtain tight upper bounds for pe$(G)$ in some graph classes. We show that pe$(G) \leq 1$ on biconvex graphs and that pe$(G) \leq 2$ on bipartite convex graphs. Moreover, we design algorithms that find such a path in linear time. On the other hand, by investigating the longest paths of a graph, we obtain tight upper bounds for pe$(G)$ on general graphs and $k$-connected graphs. Finally, we study the relation between a central path and a longest path in a graph. We show that on trees, and bipartite permutation graphs, a longest path is also a central path. Furthermore, for superclasses of these graphs, we exhibit counterexamples for this property.

For unweighted graphs, finding isometric embeddings is closely related to decompositions of $G$ into Cartesian products of smaller graphs. When $G$ is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of $G$. When $G$ is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of $G$. Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph $G$, where $G$ satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any $m$-edge, $n$-vertex graph with positive integer edge weights can be factored in $O(m^2)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O(m^2+n^2\log\log n)$ time. We also show that a pseudofactorization for such a graph can be computed in $O(mn)$ time, plus the time to solve APSP, resulting in an $O(mn+n^2\log\log n)$ running time., Comment: 37 pages, 10 figures

In this paper, we derive a recurrence relation of anti-forcing polynomial for catacondensed hexagonal systems.

In this paper, we study the matrix period and the competition period of Toeplitz matrices over a binary Boolean ring $\mathbb{B} = \{0,1\}$. Given subsets $S$ and $T$ of $\{1,\ldots,n-1\}$, an $n\times n$ Toeplitz matrix $A=T_n\langle S ; T \rangle$ is defined to have $1$ as the $(i,j)$-entry if and only if $j-i \in S$ or $i-j \in T$. We show that if $\max S+\min T \le n$ and $\min S+\max T \le n$, then $A$ has the matrix period $d/d'$ and the competition period $1$ where $d = \gcd (s+t \mid s \in S, t \in T)$ and $d' = \gcd(d, \min S)$. Moreover, it is shown that the limit of the matrix sequence $\{A^m(A^T)^m\}_{m=1}^\infty$ is a directed sum of matrices of all ones except zero diagonal. In many literatures we see that graph theoretic method can be used to prove strong structural properties about matrices. Likewise, we develop our work from a graph theoretic point of view.

A classic result in extremal graph theory, known as Mantel's theorem, states that every non-bipartite graph of order $n$ with size $m>\lfloor \frac{n^{2}}{4}\rfloor$ contains a triangle. Lin, Ning and Wu [Comb. Probab. Comput. 30 (2021) 258-270] proved a spectral version of Mantel's theorem for given order $n.$ Zhai and Shu [Discrete Math. 345 (2022) 112630] investigated a spectral version for fixed size $m.$ In this paper, we prove $Q$-spectral versions of Mantel's theorem., 14 pages, 4 figures

A $k$-edge-weighting of $G$ is a mapping $\omega:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting of $G$ naturally induces a vertex-colouring $\sigma_{\omega}:V(G)\longrightarrow \mathbb{N}$ given by$\sigma_{\omega}(v)=\sum_{u\in N_G(v)}\omega(vu)$ for every $v\in V(G)$. The edge-weighting $\omega$ is neighbour sum distinguishing if it yields a proper vertex-colouring $\sigma_{\omega}$, \emph{i.e.}, $\sigma_{\omega}(u)\neq \sigma_{\omega}(v)$ for every edge $uv$ of $G$.We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(\Delta(G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.

For $q\in\mathbb{R}$, the $Q$-matrix $Q=Q_q$ of a connected simple graph $G=(V,E)$ is $Q_q=(q^{\partial(x,y)})_{x,y\in V}$, where $\partial$ denotes the path-length distance. Describing the set $\pi(G)$ consisting of those $q\in \mathbb{R}$ for which $Q_q$ is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that $G$ has at least two vertices. Then $\pi(G)$ is easily seen to be a nonempty closed subset of the interval $[-1,1]$. In this note, we show that $\pi(G)=[-1,1]$ if and only if $G$ is isometrically embeddable into a hypercube (infinite-dimensional if $G$ is infinite) if and only if $G$ is bipartite and does not possess certain five-vertex configurations, an example of which is an induced $K_{2,3}$., Comment: 6 pages

The independence number of a square matrix $A$, denoted by $\alpha(A)$, is the maximum order of its principal zero submatrices. Let $S_n^{+}$ be the set of $n\times n$ nonnegative symmetric matrices with zero trace. Denote by $J_n$ the $n\times n$ matrix with all entries equal to one. Given any integer $n$, we prove that a linear map $\phi: S_n^+\rightarrow S_n^+$ satisfies $$\alpha(\phi(X))= \alpha(X) {\quad\rm for~ all\quad}X\in S_n^+$$ if and only if there is a permutation matrix $P$ such that $$\phi(X)=H\circ(P^TXP)\quad { \rm for~ all\quad}X\in S_n^+,$$ where $H=\phi(J_n-I_n)$ with all off-diagonal entries positive.

A graph $G$ is called interval colorable if it has a proper edge coloring with colors $1,2,3,\dots$ such that the colors of the edges incident to every vertex of $G$ form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph $G$, denoted ${\theta_{\mathrm{int}}}(G)$, which is the minimum number of interval colorable edge-disjoint subgraphs of $G$ whose union is $G$. Our investigation is motivated by scheduling problems with compactness requirements, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly $3$-edge colorable graph with maximum degree $3$ is interval colorable, and using this result, we deduce an upper bound on ${\theta_{\mathrm{int}}}(G)$ for general graphs $G$. We demonstrate that this upper bound can be improved in the case when $G$ is bipartite, planar or complete multipartite and consider some applications in timetabling.

We study the average number $\mathcal{A}(G)$ of colors in the non-equivalent colorings of a graph $G$. We show some general properties of this graph invariant and determine its value for some classes of graphs. We then conjecture several lower bounds on $\mathcal{A}(G)$ and prove that these conjectures are true for specific classes of graphs such as triangulated graphs and graphs with maximum degree at most 2., 20 pages, 2 figures

We present some necessary and/or sufficient conditions for the positivity problem of three-term recurrence sequences. As applications we show the positivity of diagonal Taylor coefficients of some rational functions in a unified approach. We also establish a criterion for the positivity and log-convexity of such sequences., 13 pages

We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {\em even} if it has an even number of vertices. An {\em even-hole-free} graph is a graph with no even holes. A vertex of a graph is {\em bisimplicial} if the set of its neighbours is the union of two cliques. In an earlier paper \cite{bisimplicial}, Addario-Berry, Havet and Reed, with the authors, claimed to prove a conjecture of Reed, that every even-hole-free graph has a bisimplicial vertex, but we have recently been shown that the "proof" has a serious error. Here we give a proof using a different method.

Let $\mathcal{G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of $\mathcal{G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to $\mathcal{G}.$ We denote by $\mathcal{A}_k (\mathcal{G})$ the set of all graphs that are $k$-apices of $\mathcal{G}.$ We prove that every graph in the obstruction set of $\mathcal{A}_k (\mathcal{G}),$ i.e., the minor-minimal set of graphs not belonging to $\mathcal{A}_k (\mathcal{G}),$ has size at most $2^{2^{2^{2^{\mathsf{poly}(k)}}}},$ where $\mathsf{poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of $\mathcal{G}.$ This bound drops to $2^{2^{\mathsf{poly}(k)}}$ when $\mathcal{G}$ excludes some apex graph as a minor., Comment: 48 pages and 12 figures. arXiv admin note: text overlap with arXiv:2004.12692

The block reversal of a word $w$, denoted by $\mathtt{BR}(w)$, is a generalization of the concept of the reversal of a word, obtained by concatenating the blocks of the word in the reverse order. We characterize non-binary and binary words whose block reversal contains only rich words. We prove that for a binary word $w$, richness of all elements of $\mathtt{BR}(w)$ depends on $l(w)$, the length of the run sequence of $w$. We show that if all elements of $\mathtt{BR}(w)$ are rich, then $2\leq l(w)\leq 8$. We also provide the structure of such words.

The proper chromatic number $\Vec{\chi}(G)$ of a graph $G$ is the minimum $k$ such that there exists an orientation of the edges of $G$ with all vertex-outdegrees at most $k$ and such that for any adjacent vertices, the outdegrees are different. Two major conjectures about the proper chromatic number are resolved. First it is shown, that $\Vec{\chi}(G)$ of any planar graph $G$ is bounded (in fact, it is at most 14). Secondly, it is shown that for every graph, $\Vec{\chi}(G)$ is at most $O(\frac{r\log r}{\log\log r})+\tfrac{1}{2}\MAD(G)$, where $r=\chi(G)$ is the usual chromatic number of the graph, and $\MAD(G)$ is the maximum average degree taken over all subgraphs of $G$. Several other related results are derived. Our proofs are based on a novel notion of fractional orientations.

A thoroughly studied problem in Extremal Graph Theory is to find the best possible density condition in a host graph $G$ for guaranteeing the presence of a particular subgraph $H$ in $G$. One such classical result, due to Bollob\'{a}s and Thomason, and independently Koml\'{o}s and Szemer\'{e}di, states that average degree $O(k^2)$ guarantees the existence of a $K_k$-subdivision. We study two directions extending this result. On the one hand, Verstra\"ete conjectured that the quadratic bound $O(k^2)$ would guarantee already two vertex-disjoint isomorphic copies of a $K_k$-subdivision. On the other hand, Thomassen conjectured that for each $k \in \mathbb{N}$ there is some $d = d(k)$ such that every graph with average degree at least $d$ contains a balanced subdivision of $K_k$, that is, a copy of $K_k$ where the edges are replaced by paths of equal length. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on $d(k)$ remains open. In this paper, we show that the quadratic bound $O(k^2)$ suffices to force a balanced $K_k$-subdivision. This gives the optimal bound on $d(k)$ needed in Thomassen's conjecture and implies the existence of $O(1)$ many vertex-disjoint isomorphic $K_k$-subdivisions, confirming Verstra\"ete's conjecture in a strong sense., Comment: 17 pages, 4 figures

Let $G$ be a graph of size $m$ and $\rho(G)$ be the spectral radius of its adjacency matrix. A graph is said to be $F$-free if it does not contain a subgraph isomorphic to $F$. In this paper, we prove that if $G$ is a $K_{2,r+1}$-free non-star graph with $m\geq (4r+2)^2+1$, then $\rho(G)\leq \rho(S_m^1)$, with equality if and only if $G\cong S_m^1$. Recently, Li, Sun and Wei showed that for any $\theta_{1,2,3}$-free graph of size $m\geq 8$, $\rho(G)\leq \frac{1+\sqrt{4m-3}}{2}$, with equality if and only if $G\cong S_{\frac{m+3}{2},2}$. However, this bound is not attainable when $m$ is even. We proved that if $G$ is $\theta_{1,2,3}$-free and $G\ncong S_{\frac{m+3}{2},2}$ with $m\geq 22$, then $\rho(G)\leq \rho(F_{m,1})$ if $m$ is even, with equality if and only if $G\cong F_{m,1}$, and $\rho(G)\leq \rho(F_{m,2})$ if $m$ is odd, with equality if and only if $G\cong F_{m,2}$., Comment: 15 pages, 3 figures

In this paper, we exhibit an irreducible Markov chain $M$ on the edge $k$-colorings of bipartite graphs based on certain properties of the solution space. We show that diameter of this Markov chain grows linearly with the number of edges in the graph. We also prove a polynomial upper bound on the inverse of acceptance ratio of the Metropolis-Hastings algorithm when the algorithm is applied on $M$ with the uniform distribution of all possible edge $k$-colorings of $G$. A special case of our results is the solution space of the possible completions of Latin rectangles., Comment: 20 pages, 2 figures

Here we introduce connectivity operators, namely, diffusion operators, general Laplacian operators, and general adjacency operators for hypergraphs. These operators are generalisations of some conventional notions of apparently different connectivity matrices associated with hypergraphs. In fact, we introduce here a unified framework for studying different variations of the connectivity operators associated with hypergraphs at the same time. Eigenvalues and corresponding eigenspaces of the general connectivity operators associated with some classes of hypergraphs are computed. Applications such as random walks on hypergraphs, dynamical networks, and disease transmission on hypergraphs are studied from the perspective of our newly introduced operators. We also derive spectral bounds for the weak connectivity number, degree of vertices, maximum cut, bipartition width, and isoperimetric constant of hypergraphs.

We define solvable quantum mechanical systems on a Hilbert space spanned by bipartite ribbon graphs with a fixed number of edges. The Hilbert space is also an associative algebra, where the product is derived from permutation group products. The existence and structure of this Hilbert space algebra has a number of consequences. The algebra product, which can be expressed in terms of integer ribbon graph reconnection coefficients, is used to define solvable Hamiltonians with eigenvalues expressed in terms of normalized characters of symmetric group elements and degeneracies given in terms of Kronecker coefficients, which are tensor product multiplicities of symmetric group representations. The square of the Kronecker coefficient for a triple of Young diagrams is shown to be equal to the dimension of a sub-lattice in the lattice of ribbon graphs. This leads to an answer to the long-standing question of a combinatoric interpretation of the Kronecker coefficients. As an avenue to explore quantum supremacy and its implications for computational complexity theory, we outline experiments to detect non-vanishing Kronecker coefficients for hypothetical quantum realizations/simulations of these quantum systems. The correspondence between ribbon graphs and Belyi maps leads to an interpretation of these quantum mechanical systems in terms of quantum membrane world-volumes interpolating between string geometries., Version 1 - 49 pages; 12 pages of Appendices; 1 figure; revision V2 - added Lemma 1 which simplifies the proof of the main theorems; revision V3 - published version

We describe an approach, via Malle's permutation $\Psi$ on the set of irreducible characters $\text{Irr}(W)$, that gives a uniform derivation of the Chapuy-Stump formula for the enumeration of reflection factorizations of the Coxeter element. It also recovers its weighted generalization by delMas, Reiner, and Hameister, and further produces structural results for factorization formulas of arbitrary regular elements., Comment: 27 pages, comments very much welcome

We prove a recursive formula for plethysm coefficients of the form $a^\mu_{\lambda,(m)}$, generalising results on plethysms due to Bruns--Conca--Varbaro and de Boeck--Paget--Wildon. From this we deduce a stability result and resolve two conjectures of de Boeck concerning plethysms, as well as obtain new results on Sylow branching coefficients for symmetric groups for the prime 2. Further, letting $P_n$ denote a Sylow 2-subgroup of $S_n$, we show that almost all Sylow branching coefficients of $S_n$ corresponding to the trivial character of $P_n$ are positive., Comment: 35 pages, 6 figures; further explanation and detail added throughout, in particular in Section 5.1, results unchanged; typos corrected; acknowledgements updated

This paper is a follow-up to (arXiv:2203.03687), in which the first author studied primitive association schemes lying between a tensor power $\mathcal{T}_m^d$ of the trivial association scheme and the Hamming scheme $\mathcal{H}(m,d)$. A question which arose naturally in that study was whether all primitive fusions of $\mathcal{T}_m^d$ lie between $\mathcal{T}_{m^e}^{d/e}$ and $\mathcal{H}(m^d, d/e)$ for some $e \mid d$. This note answers this question positively provided that $m$ is large enough. We similarly classify primitive fusions of the $d$th tensor power of a Johnson scheme on $\binom{m}{k}$ points provided $m$ is large enough in terms of $k$ and $d$., 5 pages. Final version incorporating referees' comments. To appear in Algebraic Combinatorics

Let $n$ be a positive integer, and let $\rho_n = (n, n-1, n-2, \ldots, 1)$ be the ``staircase'' partition of size $N = {n+1 \choose 2}$. The Saxl conjecture asserts that every irreducible representation $S^\lambda$ of the symmetric group $S_N$ appears as a subrepresentation of the tensor square $S^{\rho_n} \otimes S^{\rho_n}$. In this short note we show that every irreducible representation of $S_N$ appears in the tensor cube $S^{\rho_n} \otimes S^{\rho_n} \otimes S^{\rho_n}$., Comment: 4 pages. Added an independent second proof of the main theorem

In this article, we extend the notion of the Laplacian spread to simple directed graphs (digraphs) using the restricted numerical range. First, we provide Laplacian spread values for several families of digraphs. Then, we prove sharp upper bounds on the Laplacian spread for all polygonal and balanced digraphs. In particular, we show that the validity of the Laplacian spread bound for balanced digraphs is equivalent to the Laplacian spread conjecture for simple undirected graphs, which was conjectured in 2011 and proven in 2021. Moreover, we prove an equivalent statement for weighted balanced digraphs with weights between $0$ and $1$. Finally, we state several open conjectures that are motivated by empirical data.

Given $k\ge 2$ and two $k$-graphs ($k$-uniform hypergraphs) $F$ and $H$, an \emph{$F$-factor} in $H$ is a set of vertex disjoint copies of $F$ that together covers the vertex set of $H$. Lenz and Mubayi studied the $F$-factor problems in quasi-random $k$-graphs with minimum degree $\Omega(n^{k-1})$. In particular, they constructed a sequence of $1/8$-dense quasi-random $3$-graphs $H(n)$ with minimum degree $\Omega(n^2)$ and minimum codegree $\Omega(n)$ but with no $K_{2,2,2}$-factor. We prove that if $p>1/8$ and $F$ is a $3$-partite $3$-graph with $f$ vertices, then for sufficiently large $n$, all $p$-dense quasi-random $3$-graphs of order $n$ with minimum codegree $\Omega(n)$ and $f\mid n$ have $F$-factors. That is, $1/8$ is the density threshold for ensuring all $3$-partite $3$-graphs $F$-factors in quasi-random $3$-graphs given a minimum codegree condition $\Omega(n)$. Moreover, we show that one can not replace the minimum codegree condition by a minimum vertex degree condition. In fact, we find that for any $p\in(0,1)$ and $n\ge n_0$, there exist $p$-dense quasi-random $3$-graphs of order $n$ with minimum degree $\Omega (n^2)$ having no $K_{2,2,2}$-factor. In particular, we study the optimal density threshold of $F$-factors for each $3$-partite $3$-graph $F$ in quasi-random $3$-graphs given a minimum codegree condition $\Omega(n)$., Comment: 22 pages. Accepted by Journal of Combinatorial Theory, Series B

A graph $H$ is an induced minor of a graph $G$ if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that there is a function $f(k, d) = O(k^{10} + 2^{d^5})$ so that if a graph has treewidth at least $f(k, d)$ and maximum degree at most $d$, then it contains a $k \times k$-grid as an induced minor. This proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon [Eur. J. Comb., 98, 2021] that any graph with large treewidth and bounded maximum degree contains a large wall or the line graph of a large wall as an induced subgraph. It also implies that for any fixed planar graph $H$, there is a subexponential time algorithm for maximum weight independent set on $H$-induced-minor-free graphs., 7 pages. To appear in JCTB

We characterize the simple connected graphs with the second largest eigenvalue less than 1/2, which consists of 13 classes of specific graphs. These 13 classes hint that $c_{2}\in [1/2, \sqrt{2+\sqrt{5}}]$, where $c_2$ is the minimum real number $c$ for which every real number greater than $c$ is a limit point in the set of the second largest eigenvalues of the simple connected graphs. We leave it as a problem., 36 pages, 2 tables

Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph $G$ is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in $G$, and also in terms of subgraphs of $G$ that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of $G$. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square-graphs by a sequence of ``square-boundary'' amalgamations. These considerations also lead to an $\mathcal{O}(n\log n)$-time recognition algorithm to compute a decomposition of a planar median graph with $n$ vertices into cubes and square-graphs.

Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a subset $\mathcal{F}$ of $G$ is \emph{intersecting} if any two elements of $\mathcal{F}$ agree on some element of $\Omega$. The \emph{intersection density} of $G$, denoted by $\rho(G)$, is the maximum of the rational number $|\mathcal{F}|\left(\frac{|G|}{|\Omega|}\right)^{-1}$ when $\mathcal{F}$ runs through all intersecting sets in $G$. In this paper, we prove that if $G$ is the group $\operatorname{Sym}(n)$ or $\operatorname{Alt}(n)$ acting on the $k$-subsets of $\{1,2,3\ldots,n\}$, for $k\in \{3,4,5\}$, then $\rho(G)=1$. Our proof relies on the representation theory of the symmetric group and the ratio bound., Comment: 31 pages

Let $C_n$ be a cyclic group of order $n$. A sequence $S$ of length $\ell$ over $C_n$ is a sequence $S = a_1\boldsymbol\cdot a_2\boldsymbol\cdot \ldots\boldsymbol\cdot a_{\ell}$ of $\ell$ elements in $C_n$, where a repetition of elements is allowed and their order is disregarded. We say that $S$ is a zero-sum sequence if $\Sigma_{i=1}^{\ell} a_i = 0$ and that $S$ is a zero-sum free sequence if $S$ contains no zero-sum subsequence. Let $R$ be a random subset of $C_n$ obtained by choosing each element in $C_n$ independently with probability $p$. Let $N^R_{n-1-k}$ be the number of zero-sum free sequences of length $n-1-k$ in $R$. Also, let $N^R_{n-1-k,d}$ be the number of zero-sum free sequences of length $n-1-k$ having $d$ distinct elements in $R$. We obtain the expectation of $N^R_{n-1-k}$ and $N^R_{n-1-k,d}$ for $0\leq k\leq \big\lfloor \frac{n}{3} \big\rfloor$. We also show a concentration result on $N^R_{n-1-k}$ and $N^R_{n-1-k,d}$ when $k$ is fixed., Comment: 15 pages

The \emph{central levels problem} asserts that the subgraph of the $(2m+1)$-dimensional hypercube induced by all bitstrings with at least $m+1-\ell$ many 1s and at most $m+\ell$ many 1s, i.e., the vertices in the middle $2\ell$ levels, has a Hamilton cycle for any $m\geq 1$ and $1\le \ell\le m+1$.\ud This problem was raised independently by Buck and Wiedemann, Savage, Gregor and {\v{S}}krekovski, and by Shen and Williams, and it is a common generalization of the well-known \emph{middle levels problem}, namely the case $\ell=1$, and classical binary Gray codes, namely the case $\ell=m+1$.\ud In this paper we present a general constructive solution of the central levels problem.\ud Our results also imply the existence of optimal cycles through any sequence of $\ell$ consecutive levels in the $n$-dimensional hypercube for any $n\ge 1$ and $1\le \ell \le n+1$.\ud Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the $n$-dimensional hypercube, $n\geq 2$, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.

We study the graph energy from a cooperative game viewpoint. We introduce \emph{the graph energy game} and show various properties. In particular, we see that it is a superadditive game and that the energy of a vertex, as defined in Arizmendi and Juarez-Romero (2018), belongs to the core of the game. These properties imply new bounds for the energy of graphs. We also consider a version based on $p$-Schatten norms., 15 pages, 3 figures

Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$. It can be shown that given an arbitrary perfect matching of $G$, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$-factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$, there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$, there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection., 13 pages, 8 figures

It is known that $A$-paths of length $0$ mod $m$ satisfy the Erd\H{o}s-P\'osa property if $m=2$ or $m=4$, but not if $m > 4$ is composite. We show that if $p$ is prime, then $A$-paths of length $0$ mod $p$ satisfy the Erd\H{o}s-P\'osa property. More generally, in the framework of undirected group-labelled graphs, we characterize the abelian groups $\Gamma$ and elements $\ell \in \Gamma$ for which the Erd\H{o}s-P\'osa property holds for $A$-paths of weight $\ell$., Comment: arXiv admin note: text overlap with arXiv:2009.11266

A family of sets is $(p,q)$-intersecting if every nonempty subfamily of $p$ or fewer sets has at least $q$ elements in its total intersection. A family of sets has the $(p,q)$-Helly property if every nonempty $(p,q)$-intersecting subfamily has total intersection of cardinality at least $q$. The $(2,1)$-Helly property is the usual Helly property. A hypergraph is $(p,q)$-Helly if its edge family has the $(p,q)$-Helly property and hereditary $(p,q)$-Helly if each of its subhypergraphs has the $(p,q)$-Helly property. A graph is $(p,q)$-clique-Helly if the family of its maximal cliques has the $(p,q)$-the Helly property and hereditary $(p,q)$-clique-Helly if each of its induced subgraphs is $(p,q)$-clique-Helly. The classes of $(p,q)$-biclique-Helly and hereditary $(p,q)$-biclique-Helly graphs are defined analogously. We prove several characterizations of hereditary $(p,q)$-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. We give an improved time bound for the recognition of $(p,q)$-Helly hypergraphs for each fixed $q$ and show that the recognition of hereditary $(p,q)$-Helly hypergraphs can be solved in polynomial time if $p$ and $q$ are fixed but co-NP-complete if $p$ is part of the input. In addition, we generalize to $(p,q)$-clique-Helly graphs the characterization of $p$-clique-Helly graphs in terms of expansions and give different characterizations of hereditary $(p,q)$-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of $(p,q)$-clique-Helly graphs and prove that the recognition problem of hereditary $(p,q)$-clique-Helly graphs is polynomial-time solvable for $p$ and $q$ fixed but NP-hard if $p$ or $q$ is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (hereditary) $(p,q)$-biclique-Helly graphs., Comment: 28 pages

We construct a new parametrization of double sequences $\{A_{n,k}(s)\}_{n,k}$ between $A_{n,k}(0)= \binom{n-1}{k-1}$ and $A_{n,k}(1)= \frac{1}{n!}\stirl{n}{k}$, where $\stirl{n}{k}$ are the unsigned Stirling numbers of the first kind. For each $s$ we prove a central limit theorem and a local limit theorem. This extends the de\,Moivre--Laplace central limit theorem and Goncharov's result, that unsigned Stirling numbers of the first kind are asymptotically normal. Herewith, we provide several applications.

A graph $\Gamma = (V,E)$ of order $n$ is {\em distance magic} if it admits a bijective labeling $\ell \colon V \to \{1,2, \ldots, n\}$ of its vertices for which there exists a positive integer $\kappa$ such that $\sum_{u \in N(v)} \ell(u) = \kappa$ for all vertices $v \in V$, where $N(v)$ is the neighborhood of $v$. %It is well known that a regular distance magic graph is necessarily of even valency. A {\em circulant} is a graph admitting an automorphism cyclically permuting its vertices. In this paper we study distance magic circulants of valency $6$. We obtain some necessary and some sufficient conditions for a circulant of valency $6$ to be distance magic, thereby finding several infinite families of examples. The combined results of this paper provide a partial classification of all distance magic circulants of valency $6$. In particular, we classify distance magic circulants of valency $6$, whose order is not divisible by $12$., Comment: 19 pages

This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph $G$, its zero forcing graph, $\mathscr{Z}(G)$, is the graph whose vertices are the minimum zero forcing sets of $G$ with an edge between vertices $B$ and $B'$ of $\mathscr{Z}(G)$ if and only if $B$ can be obtained from $B'$ by changing a single vertex of $G$. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing $\mathscr{Z}(G)$ takes $2^{\Theta(n)}$ operations in the worst case for a graph $G$ of order $n$.

A graph $H$ is ubiquitous if for every graph $G$ that for every natural number $n$ contains $n$ vertex-disjoint $H$-minors contains infinitely many vertex-disjoint $H$-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.

We investigate the Castelnuovo-Mumford regularity and the multiplicity of the toric ring associated with a three-dimensional Ferrers diagram. In particular, in the rectangular case, we provide direct formulas for these two important invariants. Then, we compare these invariants for an accompanying pair of Ferrers diagrams under some mild conditions and bound the Castelnuovo-Mumford regularity for more general cases., Comment: Revised following the reviewer's suggestions. 27 pages and 6 figures. Comments are welcome

We give combinatorial proofs of two multivariate Cayley--Hamilton type theorems. The first one is due to Phillips (Amer. J. Math., 1919) involving $2k$ matrices, of which $k$ commute pairwise. The second one regards the mixed discriminant, a matrix function which has generated a lot of interest in recent times. Recently, the Cayley--Hamilton theorem for mixed discriminants was proved by Bapat and Roy (Comb. Math. and Comb. Comp., 2017). We prove a Phillips-type generalization of the Bapat--Roy theorem involving $2nk$ matrices, where $n$ is the size of the matrices, among which $nk$ commute pairwise. Our proofs generalize the univariate proof of Straubing (Disc. Math., 1983) for the original Cayley--Hamilton theorem in a nontrivial way, and involve decorated permutations and decorated paths., Comment: 20 pages, 9 figures, minor corrections, final version

Let $G$ be a $K_p$-free graph. We say $e$ is a $K_p$-saturating edge of $G$ if $e\notin E(G)$ and $G+e$ contains a copy of $K_p$. Denote by $f_p(n, e)$ the minimum number of $K_p$-saturating edges that an $n$-vertex $K_p$-free graph with $e$ edges can have. Erd\H{o}s and Tuza conjectured that $f_4(n,\lfloor n^2/4\rfloor+1)=\left(1 + o(1)\right)\frac{n^2}{16}.$ Balogh and Liu disproved this by showing $f_4(n,\lfloor n^2/4\rfloor+1)=(1+o(1))\frac{2n^2}{33}$. They believed that a natural generalization of their construction for $K_p$-free graph should also be optimal and made a conjecture that $f_{p+1}(n,ex(n,K_p)+1)=\left(\frac{2(p-2)^2}{p(4p^2-11p+8)}+o(1)\right)n^2$ for all integers $p\ge 3$. The main result of this paper is to confirm the above conjecture of Balogh and Liu.

For a fixed positive $\epsilon$, we show the existence of a constant $C_\epsilon$ with the following property: Given a $\pm1$-edge-labeling $c:E(K_n)\to \{ -1,1\}$ of the complete graph $K_n$ with $c(E(K_n))=0$, and a spanning forest $F$ of $K_n$ of maximum degree $\Delta$, one can determine in polynomial time an isomorphic copy $F'$ of $F$ in $K_n$ with $|c(E(F'))|\leq \left(\frac{3}{4}+\epsilon\right)\Delta+C_\epsilon.$ Our approach is based on the method of conditional expectation.

We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class.

A graph $G$ admiting a $2$-factor is \textit{pseudo $2$-factor isomorphic} if the parity of the number of cycles in all its $2$-factors is the same. In [M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo $2$-factor isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B, 98(2) (2008), 432-444.] some of the authors of this note gave a partial characterisation of pseudo $2$-factor isomorphic bipartite cubic graphs and conjectured that $K_{3,3}$, the Heawood graph and the Pappus graph are the only essentially $4$-edge-connected ones. In [J. Goedgebeur. A counterexample to the pseudo $2$-factor isomorphic graph conjecture. Discr. Applied Math., 193 (2015), 57-60.] Jan Goedgebeur computationally found a graph $\mathscr{G}$ on $30$ vertices which is pseudo $2$-factor isomorphic cubic and bipartite, essentially $4$-edge-connected and cyclically $6$-edge-connected, thus refuting the above conjecture. In this note, we describe how such a graph can be constructed from the Heawood graph and the generalised Petersen graph $GP(8,3)$, which are the Levi graphs of the Fano $7_3$ configuration and the M\"obius-Kantor $8_3$ configuration, respectively. Such a description of $\mathscr{G}$ allows us to understand its automorphism group, which has order $144$, using both a geometrical and a graph theoretical approach simultaneously. Moreover we illustrate the uniqueness of this graph.

Let $\mathcal{H}$ be an $m$-uniform hypergraph, and let $\mathcal{A}(\mathcal{H})$ be the adjacency tensor of $\mathcal{H}$ which can be viewed as a system of homogeneous polynomials of degree $m-1$. Morozov and Shakirov generalized the traces of linear systems to nonlinear homogeneous polynomial systems and obtained explicit formulas for multidimensional resultants. Sun, Zhou and Bu introduced the Estrada index of uniform hypergraphs which is closely related to the traces of their adjacency tensors. In this paper we give formulas for the traces of $\mathcal{A}(\mathcal{H})$ when $\mathcal{H}$ contains cut vertices, and obtain results on the traces and Estrada index when $\mathcal{H}$ is perturbed under local changes. We prove that among all hypertrees with fixed number of edges, the hyperpath is the unique one with minimum Estrada index and the hyperstar is the unique one with maximum Estrada index.

In this paper, we analyze the Bollob\'as and Riordan polynomial $\mathcal{R}$ for ribbon graphs with half-ribbons introduced in [Combinatorics, Probability and Computing 31, 507-549, 2022]. We prove the universality property of a multivariate version of $\mathcal{R}$ whereas $\mathcal{R}$ itself turns out to be universal for a subclass of ribbon graphs with half-ribbons. We also show that $\mathcal{R}$ can be defined on some equivalence classes of ribbon graphs involving half-ribbons moves and that the new polynomial is universal on these classes., Comment: 21 pages, 15 figures

A fence is a poset with elements F = {x_1, x_2, ..., x_n} and covers x_1 < x_2 < ... < x_a > x_{a+1} > ... > x_b < x_{b+1} < ... where a, b, ... are positive integers. We investigate rowmotion on antichains and ideals of F. In particular, we show that orbits of antichains can be visualized using tilings. This permits us to prove various homomesy results for the number of elements of an antichain or ideal in an orbit. Rowmotion on fences also exhibits a new phenomenon, which we call orbomesy, where the value of a statistic is constant on orbits of the same size. Along the way, we prove a homomesy result for all self-dual posets and show that any two Coxeter elements in certain toggle groups behave similarly with respect to homomesies which are linear combinations of ideal indicator functions. We end with some conjectures and avenues for future research., 26 pages, 7 figures