查看更多>>摘要：? 2021 Elsevier B.V.Boolean functions with five-valued Walsh spectra (shortened as five-valued functions) and semi-bent functions are two classes of Boolean functions with high nonlinearity. They have useful applications in cryptography and communications. In this paper, we first present the construction of resilient five-valued functions by modifying the support of Rothaus's bent function. And then, we give the method of constructing resilient semi-bent functions. At the same time, the number of the newly constructed resilient semi-bent functions is determined. Lastly, we give the construction of resilient semi-bent functions with maximal algebraic degree.
查看更多>>摘要：? 2021 Elsevier B.V.Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in both pure and applied mathematics. In particular, the security of the so-called multivariate public-key cryptosystems, such as HFE of Patarin and UOV of Kipnis et al., is based on the postulated hardness of solving quadratic polynomial systems over a finite field. Lokshtanov et al. (2017) were the first to introduce a probabilistic algorithm that, in the worst-case, solves a Boolean polynomial system in time O?(2δn), for some δ∈(0,1) depending only on the degree of the system, thus beating the brute-force complexity O?(2n). Later, Bj?rklund et al. (2019) and then Dinur (2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient δ. We survey the theory behind these probabilistic algorithms, and we illustrate the results that we obtained by implementing them in C. In particular, for random quadratic Boolean systems, we estimate the practical complexities of the algorithms and their probabilities of success as their parameters change.
查看更多>>摘要：? 2021 Elsevier B.V.The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for M?bius ladder graphs. Prior to this work, in all cases where the secure domination number has been determined, the proof has either been trivial, or has been derived from lower bounds established by considering different forms of domination. However, the latter mode of proof is not applicable for most graphs, including those considered here. Hence, this work represents the first attempt to determine secure domination numbers via the properties of secure domination itself, and it is expected that these methods may be used to determine further results in the future.
查看更多>>摘要：? 2021 Elsevier B.V.Fault diagnosis plays an important role in maintaining the reliability of interconnection networks. Let v be a given node in an interconnection network G.v is conditionally locally t-diagnosable in G if the fault or fault-free status of node v can be identified correctly when the number of faults presented does not exceed t and every node has at least one healthy neighboring node. The conditional local diagnosis can be regarded as a local strategy toward the conditional diagnosis of networks, which puts more emphasis on identifying the status of a particular processor. In this paper, we first show a sufficient condition for a regular network to be conditionally locally t-diagnosable at a given node under the MM* model. As its applications, we derive the conditional diagnosability of hierarchical star network HSn etc. We also design an algorithm under the MM* model to identify the fault or fault-free status of a given processor in a regular network. According to our result, an α-regular network with a balanced three-tiered tree T(v;α,α?1,β) rooted at v is conditionally locally (2α+β?3)-diagnosable at node v and the time complexity of our algorithm to diagnose v is o(α2β2). As an application, we show our algorithm can identify the status of each node of star graph Sn if the fault node number does not exceed 3n?9. Compared with existing algorithms, our algorithm allows more faults to arise in a network.
查看更多>>摘要：? 2021 Elsevier B.V.Given a connected graph G=(V,E) and a length function ?:E→R we let dv,w denote the shortest distance between vertex v and vertex w. A t-spanner is a subset E′?E such that if dv,w′ denotes shortest distances in the subgraph G′=(V,E′) then dv,w′≤tdv,w for all v,w∈V. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p. a 1-spanner that uses [Formula presented] edges and that this is best possible. In particular, our result applies to the random graphs Gn,p for np?logn.
查看更多>>摘要：? 2021 Elsevier B.V.Exponential runtimes of algorithms for values for games with transferable utility like the Shapley value are one of the biggest obstacles in the practical application of otherwise axiomatically convincing solution concepts of cooperative game theory. We investigate to what extent the hierarchical structure of a level structure improves runtimes compared to an unstructured player set. Representatively, we examine the Shapley levels value, the nested Shapley levels value, and, as a new value for level structures, the nested Owen levels value. For these values, we provide polynomial-time algorithms (under normal conditions) which are exact and therefore not approximation algorithms. Moreover, we introduce relevant coalition functions where all coalitions that are not relevant for the payoff calculation have a Harsanyi dividend of zero. Our results shed new light on the computation of values of the Harsanyi set as the Shapley value and many values from extensions of this set.
查看更多>>摘要：? 2021 Elsevier B.V.Metric dimension is a graph parameter motivated by problems in robot navigation, drug design, and image processing. In this paper, we answer several open extremal problems on metric dimension and pattern avoidance in graphs from Geneson (2020). Specifically, we construct a new family of graphs that allows us to determine the maximum possible degree of a graph of metric dimension at most k, the maximum possible degeneracy of a graph of metric dimension at most k, the maximum possible chromatic number of a graph of metric dimension at most k, and the maximum n for which there exists a graph of metric dimension at most k that contains Kn,n. We also investigate a variant of metric dimension called edge metric dimension and solve another problem from the same paper for n sufficiently large by showing that the edge metric dimension of Pnd is d for n≥dd?1. In addition, we use a probabilistic argument to make progress on another open problem from the same paper by showing that the maximum possible clique number of a graph of edge metric dimension at most k is 2Θ(k). We also make progress on a problem from Zubrilina (2018) by finding a family of new triples (x,y,n) for which there exists a graph of metric dimension x, edge metric dimension y, and order n. In particular, we show that for each integer k>0, there exist graphs G with metric dimension k, edge metric dimension 3k(1?o(1)), and order 3k(1+o(1)).
查看更多>>摘要：? 2021 Elsevier B.V.We define an alphabetic point in a restricted growth function as a point in the word which is larger than all preceding points and smaller than all following ones. We find the trivariate generating function for restricted growth functions which tracks the number of alphabetic points as the main statistic. The generating function is then used to find the total number of alphabetic points and thereafter, a formula for the number of restricted growth functions having only one alphabetic point (i.e., those with only the initial point 1 being alphabetic). Finally, the asymptotics for those restricted growth functions having exactly m alphabetic points as well as those having only one alphabetic point are found as the size of the word n→∞.
查看更多>>摘要：? 2021 The Author(s)In the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic one, are related: our new parameter is an upper bound for the game chromatic number.
查看更多>>摘要：? 2021 Elsevier B.V.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.
NSTL
Elsevier