The relationship between k-forcing and k-power domination

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of $k$-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, $k$-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of $k$-forcing and $k$-power domination, providing a new approach to analyze both processes. We give a relationship between the $k$-forcing and the $k$-power domination numbers of a graph that bounds one in terms of the other. We also obtain results using the contraction of subgraphs that allow the parallel computation of $k$-forcing and $k$-power dominating sets.     

Identifying defective sets using queries of small size

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $Y$ of $X$, which is known to have exactly $d$ elements, by means of testing, for as few as possible subsets $A$ of $X$, whether $A$ intersects $Y$ or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number $k$. Our main results are nearly tight bounds on the minimum number of tests necessary when $d$ and $k$ are fixed and $n$ is large enough.     

On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

Nonlinear Fourier transforms for the sine-Gordon equation in the quarter plane

Using the Unified Transform, also known as the Fokas method, the solution of the sine-Gordon equation in the quarter plane can be expressed in terms of the solution of a matrix Riemann–Hilbert problem whose definition involves four spectral functions $a,b,A,B$. The functions $a(k)$ and $b(k)$ are defined via a nonlinear Fourier transform of the initial data, whereas $A(k)$ and $B(k)$ are defined via a nonlinear Fourier transform of the boundary values. In this paper, we provide an extensive study of these nonlinear Fourier transforms and the associated eigenfunctions under weak regularity and decay assumptions on the initial and boundary values. The results can be used to determine the long-time asymptotics of the sine-Gordon quarter-plane solution via nonlinear steepest descent techniques.     

Bifurcation theory for finitely smooth planar autonomous differential systems

In this paper we establish bifurcation theory of limit cycles for planar $C^k$ smooth autonomous differential systems, with $k\in \mathbb{N}$. The key point is to study the smoothness of bifurcation functions which are basic and important tool on the study of Hopf bifurcation at a fine focus or a center, and of Poincaré bifurcation in a period annulus. We especially study the smoothness of the first order Melnikov function in degenerate Hopf bifurcation at an elementary center. As we know, the smoothness problem was solved for analytic and $C^{\infty }$ differential systems, but it was not tackled for finitely smooth differential systems. Here, we present their optimal regularity of these bifurcation functions and their asymptotic expressions in the finite smooth case.     

Distribution of extremal order statistics from large subsets of concomitants

From a random sample of size $n$ from an absolutely continuous bivariate population $(X,Y)$ we consider two complementary (upper and lower) subsets of $Y$-values formed by a sorting on the basis of the corresponding $X$-values. We derive the finite-sample and asymptotic joint distributions of the extreme order statistics of these $Y$ subsets assuming that the subset sizes remain proportional to $n$ as $n\to \infty$. We illustrate the use of our results with the bivariate normal example and provide an approximation to the probability of an event of interest in selection problems.     

Cohomology over Fiber products of local rings

Let S and T be local rings with common residue field k, let R be the fiber product $S{\times }_{k}T$, and let M be an S-module. The Poincaré series $P_M^R$ of M has been expressed in terms of $P_M^S$, $P_k^S$ and $P_k^T$ by Kostrikin and Shafarevich, and by Dress and Krämer. Here, an explicit minimal resolution, as well as theorems on the structure of ${\mathrm{Ext}}_R(k,k)$ and ${\mathrm{Ext}}_R(M,k)$ are given that illuminate these equalities. Structure theorems for the cohomology modules of fiber products of modules are also given. As an application of these results, we compute the depth of cohomology modules over a fiber product.     

Computing minimum multiway cuts in hypergraphs

The hypergraph $k$-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least $k$ connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both $k$ and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum $k$-cuts of graphs from greedy packings of spanning trees.     

The perimeter of words

We define $\left[k\right]=\{1,2,\dots ,k\}$ to be a (totally ordered) alphabet on $k$ letters. A word $w$ of length $n$ on the alphabet $\left[k\right]$ is an element of ${\left[k\right]}^n$. A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the $x$-axis) in which the height of the $i$th column equals the size of the $i$th part of the word. Thus these bargraphs have heights which are less than or equal to $k$. We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length $n$ over the alphabet $\left[k\right]$. We also show how the mean and variance can be obtained using a direct counting method.