Toughness and Matching Extension in {\mathcal{P}_3}-Dominated Graphs

Let G be a connected graph. For ${x,y\in V(G)}$ with d(x, y) = 2, we define ${J(x,y)= \{u \in N(x)\cap N(y)\mid N[u] \subseteq N[x] \,{\cup}\,N[y] \}}$ and ${J'(x,y)= \{u \in N(x) \cap N(y)\,{\mid}\,{\rm if}\ v \in N(u){\setminus}(N[x] \,{\cup}\, N[y])\ {\rm then}\ N[x] \,{\cup}\, N[y]\,{\cup}\,N[u]{\setminus}\{x,y\}\subseteq N[v]\}}$ . A graph G is quasi-claw-free if ${J(x,y) \not= \emptyset}$ for each pair (x, y) of vertices at distance 2 in G. Broersma and Vumar (in Math Meth Oper Res. doi:10.1007/s00186-008-0260-7) introduced ${\mathcal{P}_{3}}$ -dominated graphs defined as ${J(x,y)\,{\cup}\, J'(x,y)\not= \emptyset}$ for each ${x,y \in V(G)}$ with d(x, y) = 2. This class properly contains that of quasi-claw-free graphs, and hence that of claw-free graphs. In this note, we prove that a 2-connected ${\mathcal{P}_3}$ -dominated graph is 1-tough, with two exceptions: K _2,3 and K _1,1,3, and prove that every even connected ${\mathcal{P}_3}$ -dominated graph ${G\ncong K_{1,3}}$ has a perfect matching. Moreover, we show that every even (2p + 1)-connected ${\mathcal{P}_3}$ -dominated graph is p-extendable. This result follows from a stronger result concerning factor-criticality of ${\mathcal{P}_3}$ -dominated graphs.     

The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least ${\frac{1}{2}|G|}$ vertices of degree 5.     

Group Connectivity of Bridged Graphs

Let G be a 2-edge-connected simple graph, and let A denote an abelian group with the identity element 0. If a graph G ^* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. A graph G is bridged if every cycle of length at least 4 has two vertices x, y such that d _G (x, y) < d _C (x, y). In this paper, we investigate the group connectivity number Λ _g (G) = min{n: G is A-connected for every abelian group with |A| ≥ n} for bridged graphs. Our results extend the early theorems for chordal graphs by Lai (Graphs Comb 16:165–176, 2000) and Chen et al. (Ars Comb 88:217–227, 2008).     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

Centralizers of coprime automorphisms of finite groups

Let A be an elementary abelian group of order p ^k with k ≥ 3 acting on a finite p′-group G. The following results are proved. If γ _k-2(C _G (a)) is nilpotent of class at most c for any ${a \in A^{\#}}$ , then γ _k-2(G) is nilpotent and has {c, k, p}-bounded nilpotency class. If, for some integer d such that 2 ^d  + 2 ≤ k, the dth derived group of C _G (a) is nilpotent of class at most c for any ${a \in A^{\#}}$ , then the dth derived group G ^(d) is nilpotent and has {c, k, p}-bounded nilpotency class.     

An Engel condition with skew derivations

Let R be a prime ring and set [x, y]₁ = [x, y] = xy ? yx for ${x,y\in R}$ and inductively [x, y] _k = [[x, y] _k-1, y] for k > 1. We apply the theory of generalized polynomial identities with automorphisms and skew derivations to obtain the following result: If δ is a nonzero σ-derivation of R and L is a noncommutative Lie ideal of R so that [δ(x), x] _k  = 0 for all ${x \in L}$ , where k is a fixed positive integer, then charR = 2 and ${R\subseteq M_{2}(F)}$ for some field F. This result generalizes the case of derivations by Lanski and also the case of automorphisms by Mayne.     

Contractible Small Subgraphs in k-connected Graphs

We prove that if G is highly connected, then either G contains a non-separating connected subgraph of order three or else G contains a small obstruction for the above conclusion. More precisely, we prove that if G is k-connected (with k ≥ 2), then G contains either a connected subgraph of order three whose contraction results in a k-connected graph (i.e., keeps the connectivity) or a subdivision of ${K_4^-}$ whose order is at most 6.     

Neighborhood Unions and Z 3-Connectivity in Graphs

Let G be a 2-edge-connected simple graph on n ≥ 14 vertices, and let A be an abelian group with the identity element 0. If a graph G* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say that G can be A-reduced to G*. In this paper, we prove that if for every ${uv\not\in E(G), |N(u) \cup N(v)| \geq \lceil \frac{2n}{3} \rceil}$ , then G is not Z ₃-connected if and only if G can be Z ₃-reduced to one of ${\{C_3,K_4,K_4^-, L\}}$ , where L is obtained from K ₄ by adding a new vertex which is joined to two vertices of K ₄.     

On restricting Cauchy–Pexider functional equations to submanifolds

Sufficient geometric conditions are given which determine when the Cauchy–Pexider functional equation f(x)g(y) = h(x + y) restricted to x, y lying on a hypersurface in ${\mathbb{R}^d}$ has only solutions which extend uniquely to exponential affine functions ${\mathbb{R}^d \to \mathbb{C}}$ (when f, g, h are assumed to be measurable and non-trivial). The Cauchy–Pexider-type functional equations ${\prod_{j=0}^df_j(x_j)=F(\sum_{j=0}^dx_j)}$ for ${x_0, \ldots,x_d}$ lying on a curve and ${f_1(x_1)f_2(x_2)f_3(x_3)=F(x_1+x_2+x_3)}$ for x ₁, x ₂, x ₃ lying on a hypersurface are also considered.     

Shifted Appell Sequences in Clifford Analysis

The aim of this paper is to present a generalization of the Appell sequences within the framework of Clifford analysis called shifted Appell sequences. It consists of sequences {M _n (x)} _n ≥ 0 of monogenic polynomials satisfying the Appell condition (i.e. the hypercomplex derivative of each polynomial in the sequence equals, up to a multiplicative constant, its preceding term) such that the first term M ₀(x) = P _k (x) is a given but arbitrary monogenic polynomial of degree k defined in ${\mathbb{R}^{m+1}}$ . In particular, we construct an explicit sequence for the case ${M_0(x)=\mathbf{P}_k(\underline x)}$ being an arbitrary homogeneous monogenic polynomial defined in ${\mathbb R^m}$ . The connection of this sequence with the so-called Fueter’s theorem will also be discussed.     

On-diagonal oscillation of the heat kernels on post-critically finite self-similar fractals

For the canonical heat kernels p _t (x, y) associated with Dirichlet forms on post-critically finite self-similar fractals, e.g. the transition densities (heat kernels) of Brownian motion on affine nested fractals, the non-existence of the limit ${\lim_{t\downarrow 0}t^{d_{s}/2}p_{t}(x,x)}$ is established for a “generic” (in particular, almost every) point x, where d _s denotes the spectral dimension. Furthermore the same is proved for any point x in the case of the d-dimensional standard Sierpinski gasket with d ≥ 2 and the N-polygasket with N ≥ 3 odd, e.g. the pentagasket (N = 5) and the heptagasket (N = 7).     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

Hitting probabilities for systems of non-linear stochastic heat equations with multiplicative noise

We consider a system of d non-linear stochastic heat equations in spatial dimension 1 driven by d-dimensional space-time white noise. The non-linearities appear both as additive drift terms and as multipliers of the noise. Using techniques of Malliavin calculus, we establish upper and lower bounds on the one-point density of the solution u(t, x), and upper bounds of Gaussian-type on the two-point density of (u(s, y),u(t, x)). In particular, this estimate quantifies how this density degenerates as (s, y) → (t, x). From these results, we deduce upper and lower bounds on hitting probabilities of the process ${\{u(t,x)\}_{t \in \mathbb{R}_+, x\in [0,1]}}$ , in terms of respectively Hausdorff measure and Newtonian capacity. These estimates make it possible to show that points are polar when d ≥ 7 and are not polar when d ≤ 5. We also show that the Hausdorff dimension of the range of the process is 6 when d > 6, and give analogous results for the processes ${t \mapsto u(t,x)}$ and ${x \mapsto u(t,x)}$ . Finally, we obtain the values of the Hausdorff dimensions of the level sets of these processes.     

On locally bounded above solutions of an equation of the Goła̧b–Schinzel type

We characterize solutions ${f, g : \mathbb{R} \to \mathbb{R}}$ of the functional equation f(x + g(x)y) = f(x)f(y) under the assumption that f is locally bounded above at each point ${x \in \mathbb{R}}$ . Our result refers to Go?a?b and Schinzel (Publ Math Debr 6:113–125, 1959) and Wo?od?ko (Aequationes Math 2:12–29, 1968).     

A Hardy type inequality for W m,1(0, 1) functions

In this paper, we consider functions ${u\in W^{m,1}(0,1)}$ where m ≥ 2 and u(0) = Du(0) = · · · = D ^m-1 u(0) = 0. Although it is not true in general that ${\frac{D^ju(x)}{x^{m-j}} \in L^1(0,1)}$ for ${j\in \{0,1,\ldots,m-1\}}$ , we prove that ${\frac{D^ju(x)}{x^{m-j-k}} \in W^{k,1}(0,1)}$ if k ≥ 1 and 1 ≤ j + k ≤ m, with j, k integers. Furthermore, we have the following Hardy type inequality, $$\left\|{D^k\left({\frac{D^ju(x)}{x^{m-j-k}}}\right)}\right\|_{L^1(0,1)} \leq \frac {(k-1)!}{(m-j-1)!} \|{D^mu}\|_{L^1(0,1)},$$ where the constant is optimal.     

The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus

Let x and y be points chosen uniformly at random from ${\mathbb {Z}_n^4}$ , the four-dimensional discrete torus with side length n. We show that the length of the loop-erased random walk from x to y is of order n ²(log n)^1/6, resolving a conjecture of Benjamini and Kozma. We also show that the scaling limit of the uniform spanning tree on ${\mathbb {Z}_n^4}$ is the Brownian continuum random tree of Aldous. Our proofs use the techniques developed by Peres and Revelle, who studied the scaling limits of the uniform spanning tree on a large class of finite graphs that includes the d-dimensional discrete torus for d ≥ 5, in combination with results of Lawler concerning intersections of four-dimensional random walks.     

2-Reducible Two Paths and an Edge Constructing a Path in (2k + 1)-Edge-Connected Graphs

Let k ≥ 5 be an odd integer and G = (V(G), E(G)) be a k-edge-connected graph. For ${X\subseteq V(G),e(X)}$ denotes the number of edges between X and V(G) ? X. We here prove that if ${\{s_i,t_i\}\subseteq X_i\subseteq V(G)(i=1,2),f}$ is an edge between s ₁ and ${s_2,X_1\cap X_2=\emptyset,e(X_1)\le 2k-3,e(X_2)\le 2k-2}$ , and e(Y) ≥ k + 1 for each ${Y\subseteq V(G)}$ with ${Y\cap\{s_1,t_1,s_2,t_2\}=\{s_1,t_2\}}$ , then there exist paths P ₁ and P ₂ such that P _i joins s _i and ${t_i,V(P_i)\subseteq X_i}$ (i = 1, 2) and ${G-f-E(P_1\cup P_2)}$ is (k ? 2)-edge-connected, and in fact we give a generalization of this result.     

Self-interacting diffusions: a simulated annealing version

We study asymptotic properties of processes X, living in a Riemannian compact manifold M, solution of the stochastic differential equation (SDE) $$dX_t = dW_t(X_t) - \beta(t)\nabla V\mu_t(X_t)dt$$ with W a Brownian vector field, β(t) = alog(t + 1), $\mu_t = \frac{1}{t} \int_0^t \delta_{X_s}ds$ and $V\mu_t(x) = \frac{1}{t}\int_0^t V(x, X_s)ds$ , V being a smooth function. We show that the asymptotic behavior of μ _t can be described by a non-autonomous differential equation. This class of processes extends simulated annealing processes for which V(x, y) is only a function of x. In particular we study the case $M = {\mathbb{S}}^n$ , the n-dimensional sphere, and V(x, y) = ?cos(d(x, y)), where d(x, y) is the distance on ${\mathbb{S}}^n$ , which corresponds to a process attracted by its past trajectory. In this case, it is proved that μ _t converges almost surely towards a Dirac measure.     

On Group Choosability of Graphs,II

Given a group A and a directed graph G, let F(G, A) denote the set of all maps ${f : E(G) \rightarrow A}$ . Fix an orientation of G and a list assignment ${L : V(G) \mapsto 2^A}$ . For an ${f \in F(G, A)}$ , G is (A, L, f)-colorable if there exists a map ${c:V(G) \mapsto \cup_{v \in V(G)}L(v)}$ such that ${c(v) \in L(v)}$ , ${\forall v \in V(G)}$ and ${c(x)-c(y)\neq f(xy)}$ for every edge e = xy directed from x to y. If for any ${f\in F(G,A)}$ , G has an (A, L, f)-coloring, then G is (A, L)-colorable. If G is (A, L)-colorable for any group A of order at least k and for any k-list assignment ${L:V(G) \rightarrow 2^A}$ , then G is k-group choosable. The group choice number, denoted by ${\chi_{gl}(G)}$ , is the minimum k such that G is k-group choosable. In this paper, we prove that every planar graph is 5-group choosable, and every planar graph with girth at least 5 is 3-group choosable. We also consider extensions of these results to graphs that do not have a K ₅ or a K _3,3 as a minor, and discuss group choosability versions of Hadwiger’s and Woodall’s conjectures.     

Every 3-connected $$\{K_{1,3},N_{1,2,3}\}$$-free graph is Hamilton-connected

A graph G is \(\{X,Y\}\)-free if it contains neither X nor Y as an induced subgraph. Pairs of connected graphs X, Y such that every 3-connected \(\{X,Y\}\)-free graph is Hamilton-connected have been investigated recently in (2002, 2000, 2012). In this paper, it is shown that every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected, where \(N_{1,2,3}\) is the graph obtained by identifying end vertices of three disjoint paths of lengths 1, 2, 3 to the vertices of a triangle.