[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$.     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

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.     

Disjoint cycles with different length in 4-arc-dominated digraphs

A d$d$-arc-dominated digraph is a digraph D$D$ of minimum out-degree d$d$ such that for every arc (x,y)$(x,y)$ of D$D$, there exists a vertex u$u$ of D$D$ of out-degree d$d$ such that (u,x)$(u,x)$ and (u,y)$(u,y)$ are arcs of D$D$. Henning and Yeo [Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694] conjectured that a digraph with minimum out-degree at least four contains two vertex-disjoint cycles of different length. In this paper, we verify this conjecture for 4-arc-dominated digraphs.     

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.     

A note on distance-regular graphs with a small number of vertices compared to the valency

In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2$\alpha >2$, there are finitely many distance-regular graphs Γ$\Gamma$ with valency k$k$, diameter D≥3$D\ge 3$ and v$v$ vertices satisfying v≤αk$v\le \alpha k$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3$k\ge 3$, diameter D≥3$D\ge 3$ and _c2≥εk$c_2\ge \epsilon k$ for a given 0<ε<1$0<\epsilon <1$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite).     

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.     

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.     

On coloring box graphs

We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n$n$-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n$n$-space has an admissible coloring with n+1$n+1$ colors. We show that for box graphs in n$n$-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}$\{1,2,3\}$, then the box graph is 3$3$-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 3$3$-colorable.     

Bounds on the connected domination number of a graph

A subset S$S$ of vertices in a graph G=(V,E)$G=(V,E)$ is a connected dominating set of G$G$ if every vertex of V?S$V?S$ is adjacent to a vertex in S$S$ and the subgraph induced by S$S$ is connected. The minimum cardinality of a connected dominating set of G$G$ is the connected domination number _γc(G)${\gamma }_c\left(G\right)$. The girth g(G)$g\left(G\right)$ is the length of a shortest cycle in G$G$. We show that if G$G$ is a connected graph that contains at least one cycle, then _γc(G)≥g(G)−2${\gamma }_c\left(G\right)\ge g\left(G\right)-2$, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.     

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$.     

Unilateral small deviations of processes related to the fractional Brownian motion

Let x(s)$x\left(s\right)$, s∈R^d$s\in R^d$ be a Gaussian self-similar random process of index H$H$. We consider the problem of log-asymptotics for the probability _pT$p_T$ that x(s)$x\left(s\right)$, x(0)=0$x\left(0\right)=0$ does not exceed a fixed level in a star-shaped expanding domain T⋅Δ$T\cdot \Delta$ as T→∞$T\to \infty$. We solve the problem of the existence of the limit, θ?lim(−log_pT)/(logT)^D$\theta ?lim(-log{p}_T)/{(logT)}^D$, T→∞$T\to \infty$, for the fractional Brownian sheet x(s)$x\left(s\right)$, s∈[0,T]²$s\in {[0,T]}^2$ when D=2$D=2$, and we estimate θ$\theta$ for the integrated fractional Brownian motion when D=1$D=1$.     

Parametric inference for discretely observed multidimensional diffusions with small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(α,_Xt)$b(\alpha ,X_t)$ and diffusion coefficient ?σ(β,_Xt)$?\sigma (\beta ,X_t)$. The diffusion sample path is discretely observed at times _tk=kΔ$t_k=k\Delta$ for k=1…n$k=1\dots n$ on a fixed interval [0,T]$[0,T]$. We study minimum contrast estimators derived from the Gaussian process approximating X$X$ for small ?$?$. We obtain consistent and asymptotically normal estimators of α$\alpha$ for fixed Δ$\Delta$ and ?→0$?\to 0$ and of (α,β)$(\alpha ,\beta )$ for Δ→0$\Delta \to 0$ and ?→0$?\to 0$ without any condition linking ?$?$ and Δ$\Delta$. We compare the estimators obtained with various methods and for various magnitudes of Δ$\Delta$ and ?$?$ based on simulation studies. Finally, we investigate the interest of using such methods in an epidemiological framework.