In this paper, we explore the enumerative combinatorics of American-style crossword puzzle grids under modified answer length requirements. While standard American-style crossword rules have a minimum answer length of three cells, we generalize this constraint to a minimum length \(m\) for an \(n\times n\) grid. We define \(\lvert Puz (n,m)\rvert\) as the number of such grids satisfying the standard structural rules of connectivity, \(180^\circ\) rotational symmetry, keyed squares, and full dimensionality. We prove that for \(m>\frac{n}{2}\), the number of valid grids is invariant under the transformation \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert\). Furthermore, we establish a closed-form formula for \(\lvert Puz (n,m)\rvert\) when \(m>\frac{n}{2}\). We also verify some counts for smaller grid dimensions verifying previously conjectured values.

Let \(G\) be a graph of order \(n\), maximum degree at most \(\Delta\), and no component of order 2. Inspired by the famous 1-2-3-conjecture, Bensmail, Marcille, and Orenga define a proper pushing scheme of \(G\) as a function \(\rho : V(G) \to \mathbb{N}_{0}\) for which \[\sigma : V(G) \to \mathbb{N}_{0} : u \mapsto (1+\rho(u)) d_G(u) + \sum\limits_{v\in N_G(u)} \rho(v),\] is a vertex coloring, that is, adjacent vertices receive different values under \(\sigma\). They show the existence of a proper pushing scheme \(\rho\) with \(\max\{\rho(u) : u \in V(G)\} \leq \Delta^2\) and conjecture that this upper bound can be improved to \(\Delta\). We show their conjecture for cubic graphs and regular bipartite graphs. Furthermore, we show the existence of a proper pushing scheme \(\rho\) with \(\sum\limits_{u\in V(G)} \rho(u) \leq (2\Delta^2+\Delta)n/6\).

A strongly connected digraph \(D\) is primitive provided the greatest common divisor of the lengths of its directed cycles equals 1. The scrambling index of a primitive digraph \(D\) is the smallest positive integer \(k\) such that for every pair of vertices \(u\) and \(v\), there is a vertex \(w\) such that we can get to \(w\) from \(u\) and \(v\) in \(D\) by directed walks of length \(k\). In this paper, we characterize those primitive doubly symmetric digraphs with the largest scrambling index.

In this paper, we consider the relationship between toughness and the existence of \((g,f)\)-factors with inclusion/exclusion properties. We obtain that if \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\) with \(b > a \geq 2\) and \(a \leq g(x) < f(x) \leq b\) where \(a\), \(b\) are two integers, then for any two given edges \(e_{1}\) and \(e_{2}\), there exists a \((g,f)\)-factor including \(e_{1}\), \(e_{2}\); and a \((g,f)\)-factor including \(e_{1}\) and excluding \(e_{2}\); as well as a \((g,f)\)-factor excluding \(e_{1}\), \(e_{2}\).

Let \(L(G(k))\) be a line graph of a \(k\)-subdivided graph \(G(k)\) of any connected, simple and undirected graph \(G\). In this paper, we fixed the valency dependence invariants of \(L(G(k))\) for \(k\geq2.\) Our results are the generalization of the results proved in [1,3,8].

A star edge coloring of a graph \(G\) is a proper edge coloring in which every path or cycle on four vertices contains at least three distinct colors. The star edge chromatic number of \(G\), denoted by \(\chi^\prime_{\mathrm{st}}(G)\), is the minimum number of colors required for such a coloring. In this paper, we study the star edge chromatic number of several graph classes derived from the Knödel graph \(W_{\Delta,n}\). In particular, we determine bounds and exact values for \(\chi^\prime_{\mathrm{st}}(G)\) for the Knödel graph \(W_{\Delta,n}\), its middle graph \(M\!\left(W_{\Delta,n}\right)\), and its Mycielskian \(\mu\!\left(W_{\Delta,n}\right)\). Furthermore, we provide explicit constructions of star edge colorings that attain these values.

Let \(G\) be a simple connected mixed graph, and let \(H(G)\) denote the Hermitian adjacency matrix of \(G\). The Hermitian permanental polynomial of \(G\) is defined as \(\pi(G; x) = \operatorname{per}(xI – H(G))\), where \(\operatorname{per}(\cdot)\) represents the permanent and \(I\) is the identity matrix. In this paper, we first derive fundamental properties of the Hermitian permanental polynomial for mixed graphs and establish explicit formulas relating its coefficients to those of the characteristic polynomial. We then analyze the root distribution of this polynomial, determining the number of zero roots for several special classes of mixed graphs. Finally, we characterize mixed graphs that remain cospectral under four‑way switching and prove that this operation preserves the permanental spectrum.

The Euler Sombor (\(EU\)) index of a graph \(G\) is defined as \[EU(\mathit{G})=\sum \limits_{{\mathit{u}}{\mathit{v}}\in E(\mathit{G})} \sqrt{deg_G^2(u)+deg_G^2(v)+deg_G(u)deg_G(v)},\] where \(deg_G(u)\) and \(deg_G(v)\) are the degrees of the vertices \(u\) and \(v\) in the graph \(G\), respectively. Biswaranja Khanra and Shibsankar Das [Euler Sombor index of trees, unicyclic and chemical graphs, MATCH Commun. Math. Comput. Chem., 94 (2025) 525–548] posed an open problem to determine the extremal values and extremal graphs of the Euler Sombor index in the class of all connected graphs with a given domination number. In this paper, we solve this open problem for trees with a given domination number. Furthermore, we determine an upper bound for the Euler Sombor index of trees with a given independence number. We also characterize the corresponding extremal trees. Additionally, we propose a set of open problems for future research.

The exponential Randić index of a graph \(G\), denoted by \(ER(G)\), is defined as \(\sum\limits_{uv\in E(G)}e^{\frac{1}{d(u)d(v)}}\), where \(d(u)\) denotes the degree of a vertex \(u\) in \(G\). The line graph \(L(G)\) of a graph \(G\) is a graph in which each vertex represents an edge of \(G\), and two vertices are adjacent in \(L(G)\) if and only if their corresponding edges in \(G\) are incident to a common vertex. In this paper, we proved that for any tree \(T\) of order \(n\ge3\), \(ER(L(T))>\frac{n}{4}e^{\frac{1}{2}}\).

We prove the following necessary conditions for signed graphs on complete graphs to admit additive graceful labelings, thus considerably narrowing down the search for such labelings. If a signed graph on a complete graph \(K_p, ~p\not = 4\), with \(n\) negative and \(m\) positive edges, admits an additively graceful labeling, then (1) \(p\), \(p-2\) or \(p-4\) must be a perfect square, (2) If \(p\) is a perfect square then, both \(m\) and \(n\) are even, (3) If \(p-4\) is a perfect square then, both \(m\) and \(n\) are odd, (4) If \(p-2\) is a perfect square then, \(m\) and \(n\) have opposite parity and (5) The number of odd and even labeled vertices in \(S\) are \(\frac{p+\sqrt{p-i}}{2}\) and \(\frac{p-\sqrt{p-i}}{2}\) according as \(p-i\) is a perfect square, \(i=0,2\) or \(4\). We also provide an example to show that, if a signed graph \(S\) with no negative edges is additively graceful then, \(S\) as a graph need not be graceful. Interestingly, this example also settles 3 more open problems concerning gracefulness and edge consecutive gracefulness (ecg), thereby demonstrating that ecg or \(m\)-gracefulness is not a reliable measure of gracefulness.