Search

• Embedding cycles into a network topology is crucial for the network simulation. • This paper investigates the problem of embedding spanning disjoint cycles in enhanced hypercube networks with each cycle containing a prescribed vertex. • It is shown that the n -dimensional enhanced hypercube Q n , m is k-spanning cyclable if k ≤ n and n ≥ 4 , and k -spanning cyclable if k ≤ n − 1 and n = 2 , 3. Moreover, some experimental examples are provided to verify the theoretical results. Embedding cycles into a network topology is crucial for the network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph G is called k -spanning cyclable if, for any k distinct vertices v 1 , v 2 , ... , v k of G , there exist k cycles C 1 , C 2 , ... , C k in G such that v i is on C i for every i , and every vertex of G is on exactly one cycle C i. If k = 1 , this is the classical Hamiltonian problem. In this study, we focus on embedding spanning disjoint cycles in enhanced hypercube networks and show that the n -dimensional enhanced hypercube Q n , m is k -spanning cyclable if k ≤ n and n ≥ 4 , and k -spanning cyclable if k ≤ n − 1 and n = 2 , 3. Moreover, the results are optimal with respect to the degree of Q n , m , and some experimental examples are provided to verify the theoretical results. [ABSTRACT FROM AUTHOR]

• Determine κ (M B n ; P l) and κ s (M B n ; P l) for n ≥ 5 and 2 ≤ l ≤ 2 n. • Determine κ (M B n ; C 2 l) and κ s (M B n ; C 2 l) for 6 ≤ 2 l ≤ n. • Determine κ (M B n ; T 2 l) and κ s (M B n ; T 2 l) for 1 ≤ l ≤ n − 2. • Provide the upper bounds of κ (M B n ; K 1 ; l) and κ s (M B n ; K 1 ; l) for n ≥ 4 and 2 ≤ l ≤ n , and show that these upper bounds are sharp for l = 2 ; 3 ; 4. Let G be a graph and H be a fixed connected subgraph. Let H = { H 1 , H 2 , ⋯ , H k } be a set of connected subgraphs of G. The H -structure connectivity (resp. H -substructure connectivity) κ (G ; H) (resp. κ s (G ; H)) is defined as the least cardinality of H such that H i is isomorphic to H (resp. a connected subgraph of H) for any 1 ≤ i ≤ k , and H 's deletion makes G disconnected or trivial. As an extension of the classic connectivity, the H -structure (resp. H -substructure) connectivity can better evaluate the fault-tolerance of an interconnection network. In this paper, we focus on the n -dimensional modified bubble-sort graph M B n. We determine κ (M B n ; P l) (resp. κ s (M B n ; P l) , where n ≥ 5 , 2 ≤ l ≤ 2 n , and P l is a path on l vertices; κ (M B n ; C 2 l) (resp. κ s (M B n ; C 2 l)), where 6 ≤ 2 l ≤ n , and C 2 l is a cycle on 2 l vertices; κ (M B n ; T 2 l) (resp. κ s (M B n ; T 2 l)), where 1 ≤ l ≤ n − 2 and T 2 l is an l -leaves 2-step star. In addition, we give the upper bound of κ (M B n ; K 1 , l) (resp. κ s (M B n ; K 1 , l)), where n ≥ 4 and 2 ≤ l ≤ n and K 1 , l is a star on l + 1 vertices, and prove that the upper bounds are sharp for l = 2 , 3 , 4. [ABSTRACT FROM AUTHOR]

Let D be a digraph with vertex set V(D) and arc set A(D). An antidirected Hamiltonian path (resp. cycle) of D is a Hamiltonian path (resp. cycle) in which consecutive arcs have opposite directions and each arc of D occurs exactly once. Let α 2 (D) = max { | W | : W ⊆ V (D) and D[W] has no 2-cycle } be the α 2 (D) -stable number. In this paper, we show that every weakly connected digraph D with α 2 (D) = 2 has an antidirected Hamiltonian path. Secondly, we determine two families of well-characterized strongly connected digraphs H and M such that for any strongly connected digraph D ∈ H ∪ M which has no antidirected Hamiltonian cycle. And finally, we further prove that every strongly connected digraph D with α 2 (D) = 2 has an antidirected Hamiltonian cycle if and only if |V(D)| is even and D ∉ H ∪ M . [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]

• An Ore type condition for a strong digraph to be supereulerian is obtained. • A previous result given by Bang-Jensen in 2015 is extended. • A conjecture for a 2-strong digraph to be supereulerian is proposed. A digraph D is called supereulerian if D has a spanning eulerian subdigraph. In this article, we show that a strong digraph D with n vertices is supereulerian if for every three different vertices z , w and v such that z and w are nonadjacent, d (z) + d (w) + d + (z) + d − (v) ≥ 3 n − 5 (if (z , v) ∉ A (D)) and d (z) + d (w) + d − (z) + d + (v) ≥ 3 n − 5 (if (v , z) ∉ A (D)). And this bound is sharp. [ABSTRACT FROM AUTHOR]

Embedding cycles into a network topology is crucial for the network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph G is called k -spanning cyclable if, for any k distinct vertices v 1 , v 2 , ... , v k of G , there exist k cycles C 1 , C 2 , ... , C k in G such that v i is on C i for every i , and every vertex of G is on exactly one cycle C i. If k = 1 , this is the classical Hamiltonian problem. In this paper, we focus on embedding spanning disjoint cycles in Cayley graphs Γ n generated by transposition trees and show that Γ n is k -spanning cyclable if k ≤ n − 2 and n ≥ 3. Moreover, the result is optimal with respect to the degree of Γ n. [ABSTRACT FROM AUTHOR]

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]

A bipartite graph with bipartition A and B is said to be Hamilton-laceable if for any u ∈ A and v ∈ B there is a Hamilton path joining u and v. It is known that the double generalized Petersen graph D P (n , k) is Hamiltonian and is bipartite if and only if n is even. In this paper we show that the bipartite double generalized Petersen graph D P (n , k) is Hamilton-laceable for n ≥ 4. [ABSTRACT FROM AUTHOR]

• Some classic results about Hamiltonicity of graphs are generalized to spanning connectedness. • Extremal number of edges, which can guarantee that a graph to be spanning connected, was determined. Let G = (V , E) be a graph and u , v be two arbitrary vertices of V (G). Then G is hamilton-connected if there exists a spanning path between u and v , and G is hamiltonian if there exist two internally disjoint pathes between u and v and the union of these two paths spans V (G). More generally, G is said to be spanning k -connected if there exist k internally disjoint pathes between u and v and the union of these k pathes contains all vertices of G. In the paper, we first generalize a classic theorem of Vergnas on hamiltonian graphs to spanning k -connectedness. Furthermore, we determine extremal number of edges in a spanning k -connected graph by extending an old theorem due to Erdős. Finally, we partially establish spanning k -connected versions of famous Chvátal-Erdős theorem. [ABSTRACT FROM AUTHOR]

Let H = (V, E) be a hypergraph, where V is a set of vertices and E is a set of non-empty subsets of V called edges. If all edges of H have the same cardinality r, then H is an r-uniform hypergraph; if E consists of all r-subsets of V, then H is a complete r-uniform hypergraph, denoted by Krn, where n = |V |. An r-uniform hypergraph H = (V, E) is (k, l)-edge-maximal if every subhypergraph H′ of H with |V (H′)| ≥ l has edge-connectivity at most k, but for any edge e ∈ E(Knr) \ E(H), H + e contains at least one subhypergraph H′′ with |V (H′′)| ≥ l and edge-connectivity at least k +1. In this paper, we obtain the lower bounds and the upper bounds of the sizes of (k, l)-edge-maximal hypergraphs. Furthermore, we show that these bounds are best possible. [ABSTRACT FROM AUTHOR]

• The design of DCNs represented by DCell networks is a hot research topic. DCell is an excellent network performing by using a large number of servers and inexpensive commodity switches. As a server-centric DCN, DCell has many desirable features. • The concept of k -restricted edge-connectivity proposed by Fábrega and Foil has been applied successfully in the further study of fault tolerance and reliability of networks. • For any integers m ≥ 0 and n ≥ 2 , we use D m , n to denote the m-dimensional DCell with n -port switches. We completely determine the k-restricted edge-connectivity of D m , n and we also characterize the structure of the minimum λ k -cuts of D m , n for 2 ≤ k ≤ n. For any integers m ≥ 0 and n ≥ 2 , we use D m , n to denote the m -dimensional DCell with n -port switches. For a simple graph G = (V , E) , an edge subset S ⊂ E (G) is said to be a λ k -cut of G , if G − S is disconnected and each component of G − S has at least k vertices. The k -restricted edge-connectivity of G , denoted by λ k (G) , is the minimum cardinality of all λ k -cuts of G. We prove that λ k (D m , n) = k (m + n − k) for m ≥ n ≥ 2 and 2 ≤ k ≤ n , λ k (D m , n) = m n for n > m ≥ 2 and m ≤ k ≤ n and λ k (D m , n) = k (m + n − k) for n > m ≥ 2 and 2 ≤ k < m. We also characterize the structure of the minimum λ k -cuts of D m , n in terms of the above conclusions. [ABSTRACT FROM AUTHOR]

The interconnection network between the storage system and the multi-core computing system is the bridge for communication of enormous amounts of data access and storage, which is the critical factor in affecting the performance of high-performance computing systems. By enforcing additional restrictions on the definition of R -structure and R -substructure connectivities to satisfy that each remaining vertex has not less than r neighbors, we can dynamically assess the cardinality of the separated component to meet the above conditions under structure faulty, thereby enhancing the evaluation of the fault tolerance and reliability of high-performance computing systems. Let R be a connected subgraph of a connected graph G. The r -restricted R -structure connectivity κ r (G ; R) (resp. r -restricted R -substructure connectivity κ r s (G ; R)) of G is the minimum cardinality of a set of subgraphs F = { F 1 , F 2 , ... , F m } such that F i is isomorphic to R (resp. F i is a connected subgraph of R) for 1 ≤ i ≤ m , and G − F is disconnected with the minimum degree of each component being at least r. Note that κ r (G ; K 1) reduces to r -restricted connectivity κ r (G) (also called r -good neighbor connectivity). In this paper, we focus on κ r (K L n ; R) and κ r s (K L n ; R) for the L -ary n -dimensional hamming graph K L n , where R ∈ { K 1 , K 1 , 1 , K L 1 }. For 0 ≤ r ≤ n − 3 , n ≥ 3 and L ≥ 3 , we determine the (L − 1) r -good neighbor connectivity of K L n , i.e., κ (L − 1) r (K L n) = (L − 1) (n − r) L r , and the (L − 1) r -good neighbor diagnosability of K L n under the PMC model and MM* model, i.e., t (L − 1) r (K L n) = [ (L − 1) (n − r) − 1 ] L r − 1. And we also drive that κ (L − 1) r (K L n ; K 1 , 1) = κ (L − 1) r s (K L n ; K 1 , 1) = 1 2 (L − 1) L r (n − r) for 1 ≤ r ≤ n − 3 , n ≥ 4. Moreover, we offer an upper bound of κ 2 (K L n ; K L 1) (resp. κ 2 s (K L n ; K L 1)) for n ≥ 3 , and establish that it is sharp for ternary n -cubes K 3 n. Specifically, κ 2 (K 3 n ; K 3 1) = κ 2 s (K 3 n ; K 3 1) = 2 (n − 1) for n ≥ 3. • Focus on r -restricted R -structure connectivity κ r (K L n ; R) and r -restricted R -substructure connectivity κ r s (K L n ; R) for K L n. • Determining the exact value of κ r (K L n ; K 1) for 0 ≤ r ≤ n − 3 , n ≥ 3. • Determining the exact values of κ (L − 1) r (K L n ; K 1 , 1) and κ (L − 1) r s (K L n ; K 1 , 1) for 1 ≤ r ≤ n − 3 , n ≥ 4. • Provide the upper bounds of κ 2 (K L n ; K L 1) and κ 2 s (K L n ; K L 1) , and establish that these upper bounds are sharp for ternary n -cubes K 3 n (n ≥ 3). [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]

• New sufficient conditions for graphs to be spanning connected are provided. • Some known classic results about Hamiltonicity of graphs are extended. A graph G is t *-connected if there exist t internally disjoint (u, v)-paths, between any two vertices u and v , whose union spans G. In this sense, t *-connectedness is a natural extension of hamiltonicity. In this paper, we provide a sufficient condition for graphs to be t *-connected by generalizing a classic result given by Chavátal [7]. Furthermore, as byproducts, we extend some known results concerning fault tolerant hamiltonicity and minimum cardinality of edges. We also establish analogous results for balanced bipartite graphs. [ABSTRACT FROM AUTHOR]

For any real number α ∈ [ 0 , 1 ] and a graph G , Nikiforov [20] defined matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). The A α - spectral radius of G is the largest eigenvalue of A α (G). In this paper, we determine the first three largest extremal graphs in Halin graphs by their A α - spectral radii when 1 2 ≤ α < 1. For 0 ≤ α ≤ 1 , the 3-regular Halin graph alone minimizes the A α - spectral radius for Halin graphs. [ABSTRACT FROM AUTHOR]

For any real α ∈ [ 0 , 1 ] , define the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). The collection of eigenvalues of A α (G) together with multiplicities is called the A α -spectrum of G. A graph G is said to be determined by its A α -spectrum if any graph that is A α -cospectral with G is isomorphic to G. Lin et al. (2019) proposed characterizing graphs G determined by their A α -spectra such that G ∨ K m (m ≥ 1) are also determined by their A α -spectra for α ∈ (1 2 , 1). In this paper, we get that if G ∈ { K 2 , ... , 2 ︸ ⌊ n 2 ⌋ − 1 ∨ (K 1 ∪ K 2) , K 2 , ... , 2 ︸ n 2 , ⋃ i = 1 t C s i , ⋃ i = 1 t C s i ¯ , ⋃ i = 1 t P s i , F n , n K 1 } , then G and G ∨ K m (m ≥ 2) are both determined by their A α -spectra for α ∈ (1 2 , 1) , which generalizes some results of Lin, Liu and Xue. [ABSTRACT FROM AUTHOR]

The fractional matching preclusion number of a graph is the minimum number of edges whose deletion results in the remaining graph that has no fractional perfect matchings. For many networks, their optimal fractional matching preclusion sets are precisely those edges incident with a single vertex. The probability that all failures concentrate around a vertex is often small. To overcome the shortcoming, we consider the concept of conditional fractional matching preclusion, in which isolated vertices are not permitted in fault networks. We establish the conditional fractional matching preclusion numbers and all possible minimum conditional fractional matching preclusion sets for n -dimensional torus networks with n ≥ 3. [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 , the matrix A α (G) of a graph is defined as A α (G) = α D (G) + (1 − α) A (G). Denote its eigenvalues by λ 1 (A α (G)) ≥ λ 2 (A α (G)) ≥ ⋯ ≥ λ n (A α (G)). In this paper, for 1 / 2 < α < 1 , the Nordhaus-Gaddum type bound for the second largest A α -eigenvalue of a graph is considered. We show that λ 2 (A α (G)) + λ 2 (A α (G ‾)) ≥ n α − 1 , and the extremal graphs for which the equality holds are K n and S n. If G ∉ { K n , S n , K n − e } , then λ 2 (A α (G)) + λ 2 (A α (G ‾)) ≥ (n − 1) α. Moreover, we give two upper Nordhaus-Gaddum type bounds for the second largest A α -eigenvalue of a graph. [ABSTRACT FROM AUTHOR]

Let H be a connected hypergraph with minimum degree δ and edge-connectivity λ . The hypergraph H is maximally edge-connected if λ = δ , and it is super edge-connected or super- λ , if every minimum edge-cut consists of edges incident with some vertex. There are several degree sequence conditions, for example, Goldsmith and White (Discrete Math 23: 31–36, 1978) and Bollobás (Discrete Math 28:321–323, 1979) etc. for maximally edge-connected graphs and super- λ graphs. In this paper, we generalize these and some other degree sequence conditions to uniform hypergraphs. [ABSTRACT FROM AUTHOR]

The k-component connectivity c κ k (G) of a non-complete graph G is the minimum number of nodes whose deletion results in a graph with at least k components. A node subset S of G is called an optimal k-component cut if | S | = c κ k (G) and G - S has exactly k components. In this paper, we determine the component connectivity of the locally twisted cube L T Q n , i.e. c κ k + 1 (L T Q n) = k n - k (k + 1) / 2 + 1 for 1 ≤ k ≤ n - 1 , n ≥ 2 , and characterize optimal k-component cuts of L T Q n . [ABSTRACT FROM AUTHOR]