Search

The stability, robustness, accuracy, and efficiency of space-time finite element methods crucially depend on the choice of approximation spaces for test and trial functions. This is especially true for high-order, mixed finite element methods which often must satisfy an inf-sup condition in order to ensure stability. With this in mind, the primary objective of this paper and a companion paper is to provide a wide range of explicitly stated, conforming, finite element spaces in four dimensions. In this paper, we construct explicit high-order conforming finite elements on 4-cubes (tesseracts); our construction uses tools from the recently developed 'Finite Element Exterior Calculus'. With a focus on practical implementation, we provide details including Piola-type transformations, and explicit expressions for the volumetric, facet, face, edge, and vertex degrees of freedom. In addition, we establish important theoretical properties, such as the exactness of the finite element sequences, and the unisolvence of the degrees of freedom. [ABSTRACT FROM AUTHOR]

An exchanged hypercube is a spanning subgraph of a hypercube. It retains a large number of desirable properties of the hypercube, yet maintains a reduced interconnection complexity. This paper shows that the graph is isomorphic to an induced subgraph of the hypercube of the least possible size. Further, the minimal hypercube consists of two factors, each of which comprises as many vertex-disjoint copies of the induced subgraph. The result is seamlessly inherited by the dual-cube that is known to be a special case of the exchanged hypercube. [ABSTRACT FROM AUTHOR]

Let ex (Q n , H) be the largest number of edges in a subgraph G of a hypercube Q n such that there is no subgraph of G isomorphic to H. We show that for any integer k ≥ 3 ex (Q n , C 4 k + 2) = O (n 5 6 + 1 3 (2 k − 2) 2 n). [ABSTRACT FROM AUTHOR]

The Fibonacci cube Γ n is the subgraph of hypercube Q n induced by the binary strings that contain no two consecutive 1s, and the Lucas cube Λ n is obtained from Γ n by removing vertices that start and end with 1. For p ≥ 1 , the subgraph of hypercube Q n induced by the strings that contain no 1 0 s 1 for all s < p is called the Fibonacci p -cube and denoted by Γ n p , and the subgraph of hypercube Q n induced by the strings in which 1 0 s 1 (s < p) is forbidden in a circular manner is called the Lucas p -cube and denoted by Λ n p. Clearly, the Fibonacci cube Γ n is Γ n 1 , and the Lucas cube Λ n is Λ n 1. In this paper, first of all, some general properties of Γ n p and Λ n p , such as the recursive structures, the number of vertices and edges, the diameter, the radius and centers, and the medianicity, are investigated. Furthermore, based on these properties, the Wiener index and cube polynomials of Γ n p and Λ n p are studied. Finally, some problems and questions are proposed. [ABSTRACT FROM AUTHOR]

Let G be a connected simple graph with vertex set V (G) and edge set E (G). For S ⊆ V (G) , let π G (S) and κ G (S) denote the maximum number of internally disjoint S -paths and S -trees, respectively, in G. For an integer k with k ≥ 2 , the k -path-connectivity π k (G) (resp. k -tree-connectivity κ k (G)) is defined as the minimum π G (S) (resp. κ G (S)) over all k -subsets S of V (G). It is proved that deciding whether π G (S) ≥ k is NP-complete for a given S in Li et al. (2021). In this paper, the upper bound of π 3 (Q n) is gotten by using the result π 3 (G) ≤ ⌊ 3 k − r 4 ⌋ for a k -regular graph G , where r = max { | N G (x) ∩ N G (y) ∩ N G (z) | : { x , y , z } ⊆ V (G) }. Furthermore, we consider the 3-path-connectivity of the n -dimensional hypercube Q n and prove that π 3 (Q n) = ⌊ 3 n − 1 4 ⌋ for n ≥ 2 , which implies that the upper bound for Q n is tight. [ABSTRACT FROM AUTHOR]

• To improve the local diagnosability of a vertex, we propose a new structure for a vertex to be locally t -diagnosable. • We also provide the corresponding diagnosis algorithm for the new structure. • We provide a sufficient and necessary condition for a vertex to be locally optimal diagnosed in faulty hypercubes. • We also give a sufficient and necessary condition for a vertex to be locally optimal diagnosed in faulty folded hypercubes. PMC model is the test-based diagnosis which a vertex performs the diagnosis by testing the neighbor vertices via the edges between them. If we only care about the status of a particular vertex, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed two structures to diagnose a vertex. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of a vertex is equal to its degree then we say it is locally optimal diagnosable. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the two structures mentioned above. Herein, we propose a new testing structure and corresponding diagnosis algorithm to diagnose a vertex under PMC model to better evaluate the local diagnosability. And this diagnosis algorithm takes linear time. Based on this new structure, we give a sufficient condition for a vertex to be locally optimal diagnosable. As its applications, we consider the sufficient and necessary condition for a vertex of hypercubes (resp. folded hypercubes) with faulty edges to be locally optimal diagnosable. [ABSTRACT FROM AUTHOR]

In the paper of Manuel et al. [10] the minimum wirelength of embedding hypercube into cylinder was given as a conjecture. We show that Gray code embedding is an optimal strategy for the conjecture. In the paper, we prove the lower bound of the wirelength as two parts respectively, one of which is studied by the edge isoperimetric problem (EIP) related to the type sequence. The technique is totally different from the previous work in Refs. [10,11,1,6]. [ABSTRACT FROM AUTHOR]

The k -ary n -cube, denoted Q n k , has the vertex set V n k = { 0 , 1 , ... , k − 1 } n , and two vertices (x 1 , x 2 , x 3 , ... , x n) and (y 1 , y 2 , y 3 , ... , y n) in V n k are adjacent if and only if there is an integer j with 1 ≤ j ≤ n such that x j ≡ y j ± 1 (mod k) and x i = y i for all i ∈ { 1 , 2 , ... , n } ∖ { j }. Let λ (F) be the vertex Turán density of a graph G for a family of forbidden configurations F. Let F 1 = { (0 , 0 , 0) , (1 , 0 , 0) , (0 , 1 , 0) , (0 , 0 , 1) } , F 2 = { (0 , 0 , 0) , (1 , 1 , 0) , (1 , 0 , 1) , (0 , 1 , 1) } , F 3 = { (0 , 0 , 0) , (1 , 1 , 1) } , F d , t , k = { F ⊆ V d k : | F | = t } , and μ (d , k) = max { t : λ (F d , t , k) = 0 }. Johnson and Talbot (2010) determined λ (F i) for i ∈ { 1 , 2 , 3 } and the bounds of μ (d , 2) in Q n 2 (where Q n 2 is the n -dimensional hypercube Q n). In this paper, we derive the exact value λ (F i) for i ∈ { 1 , 2 , 3 } in Q n 3 and determine the bounds of μ (d , k) in Q n k for any k ≥ 3. Furthermore, we consider the forbidden configurations D i = { x ∈ V 3 k : | x | = 0 or | x | = i }. The bounds of λ (D i) in Q n k are derived for any i ∈ { 1 , 2 , 3 } and k ≥ 2 , and λ (G d) = 2 / 3 in Q n 3 is derived, where G d = { x ∈ V d 3 : | x | = 0 , (| x | = 1 , qsupp (x) = i [ 1 ] ) and (| x | = 2 , qsupp (x) = { i [ 1 ] , j [ 1 ] } , i ⁄ ≡ j (mod 2)) } (see Definition 1 for qsupp (x)). [ABSTRACT FROM AUTHOR]

Edge connectivity is often used to capture edge fault tolerance. As for most common networks, their edge connectivity is exactly equal to their minimum degree. Edge matroidal connectivity and conditional edge matroidal connectivity are two new graph edge connectivity parameters that can be defined when a partition of the edge set is given, for example when the network is built with different kinds of edges having different expected faultiness. And those two edge connectivity parameters can measure edge fault tolerance more than the traditional definition. The edge matroidal connectivity is based on the associated edge partition and the other is a generalization called conditional edge matroidal connectivity. We analyze these new parameters on hypercubes and folded hypercubes which are well studied networks. In this study, we consider their standard dimensional partition of the edges. This study leads to more structural insights about edge connectivity and yields many interesting questions. • We propose two new edge connectivity parameters for a graph based on the associated edge partition. • The two edge connectivity parameters are edge matroidal connectivity and conditional edge matroidal connectivity. • We analyze the (conditional) edge matroidal connectivity for hypercubes and folded hypercubes. [ABSTRACT FROM AUTHOR]

The 2-packing number ρ 2 (G) of a graph G is the cardinality of a largest 2-packing of G and the open packing number ρ o (G) is the cardinality of a largest open packing of G , where an open packing (resp. 2-packing) is a set of vertices in G no two (closed) neighborhoods of which intersect. It is proved that if G is bipartite, then ρ o (G □ K 2) = 2 ρ 2 (G). For hypercubes, the lower bounds ρ 2 (Q n) ≥ 2 n − ⌊ log ⁡ n ⌋ − 1 and ρ o (Q n) ≥ 2 n − ⌊ log ⁡ (n − 1) ⌋ − 1 are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that Q 9 is the smallest hypercube which is not perfect injectively colorable. It is also proved that γ t (Q 2 k × H) = 2 2 k − k γ t (H) , where H is an arbitrary graph with no isolated vertices. [ABSTRACT FROM AUTHOR]

The modular decomposition of a symmetric map δ : X × X → Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T , t) if the label δ (x , y) coincides with the label of the lowest common ancestor of x and y in T , i.e., if δ (x , y) = t (lca (x , y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map δ. [ABSTRACT FROM AUTHOR]

In this paper, we consider the minimal doubly resolving set problem in Hamming graphs, hypercubes and folded hypercubes. We prove that the minimal doubly resolving set problem in hypercubes is equivalent to the coin weighing problem. Then we answer an open question on the minimal doubly resolving set problem in hypercubes. We disprove a conjecture on the metric dimension problem in folded hypercubes and give some asymptotic results for the metric dimension and the minimal doubly resolving set problems in Hamming graphs and folded hypercubes by establishing connections between these problems. Using the Lindström's method for the coin weighing problem, we give an efficient algorithm for the minimal doubly resolving set problem in hypercubes and report some new upper bounds. We also prove that the minimal doubly resolving set problem is NP-hard even restrict on split graphs, bipartite graphs and co-bipartite graphs. [ABSTRACT FROM AUTHOR]

The connectivity and its generalizations have been well studied due to their impact on the fault tolerance and diagnosability of the interconnection networks. In this paper, we introduce a novel generalized connectivity, which combines the h -extra connectivity and r -component connectivity. Given a connected graph G = (V , E) , for any h ≥ 0 and r ≥ 2 , an h -extra r -component cut of G is a subset S ⊆ V such that there are at least r components in G ∖ S and each component has at least h + 1 vertices; h -extra r -component connectivity of G , denoted as c κ r h (G) , is the minimum size of any h -extra r -component cut of G. We determine the h -extra r -component connectivity of n -dimensional hypercube Q n , c κ r 1 (Q n) = 2 (r − 1) (n − r + 1) for r ∈ { 2 , 3 , 4 }. [ABSTRACT FROM AUTHOR]

The n -dimensional hypercube Q n is one of the most attractive interconnection networks for multiprocessor systems and it is a bipartite graph. Let F v be a set of the end-nodes of k independent edges in Q n and F e be a set of f edges in Q n − F v. Given a linear forest L of Q n − F v − F e , in this paper, we prove that (i) Q n − F v − F e admits a hamiltonian cycle passing through L if | E (L) | + k + f ≤ n − 2 ; and (i i) for any two nodes x and y of the opposite partite sets in Q n − F v − F e such that none of the paths in L has x or y as internal node or both of them as end-nodes, Q n − F v − F e admits a hamiltonian path between x and y passing through L if | E (L) | + k + f ≤ n − 3 ; and (i i i) for any two distinct nodes u and v of the partite set not containing w in Q n − F v − F e − w such that none of the paths in L has u or v as internal node or both of them as end-nodes, Q n − F v − F e − w admits a hamiltonian path between u and v passing through L if | E (L) | + k + f ≤ n − 3 , where w is an arbitrary node in Q n − F v − F e. [ABSTRACT FROM AUTHOR]

The Fibonacci cube is the subgraph of the hypercube induced by the vertices whose binary string representations do not contain two consecutive 1s. These cubes were presented as an alternative interconnection network. In this paper, we calculate the number of induced paths and cycles of small length in Fibonacci cubes by using the recursive structure of these graphs. [ABSTRACT FROM AUTHOR]

Among the classical models for interconnection networks are hypercubes and Fibonacci cubes. Fibonacci cubes are induced subgraphs of hypercubes obtained by restricting the vertex set to those binary strings which do not contain consecutive 1s, counted by Fibonacci numbers. Another set of binary strings which are counted by Fibonacci numbers are those with a restriction on the runlengths. Induced subgraphs of the hypercube on the latter strings as vertices define Fibonacci-run graphs. They have the same number of vertices as Fibonacci cubes, but fewer edges and different graph theoretical properties. We obtain properties of Fibonacci-run graphs including the number of edges, the analogue of the fundamental recursion, the average degree of a vertex, Hamiltonicity, special degree sequences, and the number of hypercubes they contain. A detailed study of the degree sequences of Fibonacci-run graphs is interesting in its own right and is reported in a companion paper. [ABSTRACT FROM AUTHOR]

The connectivity of a graph G , κ (G) , is the minimum cardinality over all vertex-cuts in G , and the value of κ (G) can be determined using Menger's theorem. It has long been one of the most important factors that characterize both graph reliability and fault tolerability. A graph G is super connected if its minimum vertex-cut is always composed of a vertex's neighborhood. In this article we define the super H -connectivity κ ′ (G | H) and the super H ∗ -connectivity κ ′ (G | H ∗) as new measures to evaluate the connectedness of G , for which H denotes a connected graph that represents the structure of the clustered faults, and H ∗ denotes the union of the set of all connected subgraphs of H and the set of the trivial graph. Then we establish both κ ′ (Q n | H) and κ ′ (Q n | H ∗) for H ∈ { K 1 , m ∣ m = 1 , 2 , 3 , 4 } ∪ { P 4 , C 4 } , where Q n denotes the n -dimensional hypercube, K 1 , m denotes the m -star structure for m ≥ 1 , P 4 denotes a path of order four and C 4 is a cycle of order four. [ABSTRACT FROM AUTHOR]

The n -dimensional hypercube has n + 1 distinct eigenvalues n − 2 i , 0 ≤ i ≤ n , with corresponding eigenspaces U i (n). In 2021 it was proved by the author that if a function with non-empty support belongs to the direct sum U i (n) ⊕ U i + 1 (n) ⊕ ⋯ ⊕ U j (n) , where 0 ≤ i ≤ j ≤ n , then it has at least max ⁡ (2 i , 2 n − j) non-zeros. In this work we give a characterization of functions achieving this bound. [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]

Reliability measure of multiprocessor systems is of significant importance to the design and maintenance of multiprocessor systems. Based on edge connectivity, more refined quantitative indicators for the reliability of multiprocessor systems have been introduced. The extra edge connectivity and the component edge connectivity, as two important parameters to evaluate the robustness of multiprocessor systems, are explored extensively. In this paper, we first determine the h -extra edge connectivity of the enhanced hypercube Q n , k (one potential alternative of hypercube) for 1 ≤ h ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 2 k + 4 and 1 ≤ h ≤ 2 ⌈ n 2 ⌉ , n ≤ 2 k + 3 , k ≥ 3. Some previous results in Zhang et al. (2016) and Sabir et al. (2019) are extended. Moreover, we also establish the g -component edge connectivity of the n -dimensional enhanced hypercube Q n , k for 1 ≤ g ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 13. As an easy extension, similar results for folded hypercube F Q n , another popular network structure, are readily derived. [ABSTRACT FROM AUTHOR]

The g -good-neighbor conditional diagnosability, which specifies at least g fault-free neighbors for each fault-free node, is a very important metric in system-level diagnosis. Recently, the g -good-neighbor conditional diagnosabilities of many networks have been investigated. To enhance the g -good-neighbor conditional diagnosability, the R g -conditional diagnosability, which requires at least g fault-free neighbors for each node, has been proposed by Guo et al. [1] (2020) recently. And they establish the R g -conditional diagnosability of the hypercubes under the PMC model. In this paper, we present some counterexamples for the proof of lower bound on the R g -conditional diagnosability of the hypercubes under the PMC model, which is crucial to the original main result. And we further utilize known results to give a reasonable lower bound for the R g -conditional diagnosability of hypercubes. [ABSTRACT FROM AUTHOR]

System-level diagnosis has become an important diagnosis method for multiprocessor systems. Among all system-level diagnosis measures, diagnosability is relatively small. The conditional diagnosability constraint that each vertex has at least one good neighbor is relatively conservative when the dimension is far greater than 1, and g-good-neighbor conditional diagnosability does not consider this restriction on faulty vertices. Therefore, a thorough study of diagnosability under the condition that each vertex has at least g good neighbors is an appealing subject. Motivated by R g vertex connectivity, in this paper, we introduce a novel generalized system-level diagnosis measure named R g conditional diagnosability, which assumes that every processor has at least g good neighbors. The popular conditional diagnosability is a special case of R g conditional diagnosability when g = 1. Then, we determine that the R g conditional diagnosability of n -dimensional hypercube Q n under the Preparata Metze Chien (PMC) model is 2 2 g (n − 2 g) + 2 2 g − 1 − 1. [ABSTRACT FROM AUTHOR]

Transmission of a vertex u in a graph G is defined as T(u) = ∑ v∈V(G) d(u,v) [1]. The expression T(G) = 1/2∑ u,v∈V(G) d(u,v) is called the transmission of G. Further the cardinality of the set {T(u)/u ∈ V(G)} is addressed as the transmission dimension of G and is denoted by dim T (G) [5]. Closeness centrality of a vertex v in G is defined as the reciprocal of the transmission of v. Using this centrality measure, the most important vertices in the graph are identified. In this paper we have computed the transmission of every vertex of an r -regular caterpillar and a spanning tree of the hypercube network. [ABSTRACT FROM AUTHOR]

A d -dimensional matrix is called 1 -polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1 -permutation matrix. A diagonal of a d -dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d -dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d , the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d , we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least n n 3 / 2 (1 / 2 − o (1)) 1-permutation matrices and contains a polytope of dimension at least c n 3 / 2 for fixed c , d and even n → ∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d , we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions. [ABSTRACT FROM AUTHOR]

We compare two kinds of pursuit-evasion games played on graphs. In Cops and Robbers, the cops can move strategically to adjacent vertices as they please, while in a new variant, called deterministic Zombies and Survivors, the zombies (the counterpart of the cops) are required to always move towards the survivor (the counterpart of the robber). The cop number of a graph is the minimum number of cops required to catch the robber on that graph; the zombie number of a graph is the minimum number of zombies required to catch the survivor on that graph. We answer two questions from the 2016 paper of Fitzpatrick, Howell, Messinger, and Pike. We show that for any integers m and k such that m ≥ k ≥ 1 , there is a graph with zombie number m and cop number k. We also show that the zombie number of the n -dimensional hypercube is ⌈ 2 n ∕ 3 ⌉. [ABSTRACT FROM AUTHOR]

• Consider Q n with | F e | + | F v | ≤ n − 3 faulty edges and vertices, where n ≥ 3. • There are vertex-disjoint odd paths P [ u , v ] and P [ x , y ] with lengths sum from 2 to 2 n − 2 | F v | − 2 in Q n joining edges (u , v) and (x , y). • One application is that we obtain Q n − F e is bipancyclic, where | F e | ≤ n − 2. • The result is optimal with respect to the number of fault-tolerant elements. Let Q n denote the n -dimensional hypercube and the set of faulty edges and faulty vertices in Q n be denoted by F e and F v , respectively. In this paper, we investigate Q n (n ≥ 3) with | F e | + | F v | ≤ n − 3 faulty elements, and demonstrate that there are two fault-free vertex-disjoint paths P [ a , b ] and P [ c , d ] satisfying that 2 ≤ ℓ (P [ a , b ]) + ℓ (P [ c , d ]) ≤ 2 n − 2 | F v | − 2 , where 2 | (ℓ (P [ a , b ]) + ℓ (P [ c , d ])) , (a , b) , (c , d) ∈ E (Q n). The contribution of this paper is: (1) we can quickly obtain the interesting result that Q n − F e is bipancyclic, where | F e | ≤ n − 2 and n ≥ 3 ; (2) this result is a complement to Chen's part result (Chen (2009) [2]) in that our result shows that there are all kinds of two disjoint-free (S , T) -paths which contain 4 , 6 , 8 , ... , 2 n − 2 | F v | vertices respectively in Q n when S = { a , c } , T = { b , d } , and (a , b) , (c , d) ∈ E (Q n). Our result is optimal with respect to the number of fault-tolerant elements. [ABSTRACT FROM AUTHOR]

The fault diagnosability has played an important role in the reliability of the interconnection network. In a network, the states of any two adjacent vertices can usually affect each other, and the neighbor of a faulty vertex is more likely to become faulty. These motivate our study of fault diagnosability from the perspective of some structures instead of basing on individual faulty vertices. Therefore, we introduce a novel measure of diagnosability, called structural diagnosability. Given a specific structure H , the H -structure diagnosability of a network G , denoted by t s (G ; H) , is the maximum number of pairwise disjoint subnetworks H 1 , H 2 , ... , H m in G , such that, for i = 1 , 2 , ... , m , H i is isomorphic to H and when all vertices in H i are faulty, these vertices can be diagnosed correctly. In this paper, we will establish t s (Q n ; H) for the n -dimensional hypercube Q n under the PMC model and MM* model, respectively, where H ∈ { K 1 , 1 , K 1 , 2 , K 1 , 3 , C 4 }. [ABSTRACT FROM AUTHOR]

Let G be a simple graph. A set of pairwise disjoint edges is a matching of G. The matching polytope of G , denoted M (G) , is the convex hull of the set of the incidence vectors of the matchings of G. The graph G (M (G)) , whose vertices and edges are the vertices and edges of M (G) , is the skeleton of the matching polytope of G , S M P (G) or, even simpler, S M P. In this paper, we consider the following questions: (1) Which graphs realize SMPs? (2) Given two non-isomorphic graphs, are their skeletons non-isomorphic as well? Concerning the first question, it is well-known (see Naddef and Pulleyblank (1984) and Balinski (1961) [3]) that neither non-connected graphs nor non-Hamiltonian graphs realize S M P s. Among other simple results, we characterize both planar graphs and bipartite graphs that occur as S M P s. The second question is completely solved here. For every G and H , other than G = G ′ ∪ i = 1 k G i and H = H ′ ∪ i = 1 k H i where, for i = 1 , ... , k , G i and H i are isomorphic to K 3 or S 1 , 3 and G ′ ≃ H ′ , we prove that their skeleton matching polytopes, G (M (G)) and G (M (H)) , are isomorphic graphs if and only if G and H are also isomorphic. [ABSTRACT FROM AUTHOR]

Hypercubes and their special subgraphs, Fibonacci cubes, have been proposed as basic models for interconnection networks. By the recursive nature of Fibonacci cubes, they contain many smaller dimensional hypercubes as subgraphs. In this work, we consider the boundary enumerator polynomial of the k -dimensional hypercubes in Fibonacci cubes of dimension n. We obtain recursive relations satisfied by these polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Pell graphs , a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees. [ABSTRACT FROM AUTHOR]

A 1-factorization M = { M 1 , M 2 , ... , M n } of a graph G is called perfect if the union of any pair of 1-factors M i , M j with i ≠ j is a Hamilton cycle. It is called k -semi-perfect if the union of any pair of 1-factors M i , M j with 1 ≤ i ≤ k and k + 1 ≤ j ≤ n is a Hamilton cycle. We consider 1-factorizations of the discrete cube Q d. There is no perfect 1-factorization of Q d , but it was previously shown that there is a 1-semi-perfect 1-factorization of Q d for all d. Our main result is to prove that there is a k -semi-perfect 1-factorization of Q d for all k and all d , except for one possible exception when k = 3 and d = 6. This is, in some sense, best possible. We conclude with some questions concerning other generalizations of perfect 1-factorizations. [ABSTRACT FROM AUTHOR]

Abstract Kreweras conjectured that every perfect matching of a hypercube Q n for n ≥ 2 can be extended to a hamiltonian cycle of Q n. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of Q n for n ≥ 2 can be extended to two or more hamiltonian cycles of Q n. In this paper, we prove that every perfect matching of Q n for n ≥ 4 can be extended to at least 2 2 n − 4 different hamiltonian cycles of Q n. [ABSTRACT FROM AUTHOR]

Tea is the most consumed manufactured drink in the world. In recent years, various high end analytical techniques such as high-performance liquid chromatography have been used to analyse tea products. However, these techniques require complex sample preparation, are time consuming, expensive and require a skilled analyst to carry out the experiments. Therefore, to support rapid and non-destructive assessment of tea products, the use of near infrared (NIR) (950–1760 nm) hyperspectral imaging (HSI) for classification of six different commercial tea products (oolong, green, yellow, white, black and Pu-erh) is presented. To visualise the HSI data, linear (principal component analysis (PCA) and multidimensional scaling (MDS)) and non-linear (t-distributed stochastic neighbour embedding (t-SNE) and isometric mapping (ISOMAP)) data visualisation methods were compared. t-SNE provided separation of the six commercial tea products into three groups based on the extent of processing: minimally processed, oxidised and fermented. To perform the classification of different tea products, a multi-class error-correcting output code (ECOC) model containing support vector machine (SVM) binary learners was developed. The classification model was further used to predict classes for pixels in the HSI hypercube to obtain the classification maps. The SVM-ECOC model provided a classification accuracy of 97.41 ± 0.16% for the six commercial tea products. The methodology developed provides a means for rapid, non-destructive, in situ testing of tea products, which would be of considerable benefit for process monitoring, quality control, authenticity and adulteration detection. [ABSTRACT FROM AUTHOR]

First we consider families in the hypercube Q n with bounded VC dimension. Frankl raised the problem of estimating the number m ( n , k ) of maximum families of VC dimension k . Alon, Moran and Yehudayoff showed that n ( 1 + o ( 1 ) ) 1 k + 1 n k ≤ m ( n , k ) ≤ n ( 1 + o ( 1 ) ) n k . We close the gap by showing that log m ( n , k ) = ( 1 + o ( 1 ) ) n k log n . We also show how a bound on the number of induced matchings between two adjacent small layers of Q n follows as a corollary. Next, we consider the integrity I ( Q n ) of the hypercube, defined as I ( Q n ) = min { | S | + m ( Q n ∖ S ) : S ⊆ V ( Q n ) } , where m ( H ) denotes the number of vertices in the largest connected component of H . Beineke, Goddard, Hamburger, Kleitman, Lipman and Pippert showed that c 2 n n ≤ I ( Q n ) ≤ C 2 n n log n and suspected that their upper bound is the right value. We prove that the truth lies below the upper bound by showing that I ( Q n ) ≤ C 2 n n log n . [ABSTRACT FROM AUTHOR]

• A hypercube variant fractal cubic network is redefined over the errored definition from [Engineering Science and Technology, an International Journal 18 (2015) 32–41]. • Metric dimension and fault-tolerant metric dimension of fractal cubic networks are determined. • A family of graphs is determined in which the fault-tolerant metric dimension is twice the metric dimension. In network theory, distance parameters are crucial in analyzing structural aspects of the networks under investigation, including their symmetry, connectedness, and tendency to form clusters. To this end, the metric dimension and the fault-tolerant metric dimension are important distance invariants of networks. In this article, we consider fractal cubic networks, a variant of hypercubes. We first correct their definition from the seminal paper [Engineering Science and Technology, an International Journal 18 (2015) 32–41]. After that, we determine their metric dimension and fault-tolerant metric dimension, which is in striking contrast to the situation with hypercubes, where these invariants are intrinsically difficult. [ABSTRACT FROM AUTHOR]

Given a hypercube Q n : = { 0 , 1 } n in R n and k ∈ { 0 , ... , n } , the k -th layer Q k n of Q n denotes the set of all points in Q n whose coordinates contain exactly k many ones. For a fixed t ∈ N and k ∈ { 0 , ... , n } , let P ∈ R [ x 1 , ... , x n ] be a polynomial that has zeroes of multiplicity at least t at all points of Q n ∖ Q k n , and P has zeros of multiplicity exactly t − 1 at all points of Q k n. In this short note, we show that d e g (P) ≥ max ⁡ { k , n − k } + 2 t − 2. Matching the above lower bound we give an explicit construction of a family of hyperplanes H 1 , ... , H m in R n , where m = max ⁡ { k , n − k } + 2 t − 2 , such that every point of Q k n will be covered exactly t − 1 times, and every other point of Q n will be covered at least t times. Note that putting k = 0 and t = 1 , we recover the much celebrated covering result of Alon and Füredi (1993) [1]. Using the above family of hyperplanes we disprove a conjecture of Venkitesh (2022) [23] on exactly covering symmetric subsets of hypercube Q n with hyperplanes. To prove the above results we have introduced a new measure of complexity of a subset of the hypercube called index complexity which we believe will be of independent interest. We also study a new interesting variant of the restricted sumset problem motivated by the ideas behind the proof of the above result. [ABSTRACT FROM AUTHOR]

Dong and Wang (2019) conjectured that the resulting graph of the n -dimensional folded hypercube F Q n by deleting any perfect matching is isomorphic to the hypercube Q n. In this paper, we show that the conjecture holds when n = 2 , 3 , and it is not true for n ≥ 4. [ABSTRACT FROM AUTHOR]

Given an integer 1 ≤  j  <  n , define the ( j )-coloring of a n -dimensional hypercube H n to be the 2-coloring of the edges of H n in which all edges in dimension i , 1 ≤  i  ≤  j , have color 1 and all other edges have color 2. Cheng et al. (2017) determined the number of distinct shortest properly colored paths between a pair of vertices for the (1)-colored hypercubes. It is natural to consider the number for ( j )-coloring, j  ≥ 2. In this note, we determine the number of different shortest proper paths in ( j )-colored hypercubes for arbitrary j . Moreover, we obtain a more general result. [ABSTRACT FROM AUTHOR]

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n ≥ 3 , the semiautomorphisms are exactly the bijections that preserve the set of r -balls for each radius r . Switching of optimal codes of size at most 7 and of codes attaining K ( 8 , 1 ) = 32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes. [ABSTRACT FROM AUTHOR]

We consider the algorithmic problem of generating each subset of [ n ] : = { 1 , 2 , … , n } whose size is in some interval [ k , l ] , 0 ≤ k ≤ l ≤ n , exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions/removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n , k , and l , improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n -dimensional cube Q n induced by all levels [ k , l ] . We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c , k + 1 + c ] , c ∈ { 0 , 1 , … , k } , has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices. [ABSTRACT FROM AUTHOR]

It is useful to consider faulty networks because node faults or link faults may occur in networks. In this paper, we investigate hamiltonian properties of conditional faulty hypercubes. Let F be a set of faulty edges in hypercube Q n with n ≥ 4 and | F | ≤ 3 n − 11 . We prove that there still exists a hamiltonian path in Q n − F joining any two vertices of different partite sets if the following two constraints are satisfied: ( 1 ) the degree of every vertex in Q n − F is at least 2, and ( 2 ) there is at most one vertex with degree 2 in Q n − F . [ABSTRACT FROM AUTHOR]

Let G be a graph and T be a certain connected subgraph of G . The T -structure connectivity κ ( G ; T ) (resp. T -substructure connectivity κ s ( G ; T ) ) of G is the minimum number of a set of subgraphs F = { T 1 , T 2 , . . . , T m } (resp. F = { T 1 ′ , T 2 ′ , . . . , T m ′ } ) such that T i is isomorphic to T (resp. T i ′ is a connected subgraph of T ) for every 1 ≤ i ≤ m , and F 's removal will disconnect G . Let Q n and F Q n denote the n -dimensional hypercube and folded hypercube, respectively. In [12] , the κ ( Q n ; T ) and κ s ( Q n ; T ) were determined for T ∈ { K 1 , 1 , K 1 , 2 , K 1 , 3 , C 4 } . In this paper, we generalize the above results by determining κ ( Q n ; T ) and κ s ( Q n ; T ) for T ∈ { P k , C 2 k , K 1 , 4 } where 3 ≤ k ≤ n . We also determine κ ( F Q n ; T ) and κ s ( F Q n ; T ) for T ∈ { P k , C 2 k , K 1 , 3 } where n ≥ 7 and 2 ≤ k ≤ n . [ABSTRACT FROM AUTHOR]

An edge-colored path is called properly colored if no two consecutive edges have the same color. An edge-colored graph is called properly connected if, between every pair of vertices, there is a properly colored path. Moreover, the proper distance between vertices u and v is the length of the shortest properly colored path from u to v . Given a particular class of properly connected colorings of the hypercube, we consider the proper distance between pairs of vertices in the hypercube. [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 Λ = (V (Λ) , E (Λ)) be a graph. The 2- token graph F 2 (Λ) of Λ is with vertex set all the 2-subsets of V (Λ) , a pair of 2-subsets are adjacent if the symmetric difference is exactly in E (Λ). In this paper, it is proved that Z 2 n − 1 ⋊ Aut (Λ) ≲ Aut (F 2 (Λ)) , where Λ is a Cartesian product of n prime graphs. Then it is shown that the equality may happen by proving that Aut (F 2 (Q n)) ≅ Z 2 n − 1 ⋊ Aut (Q n) , where Q n is the n -dimensional hypercube with n ≥ 3. This also provides some partial answers to [25, Problem 1.3]. [ABSTRACT FROM AUTHOR]

An open packing in a graph G is a set S of vertices in G such that no two vertices in S have a common neighbor in G. The injective chromatic number χ i (G) of G is the smallest number of colors assigned to vertices of G such that each color class is an open packing. Alternatively, the injective chromatic number of G is the chromatic number of the two-step graph of G , which is the graph with the same vertex set as G in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that χ i (G) ≥ 1 2 + 1 4 + 2 m − n ρ o holds for any connected graph G of order n ≥ 2 , size m , and the open packing number ρ o , and characterize the class of graphs attaining the bound. Regarding the well known bound χ i (G) ≥ Δ (G) , we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which χ i (G) equals the cardinality of a largest clique of the two-step graph of G. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property. [ABSTRACT FROM AUTHOR]

Forecast downscaling for accurate nearshore wave conditions is important for a range of marine and coastal users. However, it is complex and high-resolution forecasting methods are computationally intensive, especially when being applied at scale. Identifying methods of downscaling to a high-resolution with accuracy and increased computational efficiency is desired. The prediction of wave parameters using machine learning techniques is becoming increasingly popular, potentially offering more computational efficiency. Other computationally efficient techniques also exist such as the Hybrid Downscale Technique and lookup table approaches. This paper compares three data-driven methods for downscaling offshore wave conditions to a typical computationally intensive process-based approach. A typical calibrated process-based wave model was used to create a catalogue of data from which to develop data-driven models. The comparison was also extended to include the use of wave parameter observations. Each of the data-driven methods showed comparable or improved numerical performance to the process driven technique particularly for the H s parameter (with an up to 16% improvement in Root Mean Squared Error over the process based model). Both data-driven approaches were considerably more computationally efficient, between eleven and seven thousand times faster than the process-based model. However, limitations were identified that should be considered when applying data-driven approaches for predicting wave parameters, such as availability and consistency of data, and the ability of simple parameters to represent complex sea states. • Methods to more efficiently downscale ocean conditions to the coast are presented. • Of the approaches compared the Neural Network offered the most improvement overall. • Quantity and quality of data should be considered when using these techniques. [ABSTRACT FROM AUTHOR]

The r - neighbour bootstrap process on a graph G starts with an initial set A 0 of “infected” vertices and, at each step of the process, a healthy vertex becomes infected if it has at least r infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of G eventually becomes infected, then we say that A 0 percolates . We prove a conjecture of Balogh and Bollobás which says that, for fixed r and large d , every percolating set in the d -dimensional hypercube has cardinality at least 1 + o ( 1 ) r ( d r r − 1 ) . We also prove an analogous result for multidimensionalrectangular grids. Our proofs exploit a connection between bootstrap percolation and a related process, known as weak saturation . In addition, we improve the best known upper bound for the minimum size of a percolating set in the hypercube. In particular, when r = 3, we prove that the minimum cardinality of a percolating set in the d -dimensional hypercube is exactly ⌈ d ( d + 3 ) 6 ⌉ + 1 for all d ≥ 3 . [ABSTRACT FROM AUTHOR]