Search

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G = (V , E) , a dominating set of G is a subset S ⊆ V such that every vertex in V ∖ S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G , if for every vertex u ∈ S ¯ = V ∖ S , there exists a v ∈ S such that N (v) ∩ S ¯ = N (v) ∖ S = { u }. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP -hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r -clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set { 4 , n , 2 n , 5 n 2 − 10 n 8 } based on n mod 4. [ABSTRACT FROM AUTHOR]

Given a non-decreasing sequence S = (s 1 , s 2 , ... , s k) of positive integers, an S -packing coloring of a graph G is a partition of the vertex set of G into k subsets { V 1 , V 2 , ... , V k } such that for each 1 ≤ i ≤ k , the distance between any two distinct vertices u and v in V i is at least s i + 1. In this paper, we study the problem of S -packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is (1 , 1 , 2 , 3) -packing colorable. In addition, we prove that such graphs are (1 , 2 , 2 , 2 , 2 , 2) -packing colorable. [ABSTRACT FROM AUTHOR]

A matching in a graph is a set of pairwise nonadjacent edges. A maximum matching is a matching which covers as many vertices as possible. In this paper, using the Gallai–Edmonds Structure Theorem, we obtain a characterization of graphs each of whose edges belongs to at most one maximum matching. [ABSTRACT FROM AUTHOR]

In computational and theoretical chemistry, the eccentricity matrix of graph has widely applications due to its effect of eccentricity in molecular graph. Since a molecular structure is modeled by hypergraph which has a higher accuracy than by graph, it is also interesting to study eccentricity matrix of hypergraph. The eccentricity spectral radius of H is the spectral radius of its eccentricity matrix. In this paper, some properties on eccentricity spectral radius of hypergraphs are obtained and some extremal structure of hypertrees are characterized. [ABSTRACT FROM AUTHOR]

Boolean functions used in symmetric-key encryption should have high higher-order nonlinearity to resist several known cryptographic attacks, such as algebraic attacks and low-degree approximation attacks. The higher-order nonlinearity also plays an important role in coding theory and theoretical computer science, since it relates to the covering radius of Reed–Muller codes and the Gowers norm, respectively. It is well-known that bent functions have the highest nonlinearity in an even number of variables and thus they possess the best ability to withstand fast correlation attacks and best affine approximation attacks. However, there is currently limited knowledge regarding the higher-order nonlinearity of bent functions because computing the higher-order nonlinearity, or even providing tight lower bounds, is an extremely hard task. In 1974, Dillon proposed two well-known classes of bent functions based on partial spread (in brief, PS), called PS − and PS + , respectively. He also exhibited a subclass of bent functions in PS − , known as partial spread affine plane(PS a p for short). In this paper, we provide a lower bound on the third-order nonlinearity of the simplest PS a p bent functions in n variables, where n ≥ 6 is even, by calculating the nonlinearities of all second-order derivatives of this kind of bent functions. Compared to the two known lower bounds on the third-order nonlinearity given by Carlet and Tang et al. respectively, our lower bound is much better than these two ones. [ABSTRACT FROM AUTHOR]

A dominating broadcast of a graph G is a function f : V (G) → { 0 , 1 , 2 , ... , diam (G) } such that f (v) ⩽ e (v) for all v ∈ V (G) , where e (v) is the eccentricity of v , and for every u ∈ V (G) , there exists a vertex v with f (v) ⩾ 1 and d (u , v) ⩽ f (v). The cost of f is ∑ v ∈ V (G) f (v). The minimum cost over all the dominating broadcasts of G is called the broadcast domination number γ b (G) of G. In this paper, we give new upper and lower bounds for γ b (G). We show that both the bounds are tight. Also, we improve the upper bound for a subclass of regular graphs. Further, we explore the broadcast domination numbers of generalized Petersen graphs and a subclass of circulant graphs. [ABSTRACT FROM AUTHOR]

A set of n drones with limited communication range is deployed to monitor a terrain partitioned into n pairwise disjoint and closed convex trajectories, one per drone. There is exactly one communication link between two trajectories if they are close enough, and drones can communicate provided they visit the link at the same time. If each robot flies around an assigned area and shares information with the neighbors periodically the system is said to be synchronized. Over time, one or more drones may fail and the ability to survey, communicate, and stay connected decreases, thus the robustness against drone failure becomes crucial. In this paper we study various problems related to the proper functioning of a synchronized system under drone failure. First, we provide efficient algorithms, both centralized and decentralized, for determining the connected components induced by the set of surviving drones. Second, we study coverage, isolation, and connectivity under a probabilistic failure model and show that, in the case of grids, the system is quite robust in the sense that it can tolerate a large probability of failure before drones fail to completely cover the terrain, become isolated, or the system loses full connectivity. [ABSTRACT FROM AUTHOR]

The topological structure of a recursive interconnection network can be modeled by an n -dimensional graph G n. A faulty vertex set (resp. edge set) of G n is called a t -embedded vertex (resp. edge) cut if the remaining network is disconnected and each vertex in the residual network is in a copy of fault-free t -dimensional graph G t. The t -embedded vertex connectivity ζ t (G n) (resp. the t -embedded edge connectivity η t (G n)) is defined as the minimum cardinality over all t -embedded vertex (resp. edge) cuts of G n. The m -ary n -dimensional hypercube G (n , m) has an elegant recursive structure and is also a generalized variant of the classical hypercube. This paper studies the reliability of the G (n , m) and generalizes some known results in ternary n -cubes. Specifically, we prove that ζ t (G (n , m)) = (m − 1) (n − t) m t for t ≤ n − 2 and η t (G (n , m)) = (m − 1) (n − t) m t for t ≤ n − 1. [ABSTRACT FROM AUTHOR]

In this paper, we study the distribution of parallelograms and rhombi in a given set in the plane over arbitrary finite fields F q 2. As an application, we improve the recent result due to Fitzpatrick, Iosevich, McDonald, and Wyman on the Vapnik–Chervonenkis dimension of the induced distance graph. [ABSTRACT FROM AUTHOR]