Given a network modeled as a graph, a detection system is a subset of vertices equipped with “detectors” that can uniquely identify an “intruder” anywhere in the graph. We consider two types of detection systems: open-locating-dominating (OLD) sets and identifying codes (ICs). In an OLD set, each vertex has a unique, non-empty set of detectors in its open neighborhood; meanwhile, in an IC, each vertex has a unique, non-empty set of detectors in its closed neighborhood. We explore one of their fault-tolerant variants: redundant OLD (RED:OLD) sets and redundant ICs (RED:ICs), which ensure that removing/disabling at most one detector retains the properties of OLD sets and ICs, respectively. This paper focuses on constructing optimal RED:OLD sets and RED:ICs on the infinite king grid, and presents the proof for the bounds on their minimum densities; \(\left[\frac{3}{10}, \frac{1}{3}\right]\) for RED:OLD sets and \(\left[\frac{3}{11}, \frac{1}{3}\right]\) for RED:ICs.

Exploring the vulnerability of any real-life network helps designers understand how strongly components or elements of the network are connected and how well they can function if there is any disruption. Any chemical structure can also be considered as a network in which the atoms correspond to the vertices, and the chemical bonds between the atoms correspond to the edges. Let \(G=(V, E)\) represent any simple graph with vertex set \(V\) and edge set \(E\). The vulnerability measure used in this paper is the paired domination integrity, defined as the minimum of the sum of any paired dominating set \(S\) of a graph \(G\) and the order of the largest component in the induced subgraph of \(V-S\). The minimum is found by considering all possible paired dominating sets of \(G\). In this paper, we obtain the paired domination integrity of the comb product of paths and cycles. In addition, we extend the study of graph vulnerability to chemical structures.

Let \(k, b, n\) be positive integers such that \(b\geq 2\). Denote by \(S(k,b,n)\) the numerical semigroup generated by \(\left\{b^{k+n+i}+\frac{b^{n+i}-1}{b-1}\mid i\in\mathbb{N}\right\}\). In this paper, we give formulas for computing the embedding dimension and the Frobenius number of \(S(k,b,n)\).

Given a connected graph \(G=(V,E)\) of order \(n\ge 2\) and two distinct vertices \(u,v\in V(G)\), consider two operations on \(G\): the \(k\)-multisubdivision and the \(k\)-path addition. Let \(msd_{\gamma_c}(G)\) and \(pa_{\gamma_c}(G)\) denote, respectively, the connected domination multisubdivision and path addition numbers of \(G\). In both operations, \(k\) represents the number of vertices added to \(V(G)\), resulting in a new graph denoted by \(G_{u,v,k}\). We prove that \(\gamma_c(G) \le \gamma_c(G_{u,v,k})\) for \(k = msd_{\gamma_c}(G) \in \{1,2,3\}\) in the case of \(k\)-multisubdivision, where \(uv \in E(G)\). Additionally, we show that \(\gamma_c(G) – 2 \le \gamma_c(G_{u,v,k})\) for \(k = pa_{\gamma_c}(G) \in \{0,1,2,3\}\) in the case of \(k\)-path addition, where \(uv \notin E(G)\), and provide both necessary and sufficient conditions under which these inequalities hold.

This paper introduces two novel sequences: the \(k-\)-division Fibonacci–Pell polynomials and the \(k-\)-division Gaussian Fibonacci–Pell polynomials. Building on the well-known Fibonacci and Pell sequences, these new sequences are defined using a division-based approach, enhancing their combinatorial and algebraic properties. We present explicit recurrence relations, generating functions, combinatorial identities, and Binet-type formulas for these sequences. A significant contribution of the study is the factorization of the Pascal matrix via the Riordan group method using the proposed polynomials. Two distinct factorizations are derived, highlighting the algebraic structure and combinatorial interpretations of the \(k-\)-division polynomials. The work not only generalizes known polynomial sequences but also provides new insights into their matrix representations and applications.

This paper provides new lower bounds for van der Waerden numbers using Rabung’s method, which colors based on the discrete logarithm modulo some prime. Through a distributed computing project with 500 volunteers over one year, we checked all primes up to 950 million, compared to 27 million in previous work. We point to evidence that the van der Waerden number for \(r\) colors and progression length \(k\) is roughly \(r^k\).

Lightweight design is widely used for optimizing machinery. This paper proposes an algebraic–topology–based structural optimization method that formulates a mathematical model for mechanical equipment. The model is solved via sequential linear programming and recast as a function-optimization problem addressed by a Memetic algorithm combining a Newtonian local search, adaptive multipoint crossover, and stochastic variability. Using a bridge crane main girder as a case study, we minimize cross-sectional area with selected sectional parameters as design variables and constraints from the Crane Design Manual. With population size 100 and 300 maximum iterations, the optimized girder achieves a 13% weight reduction. Static and dynamic analyses confirm that strength and stiffness satisfy safe working conditions.

Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a seminal paper, Berger and Shor [1], in 1990, developed initial upper bounds for the FAS problem in general directed graphs. Here we find asymptotic lower bounds for the FAS problem in a class of random, oriented, directed graphs derived from the Erdős-Rényi model \(G(n,M)\), with n vertices and M (undirected) edges, the latter randomly chosen. Each edge is then randomly given a direction to form our directed graph. We show that \[Pr\left(\textbf{Y}^* \le M \left( \frac{1}{2} -\sqrt{\frac{\log n}{\Delta_{av}}}\right)\right),\] approaches zero exponentially in \(n\), with \(\textbf{Y}^*\) the (random) size of the minimum feedback arc set and \(\Delta_{av}=2M/n\) the average vertex degree. Lower bounds for random tournaments, a special case, were obtained by Spencer [13] and de la Vega [3] and these are discussed. In comparing the bound above to averaged experimental FAS data on related random graphs developed by K. Hanauer [8] we find that the approximation \(\textbf{Y}^*_{av} \approx M\left( \frac{1}{2} -\frac{1}{2}\sqrt{\frac{\log n}{\Delta_{av}}}\right)\) lies remarkably close graphically to the algorithmically computed average size \(\textbf{Y}^*_{av}\) of minimum feedback arc sets.

An alternative proof of A.B. Evans’ result on the existence of strong complete mappings on finite abelian groups is presented. Applications of strong complete mappings in computing the chromatic numbers of~certain Cayley graphs are discussed.

Let \(G = (V, E)\) be a simple graph. A subset \(D \subseteq V\) is called a dominating set of \(G\) if every vertex in \(V\) is either in \(D\) or has a neighbour in \(D\). A subset \(D \subseteq V\) is called an equitable dominating set of \(G\) if for every vertex \(v \in V \setminus D\), there exists a vertex \(u \in D\) such that \(uv \in E(G)\) and \(\lvert d_G(u) – d_G(v) \rvert \leq 1\). The minimum cardinality of an equitable dominating set of \(G\), denoted by \(\gamma^{e}(G)\), is called the equitable domination number of \(G\). In this paper, we study the equitable domination number of certain graph operators such as the double graph, the Mycielskian, and the subdivision of a graph.

This paper studies the Pell-Narayana sequence modulo \(m\). It starts by defining the Pell-Narayana numbers and examining their combinatorial relationships with well-known sequences and functions, including Eulerian, Catalan, and Delannoy numbers. Building on this, the concept of a Pell-Narayana orbit is introduced for a 2-generator group with generating pair \((x, y) \in G\), which allows the analysis of the periods of these orbits. The results include explicit calculations of the Pell-Narayana periods for polyhedral and binary polyhedral groups, depending on the choice of generating pair \((x, y)\), along with a discussion of their properties. Furthermore, the paper determines the periodic lengths of Pell-Narayana orbits for the groups \(Q_8, Q_8 \times \mathbb{Z}_{2m},\) and \(Q_8 \times_\varphi \mathbb{Z}_{2m}\) for all \(m \geq 3\).

A graph \(G=(V,E)\) is \(H\)-supermagic if there exists a bijection \(f\) from the set \(V\cup E\) to the set of integers \(\{1,2,3,\dots,|V|+|E|\}\), called \(H\)-supermagic labeling such that the sum of labels of all elements of every induced subgraph of \(G\) isomorphic to \(H\) is equal to the same integer and all vertex labels are in \(\{1,2,3,\dots,|V|\}\). We present a \((K_4-e)\)-supermagic labeling of the triangular ladder \(TL_{2n}\) for any \(n\geq2\).

Slilaty and Zaslavsky (2024) characterized all single-element extensions of graphic matroids in terms of a graphical structure called a cobiased graph. In this paper we characterize all orientations of a single-element extension of a graphic matroid in terms of graphically defined orientations of its associated cobiased graph. We also explain how these orientations can be canonically understood as dual to orientations of biased graphs if and only if the underlying graph is planar.

We consider a combinatorial question about searching for an unknown ideal \(\mu\) within a known pointed poset \(\lambda\). Elements of \(\lambda\) may be queried for membership in \(\mu\), but at most \(k\) positive queries are permitted. We provide a general search strategy for this problem, and establish new bounds (based on \(k\) and the degree and height of \(\lambda\)) for the total number of queries required to identify \(\mu\). We show that this strategy performs asymptotically optimally on the family of complete \(\ell\)-ary trees as the height grows.

Graph theory serves as a central and dynamic framework for the design and analysis of networks. Convex polytopes, as fundamental geometric entities, encompass a rich variety of mathematical structures and problems. The basic theory of convex polytopes involves the study of faces, normal cones, duality—particularly polarity—along with separation and other elementary concepts. A convex polytope can be described as a convex set of points within the \(n\)-dimensional Euclidean space \(\Re^{n}\). Among the various dimensions, the partition dimension is the most challenging, and determining its exact value is an NP-hard problem. In this work, we establish bounds for the partition dimension of convex polytopes \(T_\nu\), \(R_\nu\), and \(U_\nu\).

In \(1941\) Dushnik and Miller introduced the concept of dimension of a poset. In \(2020\) Bhavale and Waphare introduced the concept of an RC-lattice as a lattice in which all the reducible elements are lying on a chain. In this paper, we introduce the concept of a complete fundamental basic block and prove that its dimension is at the most three. Consequently, we prove that the dimension of an RC-lattice on \(n\) elements is at the most three. Further, we prove that an RC-lattice is non-planar if and only if its dimension is three.

For a graph, a smallest-last (SL) ordering is formed by iteratively deleting a vertex with smallest degree, then reversing the resulting list. The SL algorithm applies greedy coloring to a SL ordering. For a given vertex coloring algorithm, a graph is hard-to-color (HC) if every implementation of the algorithm results in a nonoptimal coloring. In 1997, Kubale et al. showed that \(C_{8}^{2}\) is the unique smallest HC graph for the SL algorithm. Extending this, we show that for \(k\geq4\), \(k+4\) is the smallest order of a HC graph for the SL algorithm with \(\chi\left(G\right)=k\). We also present a HC graph for the SL algorithm with \(\chi\left(G\right)=3\) that has order 10.

Cut vertices are often used as a measure of nodes’ importance within a network. These are nodes whose failure disconnects a connected graph. Let \(N(G)\) be the number of connected induced subgraphs of a graph \(G\). In this work, we investigate the maximum of \(N(G)\) where \(G\) is a unicyclic graph with \(n\) nodes of which \(c\) are cut vertices. For all valid \(n,c\), we give a full description of those maximal (that maximise \(N(.)\)) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of \(n,c\), however, there is a unique maximal unicyclic graph with \(n\) nodes and \(c\) cut vertices. In particular, the well-known negative correlation between the number of connected induced subgraphs of trees and the Wiener index (sum of distances) fails for unicyclic graphs with \(n\) nodes and \(c\) cut vertices: for instance, the maximal unicyclic graph with \(n=3,4\mod 5\) nodes and \(c=n-5>3\) cut vertices is different from the unique graph that was shown by Tan et al. [The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices. J. Appl. Math. Comput., 55:1–24, 2017] to minimise the Wiener index. Our main characterisation of maximal unicyclic graphs with respect to the number of connected induced subgraphs also applies to unicyclic graphs with \(n\) nodes, \(c\) cut vertices and girth at most \(g>3\), since it is shown that the girth of every maximal graph with \(n\) nodes and \(c\) cut vertices cannot exceed \(4\).

The honeymoon Oberwolfach problem HOP\((2m_1,2m_2,\ldots,2m_t)\) asks the following question. Given \(n=m_1+m_2+\ldots +m_t\) newlywed couples at a conference and \(t\) round tables of sizes \(2m_1,2m_2,\ldots,2m_t\), is it possible to arrange the \(2n\) participants at these tables for \(2n-2\) meals so that each participant sits next to their spouse at every meal, and sits next to every other participant exactly once? A solution to HOP\((2m_1,2m_2,\ldots,2m_t)\) is a decomposition of \(K_{2n}+(2n-3)I\), the complete graph \(K_{2n}\) with \(2n-3\) additional copies of a fixed 1-factor \(I\), into 2-factors, each consisting of disjoint \(I\)-alternating cycles of lengths \(2m_1,2m_2,\ldots,2m_t\). The honeymoon Oberwolfach problem was introduced in a 2019 paper by Lepine and Šajna. The authors conjectured that HOP\((2m_1,2m_2,\ldots,\) \(2m_t)\) has a solution whenever the obvious necessary conditions are satisfied, and proved the conjecture for several large cases, including the uniform cycle length case \(m_1=\ldots=m_t\), and the small cases with \(n \le 9\). In the present paper, we extend the latter result to all cases with \(n \le 20\) using a computer-assisted search.

We introduce and investigate a new class of graph maps, called backward edge-preserving maps. These are the maps between the vertex sets of graphs such that the pre-image of every edge in the target graph is an edge in the source graph. We give a complete structural characterization of such maps for both general and connected graphs. We also explore the relationship between backward edge-preserving maps, metric maps, and graph homomorphisms, and establish criteria for the intersection of these classes. Furthermore, we study a related class of graph cohomomorphisms and establish conditions under which a map can simultaneously be a homomorphism and a cohomomorphism.

A directed star is a star digraph in which the centre is either a sink or a source. With every directed star, we associate a weight \(w\left(\alpha\right)\). Let \(D\) be a digraph; and \(C\), a spanning subgraph of \(D\); in which every component is a directed star. Then \(C\) is called a directed star cover of \(D\), and the weight of \(C\) is \(w(C)=\prod_{\alpha}w\left(\alpha\right)\), where the product is taken over all the components \(\alpha\) of \(C\). The directed star polynomial of \(D\) is \[E\left(D;\mathbf{w}\right)=\sum w(C),\] where the sum is taken over all the directed star covers of \(D\). The paper establishes properties of star polynomials and establishes relationships between star polynomials, source polynomials (where all components are source stars), and sink polynomials (where all components are sink stars). Furthermore, it presents methods to compute these polynomials for general digraphs. We derive formulae for the star polynomials of rooted products of digraphs. Moreover, we establish applications of these polynomials to several domination parameters and obtain results regarding these polynomials and independent sets in undirected graphs.

Let \(G\) be an undirected graph. The \(k\)-strong labeling (coloring) number of \(G\), \(\chi_k(G)\), is the minimum number of labels (colors) necessary to label all the vertices of \(G\) so that no two vertices that are exactly of distance \(k\) apart have the same label. \(\chi_1\) is the usual chromatic number. In this article it is shown that any linear operator on the set of graphs on \(n\) vertices thar preserves \(\chi_k\) is a vertex permutation.

Cartesian-product networks combine well-studied graphs to create new structures with inherited properties, making them valuable for interconnection networks and parallel algorithms. Cycle decompositions of these networks are crucial for fault tolerance and adaptive routing. In this paper, we address the hypercube version of the Oberwolfach problem, focusing on decompositions of \(Q_n\) into cycles of equal or unequal lengths. We present an algorithm that enumerates all possible cycle types in \(Q_n\) and determine which decompositions are feasible or infeasible for \(Q_4\). Using an inductive approach, we extend these results to \(Q_n\) by leveraging distinct perfect matchings of \(Q_4\), yielding a variety of cycle decompositions. Additionally, we present results on factorizations of \(Q_n\) when \(n\) is a power of \(2\). These findings enhance the understanding of cycle structures in hypercubes and their applications to interconnection networks.

We investigate the combinatorial structure of edge-disjoint triangle packings in the complete graph \(K_n\). Two triangles are said to be edge-disjoint if they share no common edges, though they may share at most one vertex. For a given \(n\), let \(T_n\) denote the total number of subsets of triangles in \(K_n\) that are pairwise edge-disjoint, including the empty set, and let \(T_n^k\) denote the number of \(k\)-element sets of such triangles. In this article, we establish: (i) a general recurrence relation for \(T_n\) that enables asymptotic analysis, yielding the growth \(\log T_n = \Theta(n^2 \log n)\) for large \(n\); (ii) exact closed-form formulas for the number of edge-disjoint pairs (\(T_n^2\)), triples (\(T_n^3\)), and quadruples (\(T_n^4\)) of triangles in \(K_n\) for \(n \geq 6\). These results extend classical work on Steiner Triple Systems and provide new tools for analyzing triangle packings in complete graphs.