This paper addresses immune sets in graphs, which are subsets of nodes that remain unaffected during the spread of influence, failure, or infection. The specific propagation model examined is the k -PULL infection rule, also referred to as bootstrap percolation . Studying immune sets offers important insights into the structural vulnerabilities and defensive capabilities of networks. In particular, we establish upper bounds for the size of minimal k -immune sets in graphs with a given maximum degree. Additionally, we focus on the k -immune number of a graph, defined as the minimum number of vertices in a k -immune set, and we derive bounds for this parameter. Lastly, we investigate the k -immune number of the Cartesian product of two graphs.

Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule R, and to the combinatorial transversal relation between the families of inclusion-minimal R-forcing and R-immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their R-immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part (k-PUSH, (kb,kw)-PUSH, α-PUSH, k-PULL, α-PULL, and k-wPULL), we prove the NP-Completeness of the decision problem associated to the corresponding R-immune number of the graph.

Abstract In this article, we present a detailed study of the reach distance‐layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance‐layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance‐layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description.

Concern about fault tolerance in the design of interconnection networks has aroused interest in finding large graphs such that the subgraphs obtained by deleting any set of up to s vertices have small diameter. Clearly, 1 ≤ s ≤ Δ − 1, where Δ is the maximum degree of the graph. Graphs of maximum degree Δ, diameter ≤ D and such that the graphs obtained by deletion of up to s vertices have diameter ≤ D′ are known as (Δ, D, D′, s)-graphs. This article considers the case s = 1 and D = D′. In other words, it deals with the search for large graphs whose diameter does not increase after deleting one vertex. The article also contains an updated table of the largest known (Δ, D, D, 1)-graphs, in which most of the entries correspond to the constructions put forward in this article. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 316–327 2011

Given a digraph G with minimum degree δ and an integer 0≤ ν ≤ δ, consider every pair of vertex subsets V1 and V2 such that both the minimum out-degree of the induced subdigraph G[V1] and the minimum in-degree of G[V2] are at least ν. The conditional diameter Dν of G is defined as the maximum of the distances d(V1, V2) between any two such vertex subsets. Clearly, D0 is the standard diameter and D0 ≥ D1 ≥ ··· ≥ Dδ holds. In this article, we guarantee appropriate lower bounds for the connectivities and superconnectivities of a digraph G when Dν ≤ h(ℓπ), h(ℓπ) being a function of the parameter ℓπ—which is related to the shortest paths in G. As a corollary of these results, we give some constraints of the kind Dν ≤ h(ℓπ), which assure that the digraph is maximally connected, maximally edge-connected, superconnected, or edge-superconnected, extending other previous results of the same kind. Similar statements can be obtained for a graph as a direct consequence of those for its associated symmetric digraph. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 80–87 2005

Abstract The conditional diameter Dν of a digraph G measures how far apart a pair of vertex sets V1 and V2 can be in such a way that the minimum out‐degree and the minimum in‐degree of the subdigraphs induced by V1 and V2, respectively, are at least ν. Thus, D0 is the standard diameter and D0 ≥ D1 ≥ ··· ≥ Dδ, where δ is the minimum degree. We prove that if Dν ≤ 2l − 3, where l is a parameter related to the shortest paths, then G is maximally connected, is superconnected, or has a good superconnectivity, depending only on whether ν is equal to ⌈δ/2⌉, ⌈(δ − 1)/2⌉, or ⌈(δ − 1)/3⌉, respectively. In the edge case, it is enough that Dν ≤ 2l − 2. The results for graphs are obtained as a corollary of those for digraphs, because, in the undirected case, l = ⌊(g − 1)/2⌋, g being the girth. © 2002 Wiley Periodicals, Inc.

This paper studies routing vulnerability in networks modeled by chordal ring graphs. In a chordal ring graph, the vertices are labeled in ℤ2n and each even vertex i is adjacent to the vertices i + a, i + b, i, + c, where a, b, and c are different odd integers. Our study is based on a geometrical representation that associates to the graph a tile which periodically tessellates the plane. Using this approach, we present some previous results on triple-loop graphs, including an algorithm to calculate the coordinates of a given vertex in the tile. Then, an optimal consistent fault-tolerant routing of shortest paths is defined for a chordal ring graph with odd diameter and maximum order. This is accomplished by associating to the chordal ring graph a triple-loop one. When some faulty elements are present in the network, we give a method to obtain central vertices, which are vertices that can be used to reroute any communication affected by the faulty elements. This implies that the diameter of the corresponding surviving route graph is optimum. © 2000 John Wiley & Sons, Inc.

It has been proved that if the diameter D of a digraph G satisfies D ≤ 2ℓ − 2, where ℓ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D ≤ 2ℓ − 1, then G is edge-superconnected. In this paper, we studied some similar conditions for a digraph to attain superconnectivity, which are given in terms of the conditional diameter or 𝒫-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property 𝒫, and, hence, it generalizes the standard concept of the diameter. As a corollary, some new sufficient conditions to attain superconnectivity or edge-superconnectivity are derived. It is also shown that these conditions can be slightly relaxed when the digraphs are bipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs. © 1999 John Wiley & Sons, Inc. Networks 34: 197–205, 1999

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D ≤ 21 − 1, then G has maximum connectivity (κ = δ), and if D ≤ 21, then it attains maximum edge-connectivity (λ = δ), where I is a parameter which can be thought of as a generalization of the girth of a graph. In this paper, we study some similar conditions for a digraph to attain high connectivities, which are given in terms of what we call the conditional diameter or P-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property P, and, hence, it generalizes the standard concept of diameter. As a corollary, some new sufficient conditions to attain maximum connectivity or edge-connectivity are derived. It is also shown that these conditions can be slightly relaxed when the digraphs are bipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs. In particular, since I ≥ 1, some known results of Plesnik and Znám are either reobtained or improved. For instance, it is shown that any graph whose line graph has diameter D = 2 (respectively, D ≤ 3) has maximum connectivity (respectively, edge-connectivity). Moreover, for graphs with even girth and minimum degree large enough, we obtain a lower bound on their connectivities. © 1996 John Wiley & Sons, Inc.