This paper discusses the permutations that are generated by rotating $k\times k$ blocks of squares in a union of overlapping $k\times (k+1)$ rectangles. It is found that the single-rotation parity constraints effectively determine the group of accessible permutations. If there are $m$ squares, and the space is partitioned as a checkerboard with $m$ squares shaded and $n–m$ squares unshaded, then the four possible cases are $A_n$, $S_n$, $A_m\times A_{n-m}$, and the subgroup of all even permutations in $S_m\times S_{n-m}$, with exceptions when $k=2$ and $k=3$.

The packing and covering numbers for the 4-stars were determined by Roditty in 1986. In this paper, we improve and extend these results by finding a corresponding maximum packing and minimum covering of the complete graph with 4-stars for every possible leave graph and excess graph.

We examine the Borda voting method, which has numerous interesting mathematical properties. We determine when a candidate can win a Borda election with all $i$th place votes and present a method of constructing ballots that yield such a victory. Then we present a connection between Borda elections and semi-magic squares. We show how a Borda election result gives rise to a semi-magic square, and we show that given any semi-magic square there exists at least one Borda election result corresponding to it.

In 2000, Rees and Shalaby constructed simple indecomposable two-fold cyclic triple systems for all $v\equiv 0,1,3,4,7,\text{ and }9(\mathrm{mod}12)$ where $v=4$ or $v\ge 12$, using Skolem-type sequences.
We construct, using Skolem-type sequences, three-fold triple systems having the properties of being cyclic, simple, and indecomposable for all admissible orders $v$, with some possible exceptions for $v=9$ and $v=24c+57$, where $c\ge 2$ is a constant.

Counting the number of maximal independent sets is $\mathrm{\#}P$-complete even for chordal graphs. We prove that the number of maximal independent sets in a subclass $G_n^R$ (Right power set graphs) of chordal graphs can be computed in polynomial time using Golomb’s nonlinear recurrence relation. We provide a recursive construction of $G_n^R$ and prove that there are $2^{\frac{|V(G_n^R)|+1}{4}}$ maximum independent sets in $G_n^R$. We also provide a polynomial-time algorithm to solve the maximum independent set problem (MISP) in a superclass ${\mathcal{F}}_n$ of the complement of $G_n^R$.

The eccentric connectivity index of the molecular graph $G$ was proposed by Sharma, Goswami, and Madan in 1997 \cite{17}. This index is defined as ${\xi }^c(G)=\sum _{v\in V(G)}\mathrm{deg}(v)ec(v)$, where $\mathrm{deg}(v)$ is the degree of vertex $v$ in $G$ and eccentricity $ec(v)$ is the largest distance between $v$ and any other vertex of $G$. Thus, in this paper, we established the general formulas for the eccentric connectivity index of joining a special graph to its paths and of joining two different graphs by a path. Proofs were also provided.

We present a design for a seven-game tournament of the $7$-player board game $Diplomacy$, in which each player plays each country one time and each pair of players shares a border either $4$ or $5$ times. It is impossible for each pair of players to share a border the same number of times in such a tournament, and so the tournament presented is the most “balanced” possible in this sense. A similarly balanced tournament can be constructed for a generalized version of the game involving an arbitrary number of countries. We also present an infinite family of graphs that cannot be balanced.

A graph $G=(V,E)$ with $p$ vertices and $q$ edges is called a Harmonic mean graph if it is possible to label the vertices $v\in V$ with distinct labels $f(v)$ from $1,2,\dots ,q+1$ in such a way that when each edge $e=uv$ is labeled with $f(e=uv)=\lceil \frac{2f(u)f(v)}{f(u)+f(v)}\rceil$ or $\lfloor \frac{2f(u)f(v)}{f(u)+f(v)}\rfloor$, then the edge labels are distinct. In this case, $f$ is called a Harmonic mean labeling of $G$. In this paper, we investigate some new families of Harmonic mean graphs.

The clique sum $\mathrm{\Sigma }=G[G_1,G_2,\dots ,G_n]$ is the lexicographic sum over $G$ where each fiber $G_i$ is a clique. We show the reconstruction number of $\mathrm{\Sigma }$ is three unless $\mathrm{\Sigma }$ is vertex transitive and $G$ has order at least two. In the latter case, it follows that $\mathrm{\Sigma }=G[K_m]$ is a lexicographic product, and the reconstruction number is $m+2$. This complements the bounds of Brewster, Hahn, Lamont, and Lipka. It also extends the work of Myrvold and Molina.

We provide a new proof of a result of Hanson and Toft classifying the maximum-size $K_r$-free graphs on $n$ vertices with chromatic number at least $r$.

Much research has been done on the edge decomposition of $\lambda$ copies of the complete graph $G$ with respect to some specified subgraph $H$ of $G$. This is equivalent to the investigation of $(G,H)$-designs of index $\lambda$. In this paper, we present a fundamental theorem on the decomposition of $\lambda$ copies of a complete bipartite graph. As an application of this result, we show that necessary conditions are sufficient for the decomposition of $\lambda$ copies of a complete bipartite graph into several multi-subgraphs $H$ with a number of vertices less than or equal to $4$ and the number of edges less than or equal to $4$, with some exceptions where decompositions do not exist. These decomposition problems are interesting to study as various decompositions do not exist even when necessary conditions are satisfied.

If the integer $r\ge 2$, say that a composition of the natural number $n$ is $r$-$regular$ if no part is divisible by $r$. Let $c_r(n)$ denote the number of $r$-regular compositions of $n$ (with $c_r(0)=1$). We show that $c_r(n)$ satisfies a linear recurrence of order $r$. We also obtain asymptotic estimates for $c_r(n)$, and we evaluate $c_r(n)$ for $2\le r\le 5$ and $1\le n\le 10$.

Using only the skein relation and some combinatorics, we find a closed form for the Conway polynomial of $(m,3)$ torus links and a trio of recurrence relations that define the Conway polynomial of any $(m,4)$ torus link.

For positive integers $c$ and $d$, let $K_{c\times d}$ denote the complete multipartite graph with $c$ parts, each containing $d$ vertices. Let $G$ with $n$ edges be the union of two vertex-disjoint even cycles. We use graph labelings to show that there exists a cyclic $G$-decomposition of $K_{(2n+1)\times t}$, $K_{(n/2+1)\times 4t}$, $K_{5\times (n/2)t}$, and of $K_{2\times 2nt}$ for every positive integer $t$. If $n\equiv 0(\mathrm{mod}4)$, then there also exists a cyclic $G$-decomposition of $K_{(n+1)\times 2t}$, $K_{(n/4+1)\times 8t}$, $K_{9\times (n/4)t}$, and of $K_{3\times nt}$ for every positive integer $t$.

For a Hamiltonian graph $G$, the Hamiltonian cycle extension number of $G$ is the maximum positive integer $k$ for which every path of order $k$ or less is a subpath of some Hamiltonian cycle of $G$. The Hamiltonian cycle extension numbers of all Hamiltonian complete multipartite graphs are determined. Sharp lower bounds for the Hamiltonian cycle extension number of a Hamiltonian graph are presented in terms of its minimum degree and order, its size and the sum of the degrees of every two non-adjacent vertices. Hamiltonian cycle extension numbers are also determined for powers of cycles.

We give conditions on the numbers $\{{\phi }_{ij}\}$ under which a vertex-degree-based topological index $TI$ of the form

$$TI(G)=\sum _{1\le i\le j\le n-1}{m}_{ij}{\phi }_{ij},$$

where $G$ is a graph with $n$ vertices and $m_{ij}$ is the number of $ij$-edges, has the zigzag chain as an extreme value among all polyomino chains. As a consequence, we deduce that over the polyomino chains, the zigzag chain has the maximal value of the Randić index, the sum-connectivity index, the harmonic index, and the geometric-arithmetic index, and the minimal value of the first Zagreb index, second Zagreb index, and atom-bond-connectivity index.

A cluster of $2n+1$ cubes comprising the central cube and reflections in all its faces is called the $n$-dimensional cube. If $2n+1$ is not a prime, then there are infinitely many tilings of ${\mathbb{R}}^n$ by crosses, but it has been conjectured that there is a unique tiling of ${\mathbb{R}}^n$ by crosses otherwise. The conjecture has been proved for $n=2,3$, and in this paper, we prove it also for $n=5$. So there is a unique tiling of ${\mathbb{R}}^3$ by crosses, there are infinitely many tilings of ${\mathbb{R}}^4$, but for ${\mathbb{R}}^5$, there is again only one tiling by crosses. We consider this result to be a paradox as our intuition suggests that “the higher the dimension of the space, the more freedom we get.
“`

A graph $G$ is collapsible if for every even subset $R\subseteq V(G)$, there is a spanning connected subgraph $H_R$ of $G$ whose set of odd degree vertices is $R$. A graph is reduced if it has no nontrivial collapsible subgraphs. Catlin [4] showed that the existence of spanning Eulerian subgraphs in a graph $G$ can be determined by the reduced graph obtained from $G$ by contracting all the collapsible subgraphs of $G$. In this paper, we present a result on 3-edge-connected reduced graphs of small orders. Then, we prove that a 3-edge-connected graph $G$ of order $n$ either has a spanning Eulerian subgraph or can be contracted to the Petersen graph if $G$ satisfies one of the following:

1. $d(u)+d(v)>2(\frac{n}{15}–1)$ for any $uv\notin E(G)$ and $n$ is large;
2. the size of a maximum matching in $G$ is at most 6;
3. the independence number of $G$ is at most 5.

These are improvements of prior results in [16], [18], [24], and [25].

In this note, we consider the lexicographical ordering by spectral moments of trees with a given degree sequence. Such questions have been studied for a variety of different categories of trees. Particularly, the last tree in this ordering among trees with a given degree sequence was recently identified in two independent manuscripts. The characterization of the first such trees, however, remains open. We make some progress on this question in this note, by making use of the interpretation of the spectral moment in terms of numbers of paths and the product of adjacent vertex degrees, the first trees are characterized with the additional condition that the nonleaf vertex degrees are different from each other. We also comment on the case when there are repetitions in the vertex degrees.

We determine all 120 nonisomorphic systems obtainable from the projective Steiner triple system of order 31 by at most three Pasch trades. Exactly three of these, each corresponding to three Pasch trades, are rigid. Thus three Pasch trades suffice, and are required, in
order to convert the projective system of order 31 to a rigid system. This contrasts with the projective system of order 15 where four Pasch trades are required. We also show that four Pasch trades are required in order to convert the projective system of order 63 to a
rigid system.

In the paper “Eternal security in graphs” by Goddard, Hedetniemi and Hedetniemi (2005, [4]), the authors claimed that, for any Cayley graph, the eternal $m$-security number equals the minimum cardinality of a dominating set. However, the equality is false. In this note, we present a counterexample and comment on the eternal $m$-security number for Cayley graphs.

Define ${\mathcal{D}}_k$ to be the class of graphs such that, for every independent set $\{v_1,\dots ,v_h\}$ of vertices with $2\le h\le k$, if $S$ is an inclusion-minimal set of vertices whose deletion would put $v_1,\dots ,v_h$ into $h$ distinct connected components, then $S$ induces a complete subgraph; also, let $\mathcal{D}=\bigcap _{k\ge 2}{\mathcal{D}}_k$. Similarly, define ${\mathcal{D}}_k^{\prime }$ and ${\mathcal{D}}^{\prime }$ with “complete” replaced by “edgeless,” and define ${\mathcal{D}}_k^{\ast }$ and ${\mathcal{D}}^{\ast }$ with “complete” replaced by “complete or edgeless.” The class ${\mathcal{D}}_2$ is the class of chordal graphs, and the classes $\mathcal{D}$, ${\mathcal{D}}_2^{\prime }$, and ${\mathcal{D}}_2^{\ast }$ have also been characterized recently. The present paper gives unified characterizations of all of the classes ${\mathcal{D}}_k$, ${\mathcal{D}}_k^{\prime }$, ${\mathcal{D}}_k^{\ast }$, $\mathcal{D}$, ${\mathcal{D}}^{\prime }$, and ${\mathcal{D}}^{\ast }$.