Search

Let G be a graph and F be a connected subgraph of G except for K 1. Let F = { F 1 , F 2 , ... , F k } be a set of subgraphs of G such that each member of F is isomorphic to F. The F -(disjoint)-structure edge-connectivity is the minimum cardinality of F such that E (F) 's removal will disconnect G. If every member of F is isomorphic to a connected subgraph of F , then F -(disjoint)-substructure edge-connectivity is defined similarly. In this paper, we determine the star-(disjoint)-substructure edge-connectivity and star-structure edge-connectivity of an n -regular graph G , and give an upper bound on the star-disjoint-structure edge-connectivity of an n -regular graph G. We derive the F -(disjoint)-substructure edge-connectivity of hypercube-like graphs H L n and Cayley graphs generated by transposition trees Γ n (except for star graphs S n) for F being C 4 and P 4 , and show a lower bound on the F -(disjoint)-structure edge-connectivity of H L n and Γ n (except for S n) for F being C 4 and P 4. As applications, we determine the F -(disjoint)-structure edge-connectivity of crossed cubes C Q n and bubble-sort graphs B n for F being C 4 and P 4 , respectively. Furthermore, we obtain the F -(disjoint)-(sub)structure edge-connectivity of S n for F being C 6 and P 6. [ABSTRACT FROM AUTHOR]

The conditional edge-connectivity is an important parameter to evaluate the reliability and fault tolerance of multi-processor systems. The |$n$| -dimensional bijective connection networks |$B_{n}$| contain hypercubes, crossed cubes, Möbius cubes and twisted cubes, etc. The conditional edge-connectivity of a connected graph |$G$| is the minimum cardinality of edge sets, whose deletion disconnects |$G$| and results in each remaining component satisfying property |$\mathscr{P}$|⁠. And let |$F$| be the edge set as desired. For a positive integer |$a$|⁠ , if |$\mathscr{P}$| denotes the property that the average degree of each component of |$G-F$| is no less than |$a$|⁠ , then the conditional edge-connectivity can be called the |$a$| -average degree edge-connectivity |$\overline{\lambda }_{a}(G)$|⁠. In this paper, we determine that the exact value of the |$a$| -average degree edge-connectivity of an |$n$| -dimensional bijective connection network |$\overline{\lambda }_{a}(B_{n})$| is |$(n-a)2^a$| for each |$0\leq a \leq n-1 $| and |$n\geq 1$|⁠. 1 [ABSTRACT FROM AUTHOR]

The exchanged 3-ary n-cube E 3 C (r , s , t) , proposed by Lv et al. in 2021, is obtained by removing edges from a 3-ary n-cube Q n 3 , where r + s + t + 1 = n. The topological interconnection network of a multiprocessor system can be modeled as a connected graph. Analyzing the fault tolerance of its topological structure is critical in the course of design and maintenance of it. Given a connected graph G, let F be an edge subset of G. F is called an h-edge-cut of G, if G−F is disconnected and each remaining component has the minimum degree of at least h. The h-edge-connectivity λ h (G) is the minimum cardinality of all h-edge-cuts of G. For 1 ≤ r ≤ s ≤ t and 0 ≤ h ≤ r , in this paper, we determine the 2 h -edge-connectivity of exchanged 3-ary n-cubes, E 3 C (r , s , t) , and prove the exact values λ 2 h (E 3 C (r , s , t)) = 2 ⋅ 3 h (r + 1 − h). [ABSTRACT FROM AUTHOR]

In this paper, we present the upper and lower bounds on Sombor index S O (G) among all connected graphs (respectively, connected bipartite graphs). We give some sharp lower and upper bounds on S O (G) among connected graphs in terms of some parameters, including chromatic, girth and matching number. Meanwhile, we characterize the extremal graphs attaining those bounds. In addition, we give upper bounds on S O (G) among connected bipartite graphs with given matching number and/or connectivity and determine the corresponding extremal connected bipartite graphs. [ABSTRACT FROM AUTHOR]

A connected hypergraph H is maximally edge (resp. vertex)-connected if the edge (resp. vertex)-connectivity attains its minimum degree. A hypergraph H is super edge (resp. vertex)-connected if every minimum edge (resp. vertex) cut isolates a vertex of H. In this paper, sufficient conditions for the Cartesian product of hypergraphs to be maximally edge-connected, super edge-connected, maximally vertex-connected, and super vertex-connected are presented. As a corollary, we deduce that the n-dimensional r-uniform cube-hypergraph Q(n, r) is both super edge-connected and super vertex-connected. [ABSTRACT FROM AUTHOR]

The eccentric distance sum and degree distance have been well-studied in the past several years. More recently, many authors have considered the relationships between several distance-based graph invariants. Hua et al. (2018) investigated the relationship between the eccentric distance sum and the degree distance. In this paper, we present upper and lower bounds on ξ d (G) − D ′ (G) among all connected graphs. The sharp lower and upper bounds on ξ d (G) − D ′ (G) of general graphs with given connectivity (resp. edge number, number of cut edges, and matching number) are determined. In addition, we characterize the extremal graphs attaining those bounds. [ABSTRACT FROM AUTHOR]

Let G be a connected graph, F be a subset of V (G) , S be a subset of E (G). The cyclic vertex connectivity of G, denoted by κ c (G) , is the minimum cardinality of F such that G−F is disconnected and at least two of its components contain cycles. The cyclic edge connectivity of G, denoted by λ c (G) , is the minimum cardinality of S such that G−S is disconnected and at least two of its components contain cycles. Let D k , n denote the data center network. In this paper, we obtain the following results: κ c (D k , 2) = 6 k − 6 for k ≥ 2 ; κ c (D k , n) = n + 3 k − 3 for k ≥ 2 , n ≥ 3 ; λ c (D k , 2) = 6 k − 6 for k ≥ 2 ; λ c (D 2 , n) = 2 n for n ≥ 3 ; λ c (D k , n) = 3 n + 3 k − 9 for k ≥ 3 , n ≥ 3. [ABSTRACT FROM AUTHOR]

Let H be a connected subgraph of a graph G. The H-structure connectivity κ (G ; H) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to H. Similarly, the H-substructure connectivity κ s (G ; H) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of H. Structure connectivity and substructure connectivity generalise the classic connectivity. Let P n and B P n be the n-dimensional pancake graph and n-dimensional burnt pancake graph, respectively. In this paper we show κ (P n ; K 1 , t 1 ) = κ s (P n ; K 1 , t 1 ) = n − 1 (1 ≤ t 1 ≤ n − 2) , and κ (B P n ; K 1 , t 2 ) = κ s (B P n ; K 1 , t 2 ) = n (1 ≤ t 2 ≤ n − 1). [ABSTRACT FROM AUTHOR]

Motivated by effects caused by structure link faults in networks, we study the following graph theoretical problem. Let |$T$| be a connected subgraph of a graph |$G$| except for |$K_{1}$|⁠. The |$T$| -structure edge-connectivity |$\lambda (G;T)$| (resp. |$T$| -substructure edge-connectivity |$\lambda ^s(G;T)$|⁠) of |$G$| is the minimum cardinality of a set of edge-disjoint subgraphs |$\mathcal{F}=\{T_{1},T_{2},\ldots ,T_{m}\}$| (resp. |$\mathcal{F}=\{T_{1}^{^{\prime}},T_{2}^{^{\prime}},\ldots ,T_{m}^{^{\prime}}\}$|⁠) such that |$T_{i}$| is isomorphic to |$T$| (resp. |$T_{i}^{^{\prime}}$| is a connected subgraph of |$T$|⁠) for every |$1 \le i \le m$|⁠ , and |$E(\mathcal{F})$| 's removal leaves the remaining graph disconnected. In this paper, we determine both |$\lambda (G;T)$| and |$\lambda ^{s}(G;T)$| for |$(1)$| the hypercube |$Q_{n}$| and |$T\in \{K_{1,1},K_{1,2},K_{1,3},P_{4},Q_{1},Q_{2},Q_{3}\}$|⁠ ; |$(2)$| the |$k$| -ary |$n$| -cube |$Q^{k}_{n}$|   |$(k\ge 3)$| and |$T\in \{K_{1,1},K_{1,2},K_{1,3},Q^{3}_{1},Q^{4}_{1}\}$|⁠ ; |$(3)$| the balanced hypercube |$BH_{n}$| and |$T\in \{K_{1,1},K_{1,2},BH_{1}\}$|⁠. We also extend some known results. [ABSTRACT FROM AUTHOR]

A cyclic vertex-cut of a graph G is a vertex set S such that G−S is disconnected and at least two of its components contain cycles. If G has a cyclic vertex-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic vertex-connectivity κ c (G) is defined as the cardinality of a minimum cyclic vertex-cut. Let G i be a k i -regular (k i ≥ 2) and maximally connected graph with girth g (G i) ≥ 5 for i=1,2. In this paper, we mainly prove that κ c (K m ◻ G 2) = 3 k 2 + m − 3 for m ≥ 3 and κ c (G 1 ◻ G 2) = 4 k 1 + 4 k 2 − 8. In addition, we state sufficient conditions to guarantee κ c (K 2 ◻ G 2) = 2 κ (G 2). [ABSTRACT FROM AUTHOR]

Let H be a connected hypergraph. H is said to be linear if any two edges of H share at most one vertex. If all edges of H have the same cardinality, then H is uniform. We call H maximally edge-connected if the edge-connectivity of H attains its minimum degree. In this paper, we present some sufficient conditions for linear uniform hypergraphs to be maximally edge-connected that generalize the corresponding well-known results for graphs. [ABSTRACT FROM AUTHOR]

In Mader (2010), Mader conjectured that for every positive integer k and every finite tree T with order m , every k -connected, finite graph G with δ ( G ) ≥ ⌊ 3 2 k ⌋ + m − 1 contains a subtree T ′ isomorphic to T such that G − V ( T ′ ) is k -connected. In the same paper, Mader proved that the conjecture is true when T is a path. Diwan and Tholiya (2009) verified the conjecture when k = 1 . In this paper, we will prove that Mader’s conjecture is true when T is a star or double-star and k = 2 . [ABSTRACT FROM AUTHOR]

A bipartite digraph is said to be a half vertex transitive digraph if its automorphism acts transitively on the sets of its bipartition, respectively. In this paper, bipartite double coset digraphs of groups are defined and it is shown that any half vertex transitive digraph is isomorphic to some half double coset digraph, and we show that the connectivity of any strongly connected half transitive digraph is its minimum degree. [ABSTRACT FROM AUTHOR]

• Owing to the great difference of different networks connection ways, most of the research on their performances is carried out separately by using special methods. We propose two kinds of recursive networks based on connected graphs such that they contain diverse networks, aimed to study their performances by a more unified method. • We prove that the two kinds of recursive networks have common superior performances: smaller diameters and higher reliabilities—maximal connectivity and diagnosability. • We show that our results can be extended to a number of networks. Two crucial parameters to be considered when evaluating a network's reliability are its connectivity and diagnosability. The connectivity of a graph is defined as the smallest number of vertices that, if removed, would leave a disconnected or single-vertex graph. The diagnosability is the maximum number of faulty vertices that the system can correctly identify. In this paper, aim to obtain the reliability of various graphs (e.g. interconnection networks and data center networks), we propose two kinds of graphs (resp. networks)—matching recursive graphs (MRGs) and recursive networks based on connected graphs (RNCGs). We prove that these two kinds of graphs have smaller diameters. Furthermore, we study their reliabilities, including connectivities and diagnosabilities. Moreover, we also extend our results to many graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with order n and D ( G ) be the distance matrix of G . Suppose that λ 1 ( D ( G ) ) ≥ ⋯ ≥ λ n ( D ( G ) ) are the distance spectra of G . In this paper, we characterize the graphs with λ n ( D ( G ) ) ∈ [ − 1 + 17 2 , α − 1 ) ∪ [ α − 1 , − 1 − 2 ) , where α is the smallest root of x 3 − x 2 − 3 x + 1 = 0 , and − 1 + 17 2 < α − 1 < − 1 − 2 . Furthermore, we show that the graphs with λ n ≥ − 1 + 17 2 are determined by their D -spectrum. [ABSTRACT FROM AUTHOR]

A vertex-cut $$S$$ of a connected graph $$G$$ is called a restricted vertex-cut if no vertex $$u$$ of the graph $$G$$ satisfies $$N_G(u)\subseteq S$$ . The restricted connectivity $$\kappa '(G)$$ of the graph $$G$$ is the cardinality of a minimum restricted vertex-cut of $$G$$ ; this is a more refined index than the connectivity parameter $$\kappa (G)$$ . In this paper, we prove that $$\kappa '(K_m\times G_2)=2k_2+m-2$$ , where $$G_2$$ is a $$k_2\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_2)\ge 4$$ ; and $$\kappa '(G_1\times G_2)=2k_1+2k_2-2$$ , where $$G_i$$ is a $$k_i\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_i)\ge 4$$ for $$1\le i\le 2$$ . Furthermore, we determine the restricted connectivity of a class of minimal Abelian Cayley graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph of order , minimum degree , and edge-connectivity . The graph is maximally edge-connected if and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. A list is graphic if there is a graph with vertices such that for . A graphic list is super edge-connected if is the degree list of some super edge-connected graph. We prove that a graphic list with least element 1 is super edge-connected if and only if (1) or (2) and . We also give a necessary and sufficient condition for a graphic list with least entry 2 to be super edge-connected, and we show that every graphic list with least element at least 3 is super edge-connected. [Copyright &y& Elsevier]

LetG=(V, E) be a multigraph. The multigraphGis called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivity λ′(G) ofGis the minimum number of edges whose removal disconnectsGinto non-trivial components. If λ′(G) achieves the upper bound of restricted edge-connectivity, thenGis said to be λ′-optimal. This work characterizes maximally edge-connected vertex-transitive multigraphs, super edge-connected vertex-transitive multigraphs, and λ′-optimal vertex-transitive multigraphs. [ABSTRACT FROM PUBLISHER]

Abstract: A vertex subset is an -cut of a connected graph if is disconnected and every vertex in has at least fault-free neighbors in . The cardinality of the minimum -cut of is the -connectivity of , denoted by . This parameter measures a kind of conditional fault tolerance of networks. In this work, we characterize the smallest components after deleting a minimum -cut of hypercubes. Our work strengthens the results of [A.H. Esfahanian, Generalized measure of fault tolerance with application to -cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591] and [S. Latifi, M. Hegde, M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222] and also corrects bugs in them. [Copyright &y& Elsevier]

Abstract: Let be a graph of order , minimum degree and connectivity . We call the graph maximally connected when . The graph is said to be superconnected if every minimum vertex cut isolates a vertex. For an integer , we define a -diamond as the graph with vertices, where two adjacent vertices have exactly common neighbors, and the graph contains no further edges. Usually, the 1-diamond is triangle and the 2-diamond is diamond. We call a graph -diamond-free if it contains no -diamond as a (not necessarily induced) subgraph. A graph is vertex transitive if its automorphism group acts transitively on its vertex set. In this paper, we give some sufficient conditions for vertex transitive graphs to be maximally connected. In addition, superconnected -diamond-free () vertex transitive graphs are characterized. [Copyright &y& Elsevier]

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n−2δ)/(n−δ) (n−δ−1), then G is super edge-connected. We also give an analogous result for triangle-free graphs. [ABSTRACT FROM AUTHOR]

Let X = ( V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n = | V( X)| ≥ 4 and $${X \ncong K_{1,n-1}}$$ is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized. [ABSTRACT FROM AUTHOR]

Abstract: A connected graph is super edge connected (super- for short) if every minimum edge cut of is the set of edges incident with some vertex. We define a super- graph to be -super- if is still super- for any edge subset with . The maximum integer of such , written as , is said to be the edge fault tolerance of with respect to the super- property. In this paper, we study the bounds for , showing that . More refined bounds are obtained for regular graphs and Cartesian product graphs. Exact values of are obtained for edge transitive graphs. [Copyright &y& Elsevier]

Abstract: It is well known that the edge-connectivity of a simple, connected, vertex transitive graph attains its regular degree. It is then natural to consider the relationship between the graph’s edge connectivity and the number of orbits of its automorphism group. In , Liu and Meng (2008) studied the edge connectivity of regular double-orbits graphs. Later, Lin et al. (in press) characterized the λ′-optimal 3-regular double-orbit graph and given a sufficient condition for the k-regular double-orbit graphs to be optimal. In this note, we characterize the super restricted edge connected k-regular double-orbit graphs with grith at least 6. [Copyright &y& Elsevier]

graph is said to be superconnected if every minimum vertex cut isolates a vertex. A graph is said to be hyperconnected if each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this paper, we characterize superconnected or hyperconnected vertex transitive graphs with degree 4 and 5. As a corollary, superconnected or hyperconnected planar transitive graphs are characterized. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph. Then is called super restricted edge-connected, in short, sup-, if every minimum edge set of such that is disconnected and every component of has at least two vertices, the set of edges being adjacent to a certain edge with minimum edge degree in . In this paper, by studying the -superatoms of , we characterize super restricted edge-connected edge-transitive graphs. As a corollary, we present a sufficient and necessary condition for connected vertex-transitive line graphs to be super vertex-connected. [Copyright &y& Elsevier]

Abstract: A strongly connected digraph is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree. [Copyright &y& Elsevier]

Abstract: Given a graph and a non-negative integer g, the g-extraconnectivity of (written ) is the minimum cardinality of a set of vertices of , if it exists, whose deletion disconnects , and where every remaining component has more than vertices. The usual connectivity and superconnectivity of correspond to and , respectively. In this work, we determine for , , where denotes the -dimensional hypercube. [Copyright &y& Elsevier]

Abstract: A graph is max- if . A graph is super- if is max- and every minimum edge-cut set of isolates one vertex. In this paper, we proved that for all but a few exceptions, the mixed Cayley graph which is defined as a new kind of semi-regular graph is max- and super-. [Copyright &y& Elsevier]

The L -ary n -dimensional hamming graph K L n is one of the most attractive interconnection networks for parallel processing and computing systems. Analysis of the link fault tolerance of topology structure can provide the theoretical basis for the design and optimization of the interconnection networks. The k -component edge-connectivity c λ k (G) of an interconnection network G , is the minimum number of set of faulty links, such that these malfunctions disconnect the network G with at least k connected subnetworks. It gives a more precise quantitative analysis of indicators of the robustness of a parallel distributed system in the event of faulty links. Let t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. In this paper, we prove that the (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs is c λ k + 1 (K L n) = (L − 1) n k − e x k (K L n) 2 for k ≤ L t , n ≥ 7 , where e x k (K L n) represents the maximum degree sum of the subgraph induced by all k processors of K L n. As the exact values of (k + 1) -component edge-connectivity of K L n oscillate greatly, an efficient O (log ⁡ N) algorithm is designed to determine the exact values of c λ k + 1 (K L n) for each k ≤ L t and N = L n. Our result improves those of Xu et al. [33] and Liu et al. [27]. • The (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs K L n is explored. • Determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and n ≥ 7 , where t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. • An efficient O (l o g N) algorithm is designed to determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and N = L n. [ABSTRACT FROM AUTHOR]

A signed graph Σ is a graph whose edges yield the signs ±1. Let K n be the complete graph with n vertices and Σ = (K n , F −) be a signed complete graph, where F is a subgraph induced by the negative edges of Σ. The least Laplacian eigenvalue of Σ is the least eigenvalue of its Laplacian matrix. A unicyclic graph is a connected graph containing exactly one cycle. In this paper, we focus on the least Laplacian eigenvalue of Σ = (K n , F −) , where F is a unicyclic graph. [ABSTRACT FROM AUTHOR]

Given a connected graph G and a connected subgraph H of G. The H -structure connectivity κ (G; H) of G is the minimal cardinality of a set of subgraphs F = { J 1 , J 2 , ... , J m } in G , where J i ≅ H (1 ≤ i ≤ m), and the deletion of F disconnects G. Similarly, the H -substructure connectivity κs (G; H) of G is the minimal cardinality of a set of subgraphs F = { J 1 , ... , J m } in G , where J i (1 ≤ i ≤ m) is isomorphic to a connected subgraph of H , and the deletion of F disconnects G. Structure connectivity and substructure connectivity generalize the classical vertex-connectivity. In this thesis, we establish κ (A n,k ; H) and κs (A n,k ; H) of the (n, k)-arrangement graph A n,k , where H ∈ { K 1 , m 1 , P m 2 } (m 1 ≥ 1 , m 2 ≥ 4). [ABSTRACT FROM AUTHOR]

• For more than 37.5 percent of g ≤ ⌊ 3 n 2 ⌋ , the g -extra edge-connectivity of ternary n -cube, λ g (Q n 3) , exists a concentration behavior. • Determine the exact value of λ g (Q n 3) for each 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ ≤ g ≤ 3 ⌈ n 2 ⌉ + r , r = 0 , 1 , ... , ⌊ n 2 ⌋ − 1. • For the above each integer g , a necessary and sufficient condition of λ g -optimality is found. • Obtain maximum number of edge-disjoint paths connecting any two disjoint connected subgraphs with the above g vertices in Q n 3. One of most central issues in various interconnection networks of parallel and distributed systems is to find edge-disjoint paths concerned with an information transmission through links. It is universally acknowledged that an interconnection network can be modeled as an undirected simple graph G = (V , E) with processors and physical links between the processors represented as vertices and edges of the G , respectively. The studies on the edge-disjoint paths are closely related to the edge-connectivity. By the well-known Menger theorem, the maximum number of edge disjoint paths connecting any two disjoint connected subgraphs with g vertices in G can also define by the minimum modified edge-cut, called the g -extra edge-connectivity of G λ g (G). It is the cardinality of the minimum set of edges in G , if such a set exists, whose deletion disconnects G and leaves every remaining component with at least g vertices. The k -ary n -cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. This article intends to show that for 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ ≤ g ≤ 3 ⌈ n 2 ⌉ + r , the g -extra edge-connectivity of ternary n -cube (also called 3-ary n -cube) (n ≥ 3) exists a concentration behavior, and prove that these corresponding g -extra edge-connectivities of ternary n -cubes are the constants 2 (⌊ n 2 ⌋ − r) 3 ⌈ n 2 ⌉ + r , where r = 0 , 1 , 2 , ⋯ , ⌊ n 2 ⌋ − 1 , and e = 1 if n is odd and e = 0 if n is even. The above upper and lower bounds of g are sharp. As the integer g varies within the range between 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ and 3 ⌈ n 2 ⌉ + r , a necessary and sufficient condition of λ g -optimality is found. Our results improve the several previous results. [ABSTRACT FROM AUTHOR]

Parallel and distributed systems play a significant role in high-performance computing, prompting us to investigate qualitative and quantitative metrics to indicate the fault tolerance and vulnerability of systems. Consider the setup where there are large-scale link malfunctions that disconnect the network and result in various components, each with multiple processors. In this paper, we propose and study the h -extra r -component edge-connectivity of a connected graph G , which is denoted by c λ r h (G) and has not been addressed before. Let h and r be two positive integers with r ≥ 2. An edge subset F ⊆ E (G) is said to be an h -extra r -component edge-cut of G , if any, G − F has at least r components and every component of G − F has at least h vertices. The cardinality of the minimum h -extra r -component edge-cut of G is the h -extra r -component edge-connectivity of G. Let h be a positive integer with the decomposition h = ∑ i = 0 t 2 k i , where k i > k i + 1 , 0 ≤ i ≤ t − 1. In this paper, we derive a lower bound for the exact value of h -extra 3-component edge-connectivity of BC networks B n and demonstrate that it is tight for one member of B n , hypercube Q n , in the interval 1 ≤ h ≤ 2 ⌊ n 2 ⌋ − 1 − 1 , n ≥ 4. This lower bound is also tight for the exact value of 2 c -extra 3-component edge-connectivity of B n with 0 ≤ c ≤ n − 2 , n ≥ 4. Specifically, c λ 3 h (Q n) = 2 n h − ∑ i = 0 t k i 2 k i + 1 − ∑ i = 0 t i 2 k i + 2 − h for 1 ≤ h ≤ 2 ⌊ n 2 ⌋ − 1 − 1 , n ≥ 4 and c λ 3 2 c (B n) = (2 n − 2 c − 1) 2 c for 0 ≤ c ≤ n − 2 , n ≥ 4. Exact value of h -extra 3-component edge-connectivity of n -dimensional folded hypercube F Q n , c λ 3 h (F Q n) is 2 (n + 1) h − ∑ i = 0 t k i 2 k i + 1 − ∑ i = 0 t i 2 k i + 2 − h for 1 ≤ h ≤ 2 ⌈ n 2 ⌉ − 1 − 1 , n ≥ 4 , and that of 2 c -extra 3-component edge-connectivity of F Q n , c λ 3 2 c (F Q n) , is (2 n − 2 c + 1) 2 c for 0 ≤ c ≤ n − 2 , n ≥ 4. • For a connected graph G , this paper proposes a novel conditional edge-connectivity called h -extra r -component edge-connectivity c λ r h (G). • The folded hypercube F Q n and BC networks B n are two of the most intriguing interconnection networks. • Provide a lower bound for c λ 3 h (B n) and show that it is tight for one member of B n , hypercube Q n in the interval 1 ≤ h ≤ 2 ⌊ n 2 ⌋ − 1 − 1 , n ≥ 4. • This lower bound is also tight for the exact value of c λ 3 2 c (B n) with 0 ≤ c ≤ n − 2 , n ≥ 4. • Determining the exact values of c λ 3 h (F Q n) for 1 ≤ h ≤ 2 ⌈ n 2 ⌉ − 1 − 1 , n ≥ 4 and h = 2 c , 0 ≤ c ≤ n − 2 , n ≥ 4 , respectively. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A (G) and the degree diagonal matrix D (G). For any real α ∈ [ 0 , 1 ] , Nikiforov (2017) [10] defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). Denote its eigenvalues by λ 1 (A α (G)) ≥ λ 2 (A α (G)) ≥ ⋯ ≥ λ n (A α (G)). In this paper, we give a lower bound of λ 2 (A α (G)) for 0 ≤ α < 1. As an application, we show that the star is the unique graph which minimizes the second largest A α -eigenvalues among connected graphs for 1 / 2 ≤ α < 1. In particular, the graphs with λ k (A α (G)) = (n − 2) α for k ≥ 2 are determined. Furthermore, we determine the connected graphs with λ 2 (A α (G)) ≤ α + 1 are firefly graphs. Moreover, the firefly graphs are shown to be determined by their A α -spectrum for 1 / 2 ≤ α < 1. [ABSTRACT FROM AUTHOR]

Abstract The interconnection networks are generally modeled by a connected graph G , and the connectivity of G is an important parameter for reliability and fault tolerance of the network. A connected graph G = (V , E) is maximally edge-connected (or maximally- λ for short) if its edge-connectivity attains its minimum degree. We define a maximally- λ graph G to be m -maximally- λ if G − S is still maximally- λ for any edge subset S ⊆ E (G) with | S | ≤ m. The maximum integer of such m , denoted by m λ (G) , is said to be the edge fault tolerance of G with respect to the maximally- λ property. In this paper, we discuss the edge fault tolerance for maximally- λ property of two families of interconnection networks, from which we determine the exact values of m λ (G) for some well-known networks. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G . A subtree T of G is a S -Steiner tree if S ⊆ V ( T ) . Two S -Steiner trees T 1 and T 2 are edge-disjoint (resp. internally vertex-disjoint ) if E ( T 1 ) ∩ E ( T 2 ) = ∅ (resp. E ( T 1 ) ∩ E ( T 2 ) = ∅ and V ( T 1 ) ∩ V ( T 2 ) = S ). Let λ G ( S ) (resp. κ G ( S ) ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S -Steiner trees in G , and let λ k ( G ) (resp. κ k ( G ) ) be the minimum λ G ( S ) (resp. κ G ( S ) ) for S ranges over all k -subset of V ( G ) . Kriesell conjectured that if λ G ( { x , y } ) ≥ 2 k for any x , y ∈ S , then λ G ( S ) ≥ k . He proved that the conjecture holds for | S | = 3 , 4 . In this paper, we give a short proof of Kriesell’s Conjecture for | S | = 3 , 4 , and also show that λ k ( G ) ≥ 1 k − 1 k ℓ 2 (resp. κ k ( G ) ≥ 1 k − 1 k ℓ 2 ) if λ ( G ) ≥ ℓ (resp. κ ( G ) ≥ ℓ ) in G , where k = 3 , 4 . Moreover, we also study the relation between κ k ( L ( G ) ) and λ k ( G ) , where L ( G ) is the line graph of G . [ABSTRACT FROM AUTHOR]

Let ρ ( D ( G )) denote the distance spectral radius of a graph G and ∂ ( G → ) denote the distance signless Laplacian spectral radius of a digraph G → . Let G n , k D be the set of all k -connected graphs of order n with diameter D . In this paper, we first determine the unique graph with minimum distance spectral radius in G n , k D ; we then give sharp upper and lower bounds for the distance signless Laplacian spectral radius of strongly connected digraphs; we also characterize the digraphs having the maximal and minimal distance signless Laplacian spectral radii among all strongly connected digraphs; furthermore, we determine the extremal digraph with the minimal distance signless Laplacian spectral radius with given dichromatic number. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we initiate the study of a variation of standard domination, namely total restrained domination. Let be a graph. A set is a total restrained dominating set if every vertex in has at least one neighbor in and at least one neighbor in , and every vertex in has at least one neighbor in . The total restrained domination number of , denoted by , is the minimum cardinality of all total restrained dominating sets of . We determine the best possible upper and lower bounds for , characterize those graphs achieving these bounds and find the best possible lower bounds for where both and are connected. [Copyright &y& Elsevier]

• The study on D − matrix, D Q − matrix, and D α − matrix is a hot research topic. And D α − matrix has attracted many scholars to study for its structure. • The graph transformations in this paper are clever and can be generalized. Also, the conclusions have generalized some known results. • In this paper, we depict the extremal graph with maximum D α − spectral radius among U n c (n ≥ 8) for any α ∈ 0 , 1 2 , and also characterize the graphs among T n c that reach the maximum and minimum of D α − spectral radius for any α ∈ 0 , 1 , respectively. Let D (G) and T r (G) be the distance matrix and diagonal matrix with vertex transmissions of a connected graph G , separately. Define matrix D α (G) as D α (G) = α T r (G) + (1 − α) D (G) , 0 ≤ α ≤ 1. Let U n = { G | G is a simple connected graph with | V (G) | = | E (G) | = n } , T n = { T | T is a tree of order n } and their complement sets be U n c and T n c , separately. In this paper, we generalize the conclusions in Qin et al. (2020) to D α -matrix: we depict the extremal graph with maximum D α -spectral radius among U n c (n ≥ 8) for any α ∈ 0 , 1 2 , and also characterize the graphs among T n c that reach the maximum and minimum of D α -spectral radius for any α ∈ 0 , 1 , respectively. [ABSTRACT FROM AUTHOR]

Edge fault-tolerance of interconnection network is of significant important to the design and maintenance of multiprocessor systems. A connected graph G is maximally edge-connected (maximally- λ for short) if its edge-connectivity attains its minimum degree. G is super edge-connected (super- λ for short) if every minimum edge-cut isolates one vertex. The edge fault-tolerance of the maximally- λ (resp. super- λ) graph G with respect to the maximally- λ (resp. super- λ) property, denoted by m λ (G) (resp. S λ (G)), is the maximum integer m for which G − S is still maximally- λ (resp. super- λ) for any edge subset S with | S | ≤ m. In this paper, we give upper and lower bounds on m λ (G). Furthermore, we completely determine the exact values of m λ (G) and S λ (G) for vertex transitive graphs. [ABSTRACT FROM AUTHOR]

Given a signed graph G ˙ , let A (G ˙) denote its adjacency matrix. The eigenvalues of A (G ˙) are called the eigenvalues of G ˙. In this study we focus on the least eigenvalues of connected signed graphs, and consider the behavior of the least eigenvalue of a signed graph when it is perturbed by some edge variations. In particular, we identify the first four smallest eigenvalues with their extremal signed graphs among all the unbalanced signed bicyclic graphs of order n ≥ 31 and range them corresponding to their least eigenvalues in an increasing order. [ABSTRACT FROM AUTHOR]

Abstract Mader (2010) conjectured that for every positive integer k and every finite tree T with order m , every k -connected, finite graph G with δ (G) ≥ ⌊ 3 2 k ⌋ + m − 1 contains a subtree T ′ isomorphic to T such that G − V (T ′) is k -connected. The conjecture has been verified for paths, trees when k = 1 , and stars or double-stars when k = 2. In this paper we verify the conjecture for two classes of trees when k = 2. For digraphs, Mader (2012) conjectured that every k -connected digraph D with minimum semi-degree δ (D) = min { δ + (D) , δ − (D) } ≥ 2 k + m − 1 for a positive integer m has a dipath P of order m with κ (D − V (P)) ≥ k. The conjecture has only been verified for the dipath with m = 1 , and the dipath with m = 2 and k = 1. In this paper, we prove that every strongly connected digraph with minimum semi-degree δ (D) = min { δ + (D) , δ − (D) } ≥ m + 1 contains an oriented tree T isomorphic to some given oriented stars or double-stars with order m such that D − V (T) is still strongly connected. [ABSTRACT FROM AUTHOR]

Abstract: An orientation of a graph is a -orientation if under this orientation, the net out-degree at every vertex is congruent to zero . If for any function satisfying , always has an orientation such that the net out-degree at every vertex is congruent to , then is strongly -connected. In this paper, we prove that a connected graph has a -orientation if and only if it is a contraction of a -regular bipartite graph. We also proved that every -edge-connected series–parallel graph is strongly -connected, and every simple -connected chordal graph is strongly -connected. [Copyright &y& Elsevier]