Compressed sensing (CS) has broken through the traditional Nyquist sampling theory as it is a new technique in signal processing. According to CS theory, compressed sensing makes full use of sparsity so that a sparse signal can be reconstructed from very few measurements. It is well known that the construction of CS matrices is the central problem. In this paper, we provide one kind of deterministic sensing matrix by describing a combinatorial design. Then, we obtain two cases by instantiating the RIP framework with the obtained design, with the latter case being the majorization of the former. Finally, we show that our construction has better properties than DeVore’s construction using polynomials over finite fields.

In this paper, with the help of the residue method, we find some interesting formulas relating residue and ordinary Bell polynomials, \(\hat{B}_{n,k}(x_1,x_2,\ldots)\). Further, we prove identities involving some combinatorial numbers to demonstrate the application of the formulas.

We expand the theory of pebbling to graphs with weighted edges. In a weighted pebbling game, one player distributes a set amount of weight on the edges of a graph and his opponent chooses a target vertex and places a configuration of pebbles on the vertices. Player one wins if, through a series of pebbling moves, he can move at least one pebble to the target. A pebbling move of \(p\) pebbles across an edge with weight \(w\) leaves \(\lfloor pw \rfloor\) pebbles on the next vertex. We find the weighted pebbling numbers of stars, graphs with at least \(2|V|-1\) edges, and trees with given targets. We give an explicit formula for the minimum total weight required on the edges of a length-2 path, solvable with \(p\) pebbles, and exhibit a graph that requires an edge with weight \(1/3\) in order to achieve its weighted pebbling number.

We examine two particular constructions of Costas arrays known as the Taylor variant of the Lempel construction, or the \(T_4\) construction, and the variant of the Golomb construction, or the \(G_4\) construction. We connect these with Fibonacci primitive roots, and show that under the Extended Riemann Hypothesis, the \(T_4\) and \(G_4\) constructions are valid infinitely often.

The authentication codes with arbitration are said to be \(A^2\)-codes. Two constructions of \(A^2\)-codes with secrecy from polynomials over finite fields are constructed to prevent communication systems from attacks which come from the opponent, the transmitter and the receiver. Parameters of the codes and probabilities of successful attacks are also computed. At last, two constructions are compared with a known one. It is important that a source state can’t be recovered from the message without the knowledge of the transmitter’s encoding rule or the receiver’s decoding rule. It must be decoded before verification.

For \(n \geq 1\), we let \(a_n\) count the number of nonempty subsets \(S\) of \(\{1,2,3,\ldots,n\} = [n]\), where the size of \(S\) equals the minimal element of \(S\). Such a subset is called an extraordinary subset of \([n]\), and we find that \(a_n = F_n\), the \(n\)th Fibonacci number. Then, for \(n \geq k \geq 1\), we let \(a(n, k)\) count the number of times the integer \(k\) appears among these \(a_n\) extraordinary subsets of \(n\). Here we have \(a(n, k) = a(n-1, k) + a(n-2, k-1)\), for \(n \geq 3\) and \(n > k \geq 2\). Formulas and properties for \(t_n = \sum_{k=1}^n a(n, k)\) and \(s_n = \sum_{k=1}^n ka(n, k)\) are given for \(n \geq 1\). Finally, for fixed \(n \geq 1\), we find that the sequence \(a(n, k)\) is unimodal and examine the maximum element for the sequence. In this context, the Catalan numbers make an entrance.

The cycle length distribution (CLD) of a graph of order \(n\) is \((c_1, c_2, \ldots, c_n)\), where \(c_i\) is the number of cycles of length \(i\), for \(i = 1, 2, \ldots, n\). For an integer sequence \((a_1, a_2, \ldots, a_n)\), we consider the problem of characterizing those graphs \(G\) with the minimum possible edge number and with \(\text{CLD}(G) = (c_1, c_2, \ldots, c_n)\) such that \(c_i \geq a_i\) for \(i = 1, 2, \ldots, n\). The number of edges in such a graph is denoted by \(g(a_1, a_2, \ldots, a_n)\). In this paper, we give the lower and upper bounds of \(g(0, 0, k, \ldots, k)\) for \(k = 2, 3, 4\).

Two-fold automorphisms (or “TF-isomorphisms”) of graphs are a generalisation of automorphisms. Suppose \(\alpha, \beta\) are two permutations of \(V = V(G)\) such that for any pair \((u,v)\), \(u, v \in V\), \((u,v)\) is an arc of \(G\) if and only if \((\alpha(u), \beta(v))\) is an arc of \(G\). Such a pair of permutations is called a two-fold automorphism of \(G\). These pairs form a group that is called the two-fold automorphism group. Clearly, it contains all the pairs \((\alpha, \alpha)\) where \(\alpha\) is an automorphism of \(G\). The two-fold automorphism group of \(G\) can be larger than \(\text{Aut}(G)\) since it may contain pairs \((\alpha, \beta)\) with \(\alpha \neq \beta\). It is known that when this happens, \(\text{Aut}(G) \times \mathbb{Z}_2\) is strictly contained in \(\text{Aut}(G \times K_2)\). In the literature, when this inclusion is strict, the graph \(G\) is called unstable.

Now let \(\Gamma \leq S_V \times S_V\). A two-fold orbital (or “TF-orbital”) of \(F\) is an orbit of the action \((\alpha, \beta) : (u,v) \mapsto (\alpha(u), \beta(v))\) for \((\alpha, \beta) \in \Gamma\) and \(u,v \in V\). Clearly, \(\Gamma\) is a subgroup of the TF-automorphism group of any of its TF-orbitals. We give a short proof of a characterization of TF-orbitals which are disconnected graphs and prove that a similar characterization of TF-orbitals which are digraphs might not be possible. We shall also show that the TF-rank of \(\Gamma\), that is the number of its TF-orbitals, can be equal to \(1\) and we shall obtain necessary and sufficient conditions on I for this to happen.

We define a new fairness notion on edge-colorings, requiring that the number of vertices in the subgraphs induced by the edges of each color are within one of each other. Given a (not necessarily proper) \( k \)-edge-coloring of a graph \( G \), for each color \( i \in \mathbb{Z}_k \), let \( G[i] \) denote the (not necessarily spanning) subgraph of \( G \) induced by the edges colored \( i \). Let \( \nu_{i}(G) = |V(G[i])| \). Formally, a \( k \)-edge-coloring of a graph \( G \) is said to be vertex-equalized if for each pair of colors \( i, j \in \mathbb{Z}_k \), \( |\nu_{i}(G) – \nu_{j}(G)| \leq 1 \). In this paper, a characterization is found for connected graphs that have vertex-equalized \( k \)-edge-colorings for each \( k \in \{2, 3\} \) (see Corollary 4.1 and Corollary 4.2).

Let \( G = (V, E) \) be a graph. The open neighborhood of a vertex \( v \in V \) is the set \( N(v) = \{u \mid uv \in E\} \) and the closed neighborhood of \( v \) is the set \( N[v] = N(v) \cup \{v\} \). The open neighborhood of a set \( S \) of vertices is the set \( N(S) = \bigcup_{v \in S} N(v) \), while the closed neighborhood of a set \( S \) is the set \( N[S] = \bigcup_{v \in S} N[v] \). A set \( S \subset V \) dominates a set \( T \subset V \) if \( T \subseteq N[S] \), written \( S \rightarrow T \). A set \( S \subset V \) is a dominating set if \( N[S] = V \); and is a minimal dominating set if it is a dominating set, but no proper subset of \( S \) is also a dominating set; and is a \( \gamma \)-set if it is a dominating set of minimum cardinality. In this paper, we consider the family \( \mathcal{D} \) of all dominating sets of a graph \( G \), the family \( \mathcal{MD} \) of all minimal dominating sets of a graph \( G \), and the family \( \Gamma \) of all \( \gamma \)-sets of a graph \( G \). The study of these three families of sets provides new characterizations of the distance-2 domination number, the upper domination number, and the upper irredundance number in graphs.