论文库

We study upper bounds for the triameter of a connected graph in terms of distance packings and vertex connectivity. For any positive integer $k$, we bound the triameter of a graph by a linear function of its $k$-packing number and show that this bound is tight for all values of the parameters. As a corollary, we confirm the conjecture of Das and Abdioğlu on the upper bound for the triameter in terms of the order and the minimum degree of a graph. We also find the maximum triameter among graphs with given order and vertex connectivity, and describe the extremal graphs. Our main tool is a projection of a graph onto a spider or a unicyclic graph which preserves the distances between three prescribed vertices.

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

For a graph $G=(V,E)$, the boxicity $\operatorname{box}(G)$ is the least integer $d$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The Kneser graph $K(n,k)$ is the graph whose vertex set corresponds to the family of $k$ sized subsets of an $n$ sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of $K(n,k)$. We first show that for $k\ge 2$ and $n\ge 2k+1$, $\operatorname{box}(K(n,k))\ge n-2k$, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 3$. The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of $K(n,k)$. We also show that for $k\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{box}(K(2k+t,k))=o(k)$. This is the first upper bound on the boxicity of $K(n,k)$ that is sublinear in $n$. We also show that for large enough $k$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

A digraph consisting of a set of vertices $V$ and a set of arcs $E$ is called an interval digraph if there exists a family of closed intervals $\{I_u,J_u\}_{u \in V}$ such that $uv$ is an arc if and only if the intersection of $I_u$ and $J_v$ is non-empty. Interval digraphs naturally generalize interval graphs, by extending the classical interval intersection model to directed graphs. Several subclasses of interval digraphs have been studied in the literature-such as balanced, chronological and catch interval digraphs-each characterized by admitting interval representations that satisfy specific restrictions. Among these, interval nest digraphs are the ones that admit an interval representation in which $J_u$ is contained in $I_u$ for all vertices $u$ of $V$. In this work, we provide a complete characterization of interval nest digraphs in terms of vertex linear orderings with forbidden patterns, which we call nest orderings. This result completes the picture of vertex-ordering characterizations among the main subclasses of interval digraphs.