A cancellable fraction is a displayed numerator–denominator pair in which deleting the same decimal digit from the numerator and denominator leaves the represented rational number unchanged. We study vertical cancellations, where the deleted digits occur in the same decimal position in the numerator and denominator. Fix a nonzero digit \(h\). Let \(C_h(n)\) denote the number of marked vertical cancellations of the digit \(h\) among numerator–denominator pairs \((N,D)\), where \(N\) and \(D\) are both \(n\)-digit positive integers and \(D<N\). Here marked means that the cancelled position is part of the data. We prove that \[C_h(n)=O_h(n^2 10^{n-1}).\] Since the number of such displayed pairs \((N,D)\) is of order \(10^{2n}\), the proportion of vertically \(h\)-cancellable pairs is \(O_h(n^2/10^n)\). Thus vertical \(h\)-cancellability is exponentially rare. We also give an explicit family showing that \(C_h(n)\ge c_h10^n\) for all sufficiently large \(n\), and we include exact enumerations for small values of \(n\). Finally, we formulate a uniqueness conjecture asserting that almost every marked vertical cancellation belongs to a pair that is cancellable in exactly one vertical way.

A vertex set \(D\) in a finite undirected graph \(G\) is an efficient dominating set (e.d.s. for short) of \(G\) if every vertex of \(G\) is dominated by exactly one vertex of \(D\). The Efficient Domination (ED) problem asks for the existence of an e.d.s. in \(G\). The Weighted Efficient Dominating Set (WED for short) problem further asks for an e.d.s. of minimum/maximum weight in a given graph \(G\). The ED problem is known to be NP-complete, even for claw-free graphs, for \(P_7\)-free graphs, for chordal bipartite graphs, for planar bipartite graphs of maximum degree 3 and girth at least \(g\) for every fixed \(g\), and thus for \(C_4\)-free bipartite graphs. This manuscript reports a study on the WED problem for \(C_4\)-free bipartite graphs (in the context of a study for bipartite graphs) and shows that the WED problem can be solved in polynomial time for (\(S_{1,2,5},C_4\))-free bipartite graphs, for (\(P_{10},C_4\))-free bipartite graphs, and for some related graphs classes.

In this note, we give two simple bijections between compositions over groups and colorings of cycles. These bijections immediately imply the formulas for the number of \(m\)-compositions over a finite group.

Let \(G=(V(G),E(G))\) be a simple, finite and undirected graph of order \(p\) and size \(q\). For \(k\ge 1\), a bijection \(f: V(G)\cup E(G) \to \{k, k+1, k+2, \ldots, k+p+q-1\}\) such that \(f(uv)= |f(u) – f(v)|\) for every edge \(uv\in E(G)\) is said to be a \(k\)-super graceful labeling of \(G\). We say \(G\) is \(k\)-super graceful if it admits a \(k\)-super graceful labeling. In this paper, we study the \(k\)-super gracefulness of some complete multi-partite graphs.

Let \(G\) be a graph, or digraph, and let \(P=\{P_1,\dots,P_k\}\) be a partition of its vertex set. We solve the following problem: find the generating function, in the edge variables of \(G\), of the spanning trees of \(G\) each of whose restrictions to every part \(P_i\) is a spanning tree of the induced subgraph \(G[P_i]\); and, in the directed case with a fixed root \(v_i\in P_i\) for each \(i\), of the spanning arbors of \(G\) rooted at \(v_1\) each of whose restrictions to \(P_i\) is a spanning arbor of \(G[P_i]\) rooted at \(v_i\). We show that both generating functions factor as a product of the local generating functions on the parts \(G[P_i]\) (or \(P_i\), in the digraph case) with the generating function of spanning trees/arbors of a naturally associated contracted multigraph whose vertices are the parts of \(P\). This localizes the classical theorems of Kirchhoff and Tutte and yields an exact identity, and a family of lower bounds, for the number of spanning trees of \(G\) in terms of spanning-tree counts of smaller induced subgraphs.

A \(2\)-factored dominating set (\(2\)fd-set) of a graph \(G=(V,E)\) is a dominating set \(F\subseteq V\) such that the induced subgraph \(G[F]\) is \(2\)-regular, and hence is a disjoint union of cycles. In this study, \(2\)-factored dominating sets on fixed-width grid graphs of dimensions \(m \times n\), where \(m \in \{2,3,4\}\), are enumerated. We establish theorems describing the generating functions with respect to the number of \(2\)-factored dominating sets in these grid graphs. The number of \(2\)-factored dominating sets grows exponentially with \(n\), with growth constant determined by the dominant singularity of the generating function.

A Boolean network maps Boolean configurations of fixed length to themselves. A trapspace is an invariant subcube; a principal trapspace is the smallest trapspace containing a configuration, while a minimal trapspace contains no proper trapspace. Commutative Boolean networks are those whose local updates commute. We connect these concepts through five contributions. First, we introduce trapping graphs and trapping closures, define trapping networks by transitivity of their general asynchronous graphs, and prove that they are exactly the trapping closures. Second, we show that two Boolean networks have the same collections of principal trapspaces if and only if they have the same trapping closure. Hence, trapping networks provide a normal form for trapspace analysis. We also characterize the possible collections of principal and minimal trapspaces. Third, we prove that commutative networks are trapping and classify their principal trapspaces. Fourth, we study bijective commutative networks, called Marseille networks, and give equivalent characterizations and classifications. Fifth, we study idempotent commutative networks, called Lille networks, relate them to globally idempotent networks, prove that globally idempotent networks are trapping, and provide equivalent characterizations. These results clarify the relationships among asynchronous, general asynchronous, and trapping graphs and describe the structure of trapping networks.

The Ramsey number \(R(G)\) of a graph \(G\) without isolated vertices is the minimum positive integer \(n\) such that for every red-blue coloring of the complete graph \(K_n\) of order \(n\), there is a subgraph isomorphic to \(G\) all of whose edges are colored the same (a monochromatic \(G\)). A Ramsey chain in a graph \(G\) with a red-blue coloring is a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{k}\) of pairwise edge-disjoint monochromatic subgraphs of \(G\) such that \(G_i\) has \(i\) edges for \(1 \le i \le k\) and \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le k-1\). The subgraphs in a Ramsey chain are the links of the chain and the terminal subgraph \(G_k\) is the target link of the chain. A graph \(H\) without isolated vertices is called a target graph if there exists a positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a Ramsey chain with target link \(H\). The target Ramsey number \(TR(H)\) of \(H\) is the minimum positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a Ramsey chain with target link \(H\). The target Ramsey number \(TR(s)\) of a Ramsey chain \(s\) is the minimum positive integer \(n\) such that \(s\) is a Ramsey chain in every red-blue coloring of \(K_{n}\). We investigate graphs \(H\) with the property that \(TR(s) =TR(H)= R(H)\) for every Ramsey chain \(s\) with target link \(H\). It is shown that every graph \(H\) with relatively small size has this property. Other results and open questions are also presented.

The sum graph \(G^{+}(S)\) of a finite subset \(S\subset \mathbb{N}\)={1,2,3,…} is the graph (V,E) where V=S and \(uv\in\)E if and only if \(u+v\in\) S. This concept was introduced by Harary [9], where some basic properties of the family of all sum graphs were presented. In [10], Harary extended this definition into an integral sum graph and proposed some open problems. Motivated by these definitions, we introduce a graph called perfect difference graph. We investigate the properties of this family of graphs.

We study the Equivalent Local Sequence Problem (ELSP) for simple undirected graphs using Bouchet’s isotropic-system formalism and normal matrices over \(\mathbb F_2\). Although Bouchet’s theory characterizes graph local equivalence in polynomial time, converting normal-matrix certificates into explicit graph transformations remains challenging. We introduce the Normal-Matrix Factorization Problem (NMFP), which asks whether a normal-matrix witness of local equivalence has a graph-compatible factorization into elementary transformations. Whenever such a factorization exists, an explicit local-complementation sequence can be recovered in polynomial time. Thus, the constructive part of ELSP reduces to NMFP, identifying normal-matrix factorization as its main unresolved algebraic difficulty. We apply this framework to undirected Paley graphs. In contrast to the directed case, whose local-complementation dynamics are abelian and admit linear inversion, the undirected case is noncommutative and has a more intricate stabilizer structure. Using normal matrices, we analyze Paley-graph orbits and stabilizers, derive algebraic constraints on stabilizing transformations, and completely verify the first undirected Paley graph \(P_5\). These results establish NMFP as central to constructive local equivalence and reveal connections among isotropic systems, graph transformations, and algebraic stabilizers.