In this paper, we prove that if a graph does not contain any cycle of length greater than \(4\), then the square of its line graph is perfect. As an application, we give a concise proof of a known result: the strong chromatic index of a bipartite graph that does not contain any cycle of length greater than \(4\) is at most \(\Delta^2\), where \(\Delta\) represents the maximum degree of the graph. This latter result provides a partial affirmative answer to some known conjectures on upper bounds for the strong chromatic index of graphs.

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.

We relate two decompositions that isolate König–Egerváry structure: the SD–KE decomposition, defined by the classical Edmonds–Sterboul–Deming obstructions, and Larson’s critical independence decomposition, whose complement is \(2\)-bicritical. Let \(I\) be a maximum critical independent set, set \(L(G)=I\cup N_G(I)\), \(L^c(G)=V(G)\setminus L(G)\), and \(B=N_G(I)\). We first prove a normal form for maximum matchings: each maximum matching is obtained from a maximum matching of \(G[L^c(G)]\), a matching crossing from a subset \(X\subseteq B\) into exposed vertices on the \(L^c(G)\) side, and a maximum matching of \(G[L(G)-X]\). The possible sets \(X\) are the crossing profiles. For a crossing profile \(X\) and a maximum matching \(P\) of \(G[L(G)-X]\), view \(P\) as a matching of \(G[L(G)]\). Let \(\Lambda_I(G)\) be the union of the vertices on \(P\)-augmenting paths in \(G[L(G)]\), over all crossing profiles and all residual maximum matchings. We prove \(SD(G)=L^c(G)\cup\Lambda_I(G),\) and \(KE(G)=L(G)\setminus\Lambda_I(G).\) Thus the SD vertices on the Larson König–Egerváry side are precisely those reached by augmenting corridors forced by admissible crossings.

An edge labeling of a graph \(G = (V, E)\) is said to be local antimagic if it is a bijection \(f:E \to\{1,\ldots ,|E|\}\) such that for any pair of adjacent vertices \(x\) and \(y\), \(f^+(x)\not= f^+(y)\), where the induced vertex label \(f^+(x)= \sum f(e)\), with \(e\) ranging over all the edges incident to \(x\). The local antimagic chromatic number of \(G\), denoted by \(\chi_{la}(G)\), is the minimum number of distinct induced vertex labels over all local antimagic labelings of \(G\). In this paper, we study local antimagic labeling of three disjoint cycles with at least two odd cycles, one of which is \(C_3\). We prove that (1) \(\chi_{la}(C_3+C_3+C_3)=5\) and \(\chi_{la}(C_3+C_3+C_{k})=4\) for \(k\geq 4\); (2) \(\chi_{la}(C_3+C_4+C_{2k+1})=4\); (3) \(\chi_{la}(C_3+C_6+C_{4k+1})=3\); (4) \(\chi_{la}(C_3+C_{10}+C_{8k-3})=3\); (5) \(\chi_{la}(C_3+C_5+C_{14})=4\) and \(\chi_{la}(C_3+C_5+C_{4k+2})=3\) for \(k\neq3\); (6) \(\chi_{la}(C_3+C_{4k+1}+C_{4k+5})=3\) and \(\chi_{la}(C_3+C_{4k+1}+C_{4k+6})=3\).

This paper identifies and corrects invalid arguments in [Edge \(k\)-Product Cordial Labeling of Graphs, Eur. J. Pure Appl. Math., 18(2), Article No. 5887 (2025)]. In particular, several published statements are shown to be false through explicit counterexamples. Revised versions of these results are established under appropriate conditions, often involving structural properties such as girth. Correct bounds or conditions are obtained for specific graph classes, including shadow graphs, splitting graphs of stars, and path unions of cycles. These corrections clarify the limitations of the earlier claims and provide a more accurate foundation for further study of edge \(k\)-product cordial labeling.

This work introduces Combinatorial Grid Sequencing (CGS), an axiomatic combinatorial theory inspired by certain patterns of concrete-casting works in multi-storey building construction. By incorporating elementary number theory and max-plus algebra, we derive several theorems that characterize the inherent properties of CGS systems. Notably, the development of an explicit inverse map within this framework led to the independent discovery of three number-theoretic identities involving the floor function. The theory provides a rigorous framework for developing algorithms to model real-world problems categorized as CGS problems. We demonstrate that this approach offers a time-efficient, systematic computational model capable of significantly accelerating certain complex optimization tasks for engineers.

It is known that an automorphism group \(G\) acting on a symmetric, uniform, and balanced incidence structure \({\cal D}\) has the same number of orbits on the set of points and the set of lines of \({\cal D}\). Moreover, a group \(G\) induces a tactical decomposition of \({\cal D}\). These facts are often used to perform efficient constructions of various combinatorial designs and other incidence structures. In this paper, we use a variation of this approach to construct Hadamard 3-balanced incidence structures by employing an automorphism of order 3. We are also able to reach structures with a small automorphism group.

A signed Roman dominating function (SRDF) on \(G=(V,E)\), a finite, connected, simple graph is a mapping \(f : V \to \{-1, 1, 2\},\) such that

(a) For every vertex \(x \in V\), \(\sum\limits_{y \in N[x]} f(y) \ge 1,\) where \(N[x]\) denotes the closed neighborhood of \(x\), consisting of \(x\) together with all vertices adjacent to \(x\).

(b) Every vertex \(x \in V\) with \(f(x) = -1\) is adjacent to at least one vertex \(y \in V\) such that \(f(y) = 2\).

The weight of an SRDF is defined as \(\sum\limits_{v \in V(G)} f(v)\). The signed Roman domination number (SRDN) of \(G\), denoted by \(\gamma_{SR}(G)\), is the minimum possible weight among all signed Roman dominating functions on \(G\). In this work, we determine the signed Roman domination number of the ladder graph \(LG_n\) and its complement \(LG_n^c\).