Let \(G\) be a graph of a network system with vertices, \(V(G)\), representing physical locations and edges, \(E(G)\), representing informational connectivity. A locating-dominating (LD) set \(S \subseteq V(G)\) is a subset of vertices representing detectors capable of sensing an “intruder” at precisely their location or at some unknown point in their open-neighborhood. An LD set must be capable of locating an intruder anywhere in the graph using this collection of detectors. We explore three types of fault-tolerant LD sets: redundant LD sets, which allow at most one detector to be removed or disabled, error-detecting LD sets, which allow at most one false negative, and error-correcting LD sets, which allow at most one error (false positive or false negative). In particular, we determine lower and upper bounds for the minimum density of these three fault-tolerant locating-dominating sets in the infinite king grid.

Several necessary properties of König–Egerváry graphs involving the core, the corona, and critical independent sets are by now part of the folklore of the theory, and have motivated different lines of research within the same framework. In particular, every König–Egerváry graph satisfies the core–corona identity \(|core(G)|+|corona(G)|=2\alpha(G),\) the covering relation \(corona(G)cup N(core(G))=V(G),\) and the fact that \(core(G)\) is a critical independent set. Each of these conditions captures a different aspect of the interaction between maximum independent sets and matchings, but none of them alone characterizes the König–Egerváry property. In this note we show that their conjunction does: a graph \(G\) is König–Egerváry if and only if the above two core–corona conditions hold and \(core(G)\) is critical. Equivalently, the class of König–Egerváry graphs is precisely the intersection of the three graph families determined by these conditions. We also provide examples showing that the characterization is sharp: any two of the three conditions may hold in a graph which is not König–Egerváry.

Let \(\alpha(G)\), \(\mu(G)\) and prk\((G)\) denote the independence number, the matching number and the permanental rank of \(G\), respectively. Here prk\((G)\) is the maximum order of a principal submatrix with nonzero permanent of the adjacency matrix of \(G\). Let \(d(G)=\max_{S\subseteq V(G)}\{|S|-|N(S)|\}\) be the critical difference of \(G\). Let core\((G)\) and ker\((G)\) be the intersection of all maximum independent sets and all critical independent sets, respectively. In this note we use Larson’s critical independence decomposition to split the graph into two induced subgraphs, \(L_G\) and \(L_G^c\), where \(L_G\) is Kőnig–Egerváry and \(L_G^c\) is 2-bicritical. We prove that for every graph \(G\) one has \(\alpha(G)-\mu(G) = |L_G|-prk(L_G)+\alpha(L_G^c)-\mu(L_G^c) = d(L_G)+\alpha(L_G^c)-\mu(L_G^c).\) Moreover, we show that \(\alpha(L_G^c)\le \mu(L_G^c)\) and establish the refined kernel bound \(d(L_G)+k\le |ker(G)|,\) where \(k\) is the number of nontrivial connected components of \(L_G\) without a perfect matching. Consequently, \(\alpha(G)-\mu(G)+k\le |ker(G)|.\) In particular, when \(\alpha(G)>\mu(G)\), one has \(|L_G|>prk(L_G)\). The bound is sharp for every prescribed value of \(k\). Since ker\((G)\subseteq core(G)\) for every graph, we recover as a consequence the known Boros–Golumbic–Levit inequality \(\alpha(G)-\mu(G)+1\le |core(G)|\) for connected graphs with at least two vertices and \(\alpha(G)>\mu(G)\). This result improves on related results by Hammer et al. (1982) and by Levit and Mandrescu (1999).

A pair of letters \(x\) and \(y\) are said to alternate in a word \(w\) if, after removing all letters except for the copies of \(x\) and \(y\) from \(w\), the resulting word is of the form \(xyxy\ldots\) (of even or odd length) or \(yxyx\ldots\) (of even or odd length). A graph \(G = (V(G), E(G))\) is word-representable if there exists a word \(w\) over the alphabet \(V(G)\) such that two distinct vertices \(x, y \in V(G)\) are adjacent in \(G\) (i.e., \(xy \in E(G)\)) if and only if the letters \(x\) and \(y\) alternate in \(w\). A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Word-representability of split graphs has been studied in a series of papers in recent years. Partial progress has been made in characterizing word-representable split graphs through minimal forbidden induced subgraphs, but a complete classification remains open. In this work, we study a specific subclass: split graphs with an independent set of size four, and we provide a minimal forbidden induced subgraph characterization of word-representable graphs in this class as a step towards addressing the broader classification problem. The subclass we study also corresponds to an open problem posed by Kitaev and Pyatkin. In addition, we outline possible approaches and proof strategies that may lead to a complete characterization of word-representable split graphs.

We consider the encoding of graph problems as Quadratic Unconstrained Binary Optimization (QUBO) problems, solvable by quantum or classical annealers. However, nowhere-zero flows have not previously been included among graph problems encoded as QUBO problems. Nowhere-zero flows are related to Tutte’s \(5\)-flow conjecture and occur in many contexts in graph theory. We provide a QUBO Hamiltonian encoding of nowhere-zero flows and prove the correctness of the construction. The resulting Hamiltonian \(H_{\mathrm{mod},k}\) has zero ground-state energy if and only if the graph \(G\) has a nowhere-zero \(\mathbb{Z}_k\)-flow. By Tutte’s equivalence theorem, zero ground energy is equivalent to \(\varphi(G)\le k\), and the zero-energy degeneracy is given by the flow polynomial \(F(G;k)\). The construction uses one-hot variables for edge flow residues modulo \(k\) and auxiliary variables for the per-vertex modular quotient. We prove that correctness is independent of the choice of orientation, root vertex, and positive penalty weights. We verify the construction on \(59\) graph and \(k\) examples, including both yes-instances and no-instances. We also sweep orientations and root choices on selected robustness instances and test a finite suite of positive penalty weights. The Hamiltonian is implemented using the dimod.BinaryQuadraticModel class, compatible with the D-Wave Ocean SDK. Quantum-hardware runs and claims about potential speedup are left to future work.

Measures of spread of information are introduced, with applications to neuronal activity in regions of a brain or to the design of artificial robotic networks in which efficient transmission of information is sought. We make links to spectral connectivity measures in graphs, such as spanning trees and higher-order diameters (as defined here). The exposition is then specialized to regular graphs by developing a formula that expresses the number of spanning trees in terms of walks in the complementary graph. Using traces, we then develop bounds for the number of spanning trees. Two approaches are used to establish such bounds: the first involves a logarithmic series expansion of the number of spanning trees in the complementary graph, while the second relies on certain \(l_p\) norm inequalities. Consequences to bipartite graphs are then examined.

The Padovan sequence \((P_n)_{n\geq 0}\) is defined by the third-order linear recurrence \(P_n=P_{n-2}+P_{n-3}\) for \(n\geq 3\), with initial terms \(P_0=1\) and \(P_1=P_2=0\). We derive closed forms for the weighted finite sums \(\sum\limits_{i=1}^{n} i^mP_i\) for all integers \(m\geq 0\) and \(n\geq 1\). The construction introduces an alternating integer sequence \((\mathcal{A}^{(m)})_{m\geq 0}\) and a family of coefficient polynomials \(\mathcal{C}^{(m)}(x)\) whose shifted evaluations determine the coefficients of \(P_n\), \(P_{n+1}\), and \(P_{n+2}\). The resulting formula unifies the cases \(m=0,1,2,\ldots\) and provides an effective recurrence, together with an exponential generating function, for the coefficients. The same polynomial family also gives explicit weighted-sum identities for arbitrary sequences satisfying the Padovan recurrence, including the Perrin and Van der Laan sequences.

The concept of the integrated adjacency matrix for mixed graphs was first introduced in [9], where its spectral properties were analyzed in relation to the structural characteristics of the mixed graph. Building upon this foundation, this paper introduces the integrated Laplacian matrix, the integrated signless Laplacian matrix, and the normalized integrated Laplacian matrix for mixed graphs. We further explore how the spectra of these matrices relate to the structural properties of the mixed graph.

The study of piecewise differential systems appears in various scientific topics and serves as an important tool for modeling many phenomena in contemporary research. Moreover, the existence and maximum number of limit cycles in such systems represent one of the most difficult problems in mathematics. This paper examines the existence and the maximum number of crossing limit cycles for the 3\(D\)-discontinuous piecewise differential system formed by a linear differential center and relay system separated by cylinder. Firstly we consider the right circular cylinder \(\mathcal{C}_1 =\{(x,y,z)\in \mathbb{R}^3:x^2+y^2=1\}\) as a switching manifold. Secondly we separate the entire space by the parabolic cylinder \(\mathcal{C}_2 =\{(x,y,z)\in \mathbb{R}^3:z=y^2\}\).

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.