Let \(G\) be a simple connected graph and \(A(G)\) and \(D(G)\) represent the adjacency matrix and the diagonal matrix of degrees of graph G, respectively. The normalized Laplacian of \(G\) is defined by \(\mathcal{L}(G)=I_n-D(G)^{-1/2}A(G)D(G)^{-1/2},\) where \(I_n\) is the identity matrix of order \(n\). The normalized Laplacian plays an important role in spectral graph theory. In this paper, we characterize the connected graphs that minimize the spectral radius of the normalized Laplacian in the class of graphs with exactly one vertex of degree greater than two and in the class of graphs with exactly two vertices of degree greater than two. In each class, we determine the extremal graphs and the exact minimum normalized Laplacian spectral radius.

The inequality chain \(ir(G)\le \gamma(G)\le i(G)\le \alpha(G) \le \Gamma(G) \le I\!R(G)\) is known as the domination chain, where \(ir(G), \gamma(G), i(G), \alpha(G), \Gamma(G)\) and \(I\!R(G)\) are the lower irredundance number, the domination number, the independence domination number, the independence number, the upper domination number and the upper irredundance number of \(G\), respectively. The Ramsey-type problem seeks to characterize the family \({\mathcal H}\) of graphs such that every \({\mathcal H}\)-free graph \(G\) has a bounded parameter \(\mu\). The classical Ramsey’s theorem states that every \(\{K_n, E_n\}\)-free graph has a bounded number of vertices. Furuya (Discrete Math.Theor 2018) characterized \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has a bounded domination number. The characterization of the graph family \({\mathcal H}\) for which every connected \({\mathcal H}\)-free graph \(G\) has a bounded independence number was due to Choi, Furuya, Kim, Park (Discrete math. 2020) and Chiba, Furuya (Electron. J. Combin., 2022). In this paper, we further characterize \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu\) belonging to the set \(\{ir(G), i(G), \Gamma(G), \text{IR}(G)\}\). This completes the characterization of \({\mathcal H}\) for which every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu(G)\) along the domination chain. Additionally, we characterize \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu\) related to the domination number. Specifically, we consider the following parameters of \(G\): open irredundance number \(O\!I\!R(G)\), independence saturation number \(I\!S(G)\) and irredundance saturation number \(I\!R\!S(G)\).

Let \(D\) be a finite simple digraph with vertex set \(V(D)\). For \(v\in V(D)\), the set \(N^-[v]\) consists of \(v\) and all vertices of \(D\) from which arcs go into \(v\). Let \(k\ge 1\) be an integer. A signed double Roman \(k\)-dominating function (SDR\(k\)DF) on a digraph \(D\) is a function \(f:V(D)\rightarrow\{-1,1,2,3\}\) satisfying the following conditions: (i) \(\sum\limits_{x\in N^-[v]}f(x)\ge k\) for each \(v\in V(D)\); (ii) every vertex \(u\) with \(f(u)=-1\) has an in-neighbor \(z\) with \(f(z)=3\) or two in-neighbors \(x\) and \(y\) with \(f(x)=f(y)=2\); (iii) every vertex \(u\) with \(f(u)=1\) has an in-neighbor \(z\) with \(f(z)\ge 2\). The weight of an SDR\(k\)DF \(f\) is \(\omega(f)=\sum\limits_{v\in V(D)}f(v)\). The signed double Roman \(k\)-domination number \(\gamma_{sdR}^k(D)\) is the minimum weight of an SDR\(k\)DF on \(D\). In this paper, we study the signed double Roman \(k\)-domination number of digraphs and present various bounds on \(\gamma_{sdR}^k(D)\). In addition, we determine this parameter for several classes of digraphs. Some of our results extend well-known properties of the signed double Roman \(k\)-domination number \(\gamma_{sdR} ^k(G)\) of graphs \(G\).

We give combinatorial interpretations of some Rogers\(-\)Ramanujan type identities, also known as sum-product identities in terms of \((n+t)-\)color partitions and split \((n+t)-\)color partitions. The identities discussed in this study contains negative exponent of \(q\). These interesting results reveal rich structure and great potential for further research because they reveal intricate mathematical structures, and link various other fields.

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.