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.

Abstract An ({r, r + 1}; g)‐cage is a graph with degree set {r, r + 1}, girth g, and with the smallest possible order; every such graph is called a semiregular cage. In this article, semiregular cages are shown to be maximally edge‐connected and 2‐connected. As a consequence, ({3, 4}; g)‐cages are proved to be maximally connected. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract The conditional diameter D𝒫(G) of a connected graph G is a measure of the maximum distance between two subsets of vertices satisfying a given property 𝒫 of interest. For any given integer k ≥ 1, a connected graph G is said to be conditional diameter k‐saturated if D𝒫(G) ≥ k and there does not exist any other connected graph G′ with order ∣V(G′)∣ = ∣V(G)∣, size ∣E(G′)∣ > ∣E(G)∣, and conditional diameter D𝒫(G′) ≥ k. In this article, we obtain such conditional diameter saturated graphs for a number of properties 𝒫, generalizing the results obtained in (Ore, J Combin Theory 5(1968), 75–81) for the (standard) diameter D(G). © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract The product graph Gm*Gp of two given graphs Gm and Gp, defined by J.C. Bermond et al. [J Combin Theory, Series B 36 (1984) 32–48] in the context of the so‐called (Δ,D)‐problem, is one interesting model in the design of large reliable networks. This work deals with product graphs for which we provide bounds for the connectivity parameter κ. Moreover, we state sufficient conditions that guarantee these product graphs to be maximally connected or superconnected. As a consequence, we deduce that even small networks with low reliability may lead to larger networks with high levels of fault‐tolerance. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 114–120 2006

Abstract A (k;g)‐cage is a k‐regular graph with girth g and with the least possible number of vertices. In this article we prove that (k;g)‐cages are edge‐superconnected if g is even. Earlier, Marcote and Balbuena proved that (k;g)‐cages are edge‐superconnected if g is odd [Networks 43 (2004), 54–59]. Combining our results, we conclude that all (k;g)‐cages are edge‐superconnected. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 102–110 2006

Iterated line digraphs arise naturally in designing fault tolerant systems. Diameter vulnerability measures the increase in diameter of a digraph when some of its vertices or arcs fail. Thus, the study of diameter vulnerability is a suitable approach to the fault tolerance of a network. In this article we present some upper bounds for diameter vulnerability of iterated line digraphs LkG. Our bounds depend basically on the girth of the digraph G and on the number of iterations k. These bounds generalize some previous results on diameter vulnerability of line digraphs. Also, we apply our results to several important families of line digraphs such as Kautz digraphs and deBruijn generalized cycles, which contain deBruijn digraphs, the Reddy-Pradhan-Kuhl digraphs, and the butterflies. Our bounds allow us to obtain improvements in known results on diameter vulnerability for all these families. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 49-54 2005

Abstract A permutation graph (or generalized prism) Gπ of a graph G is obtained by taking two disjoint copies of G and adding an arbitrary matching between the two copies. Permutation graphs can be seen as suitable models for building larger interconnection networks from smaller ones without increasing significantly their maximum transmission delays, in such a way that these larger networks are highly fault‐tolerant. For permutations graphs, in this article we provide conditions that guarantee optimal values for two parameters of connectivity, λ′ and κ′. For a connected graph G the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of a restricted edge‐cut; that is, the minimum cardinality of a set S of edges such that G − S is not connected and S does not contain the set of incident edges of any vertex of the graph. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) − 2 : uv ∈ E(G)}, and d(u) denotes the degree of vertex u. Among other things, we prove that permutation graphs satisfy: min{λ′(G) + δ(G), 2λ′(G), ξ(Gπ)} ≤ λ′(Gπ) ≤ ξ(Gπ) if |V(G) | ≥ ξ(G) + 2. Furthermore, min{ 2λ′(G), ξ(Gπ)} ≤ λ′(Gπ) ≤ ξ(Gπ) if G is triangle‐free. We also study the vertex case considering the restricted connectivity κ′(G) and relating it to the superconnectivity κ1(G); the latter is defined as the minimum cardinality of a set of vertices, if any, whose deletion disconnects G in such a way that every remaining component has at least two vertices. For instance, we prove that 2κ(G) ≤ κ1(G) ≤ κ′(Gπ) ≤ ξ(Gπ) if G is triangle‐free and the permutation graph has no cycles of length five. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 113–118 2005

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 A graph with minimum degree δ is said to be edge‐superconnected if each minimum edge‐cut consists of all the edges incident with some vertex (so λ = δ). A smallest δ‐regular graph G with girth g is said to be a (δ, g)‐cage. We show that every (δ, g)‐cage with odd girth is edge‐superconnected. This result strengthens one obtained by Wang et al. (λ = δ for every such cage) and supports the conjecture of Fu et al. that all (δ, g)‐cages are δ‐connected. © 2003 Wiley Periodicals, Inc.

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.