Abstract For a strongly connected digraph D the restricted arc‐connectivity λ′(D) is defined as the minimum cardinality of an arc‐cut over all arc‐cuts S satisfying that D ‐ S has a non‐trivial strong component D1 such that D ‐ V (D1) contains an arc. In this paper we prove that every digraph on at least 4 vertices and of minimum degree at least 2 is λ′ ‐connected and λ′(D) ≤ξ′(D), where ξ′(D) is the minimum arc‐degree of D. Also in this paper we introduce the concept of super‐ λ′ digraphs and provide a sufficient condition for an s ‐geodetic digraph to be super‐ λ′. Further, we show that the h ‐iterated line digraph Lh(D) of an s ‐geodetic digraph is super‐ λ′ for a particular h. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

In this article, some structures in the projective plane of order are found which allow us to construct small -regular balanced bipartite graphs of girth 6 for all . When , the order of these -regular graphs is ; and when , the order of these -regular graphs is . Moreover, the incidence matrix of a -regular balanced bipartite graph of girth 6 having vertices, where is an integer and is a prime power with , is provided. These graphs improve upon the best known upper bounds for the number of vertices in regular graphs of girth 6. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 121–127 2011

Abstract A graph is said to be edge‐superconnected if each minimum edge‐cut consists of all the edges incident with some vertex of minimum degree. A graph G is said to be a $\{d,d+1\}$ ‐semiregular graph if all its vertices have degree either d or $d+1$ . A smallest $\{d,d+1\}$ ‐semiregular graph G with girth g is said to be a $(\{d,d+1\};g)$ ‐cage. We show that every $(\{d,d+1\};g)$ ‐cage with odd girth g is edge‐superconnected. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

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

Let q be a prime power and $r=0,1\ldots, q-3$. Using the Latin squares obtained by multiplying each entry of the addition table of the Galois field of order q by an element distinct from zero, we obtain the incidence matrices of projective planes and the incidence matrices of $(q-r)$-regular bipartite graphs of girth 6 and $q^2-rq-1$ vertices in each partite set. Moreover, in this work two Latin squares of order $q-1$ with entries belonging to $\{0,1,\ldots, q\}$, not necessarily the same, are defined to be quasi row-disjoint if and only if the Cartesian product of any two rows contains at most one pair $(x,x)$ with $x\ne 0$. Using these quasi row-disjoint Latin squares we find $(q-1)$-regular bipartite graphs of girth 6 with $q^2-q-2$ vertices in each partite set. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth 6.

We show that any n‐vertex extremal graph G without cycles of length at most k has girth exactly $k+1$ if $k\ge 6$ and $n>(2(k-2)^{k-2}+k-5)/(k-3)$. This result provides an improvement of the asymptotical known result by Lazebnik and Wang [J. Graph Theory, 26 (1997), pp. 147–153] who proved that the girth is exactly $k+1$ if $k\ge 12$ and $n\ge 2^{a^2+a+1}k^a$, where $a=k-3-\lfloor(k-2)/4\rfloor$. Moreover, we prove that the girth of G is at most $k+2$ if $n>(2(t-2)^{k-2}+t-5)/(t-3)$, where $t=\lceil (k+1)/2\rceil\ge 4$. In general, for $k\ge 5$ we show that the girth of G is at most $2k-4$ if $n\ge 2k-2$.

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.

In this paper, a method for obtaining large diameter 6 graphs by replacing some vertices of a Moore bipartite diameter 6 graph with complete Kh graphs is proposed. These complete graphs are joined to each other and to the remaining nonmodified graphs by means of new edges and by using a special diameter 2 graph. The degree of the graph so constructed coincides with the original one. © 1999 John Wiley & Sons, Inc. Networks 34: 154–161, 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.