For a graph \(G\) and a positive integer \(k\), the \(k\)-Bell colour graph of \(G\) is the graph whose vertices are the partitions of \(V\) into at most \(k\) independent sets, with two of these being adjacent if there exists a vertex \(x\) such that the partitions are identical when restricted to \(V – \{x\}\). The \(k\)-Stirling colour graph of \(G\) is defined similarly, but for partitions into exactly \(k\) independent sets. Building on the existing result that for each \(k \geq 3\), the \(k\)-Bell colour graph of a tree with at least 4 vertices is Hamiltonian, we show that every graph on \(n\) vertices, except \(K_n\) and \(K_n – e\), has a Hamiltonian \(n\)-Bell colour graph, and this result is best possible. It is also shown that, for \(k \geq 4\), the \(k\)-Stirling colour graph of a tree with at least \(k+1\) vertices is Hamiltonian.

Several graph decompositions that factorize the determinant of the adjacency matrix isolate a Kőnig–Egerváry part, such as the SD–KE decomposition and the critical independence decomposition of Larson. This suggests that the study of graph unimodularity can be approached, to a large extent, through the structure of Kőnig–Egerváry graphs. In this paper, we advance this point of view by introducing a new determinant factorization within the class of Kőnig–Egerváry graphs. More precisely, given a Kőnig–Egerváry graph \(G\), we consider the partition of \(V(G)\) into its perfect-flower part \(PF(G)\) and its perfect-flower-free part \(PFF(G)\), and prove that \[\det(G)=\det(G[PF(G)])\det(G[PFF(G)]).\] We also obtain the analogous factorization for the permanent. This decomposition provides a new tool for the study of unimodularity, reducing the problem to two induced subgraphs of very different nature: the graph \(G[PF(G)]\), whose structure is closely related to Sterboul–Deming configurations with perfect matchings, and the graph \(G[PFF(G)]\), which is governed by the theory of critical independent sets. In this way, the paper provides a new structural framework for the study of unimodular graphs through Kőnig–Egerváry theory.

In a graph, the distance between two vertices is the length of a shortest path connecting them. The distance-2 domination number \(\gamma_2(G)\) of a graph \(G\) is the minimum size of a vertex subset such that every vertex outside it is within distance two of some subset vertex. In a connected graph, a connected dominating set is a subset \(S\) whose induced subgraph is connected and in which every vertex not in \(S\) is adjacent to some vertex in \(S\); the connected domination number \(\gamma_c(G)\) is the size of a smallest such set. For \(k\ge 1\), let 𝒯_k be the set of trees \(T\) satisfying \(\gamma_c(T)=2\gamma_2(T)=2k\). The collection 𝒯₁ is the set of all double stars. In this paper, we provide a constructive characterization of 𝒯_k for all \(k\ge 2\).

This paper introduces row-major natural ordering labeling (hereafter referred to as the “Natural Square”) to the domino tiling space of the \(4\times4\) square grid and elucidates the structural correspondence between geometric group actions and algebraic invariants. First, based on the 36 complete tilings derived from Kasteleyn theory, these tilings are classified into 9 equivalence classes (hereafter, families) under the action of the dihedral group \(D_4\). Next, phenomena observed through exhaustive computational experiments are analyzed, and it is shown that the sum of the block-product sums for any tiling and its 90-degree rotation is invariably 1,428 (90-Degree Rotation Complement Theorem for Block-Product Sums). Furthermore, algebraic complementary pairs that satisfy power-sum equalities (Prouhet–Tarry–Escott type) across multiple degrees are identified, and the structure of higher-moment preservation phenomena that transcend geometric constraints is discussed.

A tree could be defined as follows. An edge is a tree. If \(T_{k-1}=\cup_{i=1}^{k-1}e_i\) is a tree with \(k-1\) edges \(e_i\), and \(e_k\) an edge, then \(T_k=T_{k-1}\cup e_k\) is a tree if \(T_{k-1}\cap e_k\) is a point. We generalize this construction: A simplex \(S_1\) of dimension \(\ge1\) is a thick tree. If \(G_{k-1}=\cup_{i=1}^{k-1}S_i\) is a thick tree, where \(S_i\) are simplices of dimension \(\ge1\), and \(S_k\) a new simplex of dimension \(\ge1\), then \(G_{k-1}\cup S_k\) is a thick tree if \(G_{k-1}\cap S_k\) is a point. All homological properties of Stanley-Reisner rings of thick trees are well known. We determine the Hilbert series and Betti numbers for Stanley-Reisner rings of skeletons of thick trees. From this one can read of projective dimension, regularity, and judge when they are Cohen-Macaulay.

In this paper we introduce and study the hyper-Mersenne numbers, a class of integer sequences extending the classical Mersenne numbers which arise in a combinatorial and algebraic context. Using generating functions, we derive explicit formulae and identities for these sequences. In particular, we find relations to binomial coefficients and figurate numbers. We also provide a closed-form expression for the determinant of associated matrices, valid in full generality.

A graph \(G\) is \(H\)-saturated if \(G\) does not have \(H\) as a subgraph but \(G + uv\) has at least one copy of \(H\) for any edge \(uv \notin E(G)\). The smallest number of edges of all \(H\)-saturated graphs of order \(n\) is called \(H\)-saturation number and is denoted by \(sat(n; H)\). In this paper, we establish the existence of \(C_{4}\)-saturated graphs with prescribed the number of edges in some length that is close to \(sat(n; C_{4})\).

The Hall number \(h(G)\) of a graph \(G\) is the minimum integer \(k\) such that every \(k\)-list assignment satisfying Hall’s condition on all induced subgraphs of \(G\) admits a proper coloring. In this paper, we investigate graphs for which the Hall number strictly captures list colorability, satisfying the equality \(h(G)=ch(G)\). We confirm a conjecture of Allagan by proving that this equality holds for every complete multipartite graph without singleton parts. For complete \(k\)-partite graphs of the form \(K(m,n,1,\dots,1)\), we establish that \(h(G)=ch(G)\) for all sufficiently large \(n\). Furthermore, we also determine \(h(G)\) for \(2\)-trees and wheel graphs \(W_n\). We show that for a \(2\)-tree \(G\), \(h(G) \in \{1, 2, 3\}\) for \(|V(G)| = 3, 4\), and \(\ge 5\), respectively. For wheel graphs, we demonstrate that \(h(W_n)\) is dictated by the parity of the rim: \(h(W_n)=3\) for odd \(n\ge5\), and \(h(W_n)=4\) for even \(n\ge6\).

For a connected graph \(G\) of order at least two, a total monophonic set of a graph \(G\) is a monophonic set \(S\) such that the subgraph \(G[S]\) induced by \(S\) has no isolated vertices. The minimum cardinality of a total monophonic set of \(G\) is the total monophonic number of \(G\) and is denoted by \(m_{t}(G)\). We determine bounds for it and characterize graphs which realize the lower bound. Also, some general properties satisfied by this concept are studied. It is shown that for positive integers \(a, b\) such that \(3 \leq a \leq b\) with \(b \leq 2a\), there exists a connected graph \(G\) such that \(m(G) = a\) and \(m_t(G) = b\). Further, if \(p, a, b\) are positive integers such that \(4 \leq a \leq b \leq p\), then there exists a connected graph \(G\) of order \(p\) with \(m_t(G) = a\) and \(m_c(G) = b\), where \(m_c(G)\) is the connected monophonic number of \(G\).

The concept of k-extendability is a fundamental notion in matching theory and is closely related to factor-criticality. In a seminal work, Zhang et al. established sharp conditions under which these two concepts are equivalent. In this paper, we study the equivalence between extendability and factor-criticality from the perspective of Sachs subgraphs and discuss conditions under which these notions are equivalent.