[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

On words that are concise in residually finite groups

A group-word w$w$ is called concise if whenever the set of w$w$-values in a group G$G$ is finite it always follows that the verbal subgroup w(G)$w\left(G\right)$ is finite. More generally, a word w$w$ is said to be concise in a class of groups X$X$ if whenever the set of w$w$-values is finite for a group G∈X$G\in X$, it always follows that w(G)$w\left(G\right)$ is finite. P. Hall asked whether every word is concise. Due to Ivanov the answer to this problem is known to be negative. Dan Segal asked whether every word is concise in the class of residually finite groups. In this direction we prove that if w$w$ is a multilinear commutator and q$q$ is a prime-power, then the word w^q$w^q$ is indeed concise in the class of residually finite groups. Further, we show that in the case where w=_γk$w={\gamma }_k$ the word w^q$w^q$ is boundedly concise in the class of residually finite groups. It remains unknown whether the word w^q$w^q$ is actually concise in the class of all groups.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

Frobenius groups and retract rationality

Let k$k$ be any field, G$G$ be a finite group acting on the rational function field k(_xg:g∈G)$k(x_g:g\in G)$ by h⋅_xg=_xhg$h\cdot x_g=x_{hg}$ for any h,g∈G$h,g\in G$. Define k(G)=k(_xg:g∈G)^G$k\left(G\right)=k{(x_g:g\in G)}^G$. Noether’s problem asks whether k(G)$k\left(G\right)$ is rational (= purely transcendental) over k$k$. A weaker notion, retract rationality introduced by Saltman, is also very useful for the study of Noether’s problem. We prove that, if G$G$ is a Frobenius group with abelian Frobenius kernel, then k(G)$k\left(G\right)$ is retract k$k$-rational for any field k$k$ satisfying some mild conditions. As an application, we show that, for any algebraic number field k$k$, for any Frobenius group G$G$ with Frobenius complement isomorphic to S_L2(_F5)$S{L}_2\left({\mathbb{F}}_5\right)$, there is a Galois extension field K$K$ over k$k$ whose Galois group is isomorphic to G$G$, i.e. the inverse Galois problem is valid for the pair (G,k)$(G,k)$. The same result is true for any non-solvable Frobenius group if k(_ζ8)$k\left({\zeta }_8\right)$ is a cyclic extension of k$k$.     

Modules satisfying the weak Nakayama property

Let R$R$ be a commutative ring with identity. We will say that an R$R$-module M$M$ satisfies the weak Nakayama property, if IM=M$IM=M$, where I$I$ is an ideal of R$R$, implies that for any x∈M$x\in M$ there exists a∈I$a\in I$ such that (a−1)x=0$(a-1)x=0$. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R$R$ is a local ring, then R$R$ is a Max ring if and only if J(R)$J\left(R\right)$, the Jacobson radical of R$R$, is T$T$-nilpotent if and only if every R$R$-module satisfies the weak Nakayama property.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

The Laplacian polynomial and Kirchhoff index of graphs derived from regular graphs

Let R(G)$R\left(G\right)$ be the graph obtained from G$G$ by adding a new vertex corresponding to each edge of G$G$ and by joining each new vertex to the end vertices of the corresponding edge, and Q(G)$Q\left(G\right)$ be the graph obtained from G$G$ by inserting a new vertex into every edge of G$G$ and by joining by edges those pairs of these new vertices which lie on adjacent edges of G$G$. In this paper, we determine the Laplacian polynomials of R(G)$R\left(G\right)$ and Q(G)$Q\left(G\right)$ of a regular graph G$G$; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs.     

Large deviations of infinite intersections of events in Gaussian processes

Consider events of the form {_Zs≥ζ(s),s∈S}$\{Z_s\ge \zeta \left(s\right),s\in S\}$, where Z$Z$ is a continuous Gaussian process with stationary increments, ζ$\zeta$ is a function that belongs to the reproducing kernel Hilbert space R$R$ of process Z$Z$, and S⊂R$S\subset \mathbb{R}$ is compact. The main problem considered in this paper is identifying the function β^∗∈R${\beta }^{\ast }\in R$ satisfying β^∗(s)≥ζ(s)${\beta }^{\ast }\left(s\right)\ge \zeta \left(s\right)$ on S$S$ and having minimal R$R$-norm. The smoothness (mean square differentiability) of Z$Z$ turns out to have a crucial impact on the structure of the solution. As examples, we obtain the explicit solutions when ζ(s)=s$\zeta \left(s\right)=s$ for s∈[0,1]$s\in [0,1]$ and Z$Z$ is either a fractional Brownian motion or an integrated Ornstein–Uhlenbeck process.     

Crossing number additivity over edge cuts

Consider a graph G$G$ with a minimal edge cut F$F$ and let _G1$G_1$, _G2$G_2$ be the two (augmented) components of G−F$G-F$. A long-open question asks under which conditions the crossing number of G$G$ is (greater than or) equal to the sum of the crossing numbers of _G1$G_1$ and _G2$G_2$—which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|∈{0,1,2}$\left|F\right|\in \{0,1,2\}$ and that there exist graphs violating this property with |F|≥4$\left|F\right|\ge 4$. In this paper, we show that crossing number is additive for |F|=3$\left|F\right|=3$, thus closing the final gap in the question.     

Resolving sets for Johnson and Kneser graphs

A set of vertices S$S$ in a graph G$G$ is a resolving set   for G$G$ if, for any two vertices u,v$u,v$, there exists x∈S$x\in S$ such that the distances d(u,x)≠d(v,x)$d(u,x)\ne d(v,x)$. In this paper, we consider the Johnson graphs J(n,k)$J(n,k)$ and Kneser graphs K(n,k)$K(n,k)$, and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

Factorization properties of paratopological groups

In this article we continue the study of R$\mathbb{R}$-factorizability in paratopological groups. It is shown that: (1) all concepts of R$\mathbb{R}$-factorizability in paratopological groups coincide; (2) a Tychonoff paratopological group G   is R$\mathbb{R}$-factorizable if and only if it is totally ω  -narrow and has property ω-QU$\omega \text{-}\mathit{QU}$; (3) every subgroup of a _T1$T_1$ paratopological group G   is R$\mathbb{R}$-factorizable provided that the topological group G^?$G^{?}$ associated to G is a Lindelöf Σ-space, i.e., G is a totally Lindelöf Σ-space  ; (4) if Π=_∏i∈IGi$\Pi ={\prod }_{i\in I}{G}_i$ is a product of _T1$T_1$ paratopological groups which are totally Lindelöf Σ-spaces, then each dense subgroup of Π   is R$\mathbb{R}$-factorizable. These results answer in the affirmative several questions posed earlier by M. Sanchis and M. Tkachenko and by S. Lin and L.-H. Xie.     

Monotonicity of the reflected Bessel transition density on the diagonal

For α∈R$\alpha \in \mathbb{R}$, let p^R(t,x,x)$p^R(t,x,x)$ denote the diagonal of the transition density of the α$\alpha$-Bessel process in (0,1]$(0,1]$, killed at 0 and reflected at 1. As a function of x$x$, if either α≥3$\alpha \ge 3$ or α=1$\alpha =1$, then for t>0$t>0$, the diagonal is nondecreasing. This monotonicity property fails if 1≠α<3$1\ne \alpha <3$.     

Description of extended eigenvalues and extended eigenvectors of integration operators on the Wiener algebra

In the present paper we consider the Volterra integration operator V   on the Wiener algebra W(D)$W(\mathbb{D})$ of analytic functions on the unit disc D$\mathbb{D}$ of the complex plane C$\mathbb{C}$. A complex number λ$\lambda$ is called an extended eigenvalue of V if there exists a nonzero operator A   satisfying the equation AV=λVA$\mathit{AV}=\lambda \mathit{VA}$. We prove that the set of all extended eigenvalues of V   is precisely the set C?{0}$\mathbb{C}?\{0\}$, and describe in terms of Duhamel operators and composition operators the set of corresponding extended eigenvectors of V$V$. The similar result for some weighted shift operator on _?p${?}_p$ spaces is also obtained.