Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

Properties of traveling waves for integrodifference equations with nonmonotone growth functions

In this paper, we will establish some new properties of traveling waves for integrodifference equations with the nonmonotone growth functions. More precisely, for c ≥ c _*, we show that either lim_x?+￥ f(x)=u*{\lim\limits_{\xi\rightarrow+\infty} \phi(\xi)=u*} or 0 < liminf_{x? + ￥} f(x) < u* < limsup_x?+￥f(x) ￡ b,{0 < \liminf\limits_{\xi \rightarrow + \infty} \phi(\xi) < u* < \limsup \limits_{\xi\rightarrow+\infty}\phi(\xi)\leq b,} that is, the wave converges to the positive equilibrium or oscillates about it at +∞. Sufficient conditions can assure that both results will arise. We can also obtain that any traveling wave with wave speed c > c* possesses exponential decay at −∞. These results can be well applied to three types of growth functions arising from population biology. By choosing suitable parameter numbers, we can obtain the existence of oscillating waves. Our analytic results are consistent with some numerical simulations in Kot (J Math Biol 30:413–436, 1992), Li et al. (J Math Biol 58:323–338, 2009) and complement some known ones.     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

An Erd?s-Gallai Theorem for Matroids

Erdős and Gallai showed that for any simple graph with n vertices and circumference c it holds that | E(G) | ￡ \frac12(n - 1)c{{{\mid}{E(G)}{\mid} \leq {\frac{1}{2}}(n - 1)c}}. We extend this theorem to simple binary matroids having no F ₇-minor by showing that for such a matroid M with circumference c(M) ≥  3 it holds that | E(M) | ￡ \frac12r(M)c(M){{{\mid}{E(M)}{\mid} \leq {\frac{1}{2}}r(M)c(M)}}.     

On the reconstruction index of permutation groups: semiregular groups

Summary. The reconstruction index of all semiregular permutation groups is determined. We show that this index satisfies 3 ￡ r(G, W) ￡ 5 3 \leq \rho(G, \Omega) \leq 5 and we classify the groups in each case.     

Generalized time-dependent conditional linear models under left truncation and right censoring

Consider the model f(S(z|X)){\phi(S(z|X))} = \pmbb(z) [(X)\vec]{\pmb{\beta}(z) {\vec{X}}}, where f{\phi} is a known link function, S(·|X) is the survival function of a response Y given a covariate X, [(X)\vec]{\vec{X}} = (1, X, X ² , . . . , X ^p ) and \pmbb(z){\pmb{\beta}(z)} is an unknown vector of time-dependent regression coefficients. The response is subject to left truncation and right censoring. Under this model, which reduces for special choices of f{\phi} to e.g. Cox proportional hazards model or the additive hazards model with time dependent coefficients, we study the estimation of the vector \pmbb(z){\pmb{\beta}(z)} . A least squares approach is proposed and the asymptotic properties of the proposed estimator are established. The estimator is also compared with a competing maximum likelihood based estimator by means of simulations. Finally, the method is applied to a larynx cancer data set.     

On the mean square of the error term for the asymmetric two-dimensional divisor problems(II)

Let Δ(a, b; x) denote the error term of the asymmetric two-dimensional divisor problem. In this paper we shall study the relation between the discrete mean value ?_{n ￡ T} D²(a,b;n){\sum_{n\leq T} \Delta^2(a,b;n)} and the continuous mean value ò₁^TD²(a,b;x)dx{\int_1^T\Delta^2(a,b;x)dx} .     

On some inequalities for Doob decompositions in Banach function spaces

Let ${\Phi : \mathbb{R} \to [0, \infty)}Let F: \mathbbR ? [0, ￥){\Phi : \mathbb{R} \to [0, \infty)} be a Young function and let f = (f_n)_n ? \mathbbZ₊{f = (f_n)_n\in\mathbb{Z}_{+}} be a martingale such that F(f_n) ? L₁{\Phi(f_n) \in L_1} for all n ? \mathbbZ₊{n \in \mathbb{Z}_{+}} . Then the process F(f) = (F(f_n))_n ? \mathbbZ₊{\Phi(f) = (\Phi(f_n))_n\in\mathbb{Z}_{+}} can be uniquely decomposed as F(f_n)=g_n+h_n{\Phi(f_n)=g_n+h_n} , where g=(g_n)_n ? \mathbbZ₊{g=(g_n)_n\in\mathbb{Z}_{+}} is a martingale and h=(h_n)_n ? \mathbbZ₊{h=(h_n)_n\in\mathbb{Z}_{+}} is a predictable nondecreasing process such that h ₀ = 0 almost surely. The main results characterize those Banach function spaces X such that the inequality ||h_￥||_X ￡ C ||F(Mf) ||_X{\|{h_{\infty}}\|_{X} \leq C \|{\Phi(Mf)} \|_X} is valid, and those X such that the inequality ||h_￥||_X ￡ C ||F(Sf) ||_X{\|{h_{\infty}}\|_{X} \leq C \|{\Phi(Sf)} \|_X} is valid, where Mf and Sf denote the maximal function and the square function of f, respectively.     

An explicit growth condition for middle-degree cuspidal cohomology of arithmetically defined quaternionic hyperbolic n-manifolds

Let G/\mathbb Q{G/\mathbb Q} be the simple algebraic group Sp(n, 1) and G = G(N){\Gamma=\Gamma(N)} a principal congruence subgroup of level N ≥ 3. Denote by K a maximal compact subgroup of the real Lie group G(\mathbb R){G(\mathbb R)} . Then a double quotient G\G(\mathbb R)/K{\Gamma\backslash G(\mathbb R)/K} is called an arithmetically defined, quaternionic hyperbolic n-manifold. In this paper we give an explicit growth condition for the dimension of cuspidal cohomology H²ⁿ_cusp(G\G(\mathbb R)/K,E){H^{2n}_{cusp}(\Gamma\backslash G(\mathbb R)/K,E)} in terms of the underlying arithmetic structure of G and certain values of zeta-functions. These results rely on the work of Arakawa (Automorphic Forms of Several Variables: Taniguchi Symposium, Katata, 1983, eds. I. Satake and Y. Morita (Birkh?user, Boston), pp. 1–48, 1984).     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

On some composite functional inequalities

The aim of the paper is to deal with the following composite functional inequalities

All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.     

A characterization of hyperbolic potentials of rational maps

Consider a rational map f of degree at least 2 acting on its Julia set J(f), a H?lder continuous potential φ: J(f) → ℝ and the pressure P(f,φ). In the case where

On cardinality constrained cycle and path polytopes

Given a directed graph D = (N, A) and a sequence of positive integers ${1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}Given a directed graph D = (N, A) and a sequence of positive integers 1 ￡ c₁ < c₂ < ? < c_m ￡ |N|{1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c _p for some p ? {1,?,m}{p \in \{1,\ldots,m\}}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.     

Around splitting and reaping for partitions of ω

We investigate splitting number and reaping number for the structure (ω) ^ω of infinite partitions of ω. We prove that \mathfrakr_d ￡ non(M),non(N),\mathfrakd{\mathfrak{r}_{d}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N}),\mathfrak{d}} and \mathfraks_d 3 \mathfrakb{\mathfrak{s}_{d}\geq\mathfrak{b}} . We also show the consistency results ${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})}${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and ${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})}${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})} . To prove the consistency \mathfrakr_d < add(M){\mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and \mathfraks_d < cof(M){\mathfrak{s}_{d} < \mathsf{cof}(\mathcal{M})} we introduce new cardinal invariants \mathfrakr_pair{\mathfrak{r}_{pair}} and \mathfraks_pair{\mathfrak{s}_{pair}} . We also study the relation between \mathfrakr_pair, \mathfraks_pair{\mathfrak{r}_{pair}, \mathfrak{s}_{pair}} and other cardinal invariants. We show that cov(M),cov(N) ￡ \mathfrakr_pair ￡ \mathfraks_d,\mathfrakr{\mathsf{cov}(\mathcal{M}),\mathsf{cov}(\mathcal{N})\leq\mathfrak{r}_{pair}\leq\mathfrak{s}_{d},\mathfrak{r}} and \mathfraks ￡ \mathfraks_pair ￡ non(M),non(N){\mathfrak{s}\leq\mathfrak{s}_{pair}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N})} .     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

Well-Posedness of Fractional Differential Equations on Vector-Valued Function Spaces

We study the well-posedness of the fractional differential equations with infinite delay (P ₂): D^a u(t)=Au(t)+ò^t_-￥a(t-s)Au(s)ds + f(t), (0 ￡ t ￡ 2p){D^\alpha u(t)=Au(t)+\int^{t}_{-\infty}a(t-s)Au(s)ds + f(t), (0\leq t \leq2\pi)}, where A is a closed operator in a Banach space ${X, \alpha > 0, a\in {L}^1(\mathbb{R}_+)}${X, \alpha > 0, a\in {L}^1(\mathbb{R}_+)} and f is an X-valued function. Under suitable assumptions on the parameter α and the Laplace transform of a, we completely characterize the well-posedness of (P ₂) on Lebesgue-Bochner spaces L^p(\mathbbT, X){L^p(\mathbb{T}, X)} and periodic Besov spaces B _p,q^s(\mathbbT, X){{B} _{p,q}^s(\mathbb{T}, X)} .     

Optimal Extension of Fourier Multiplier Operators in L p (G)

Given 1 ≤ p < ∞, a compact abelian group G and a p-multiplier ${\psi : \Gamma \to {\mathbb C}}Given 1 ≤ p < ∞, a compact abelian group G and a p-multiplier y: G? \mathbb C{\psi : \Gamma \to {\mathbb C}} (with Γ the dual group), we study the optimal domain of the multiplier operator T^(p)_y : L^p (G) ? L^p (G){T^{(p)}_\psi : L^p (G) \to L^p (G)}. This is the largest Banach function space, denoted by L¹(m^(p)_y){L^1(m^{(p)}_\psi)}, with order continuous norm into which L ^p (G) is embedded and to which T^(p)_y{ T^{(p)}_\psi} has a continuous L ^p (G)-valued extension. Compactness conditions for the optimal extension are given, as well as criteria for those ψ for which L¹(m^(p)_y) = L^p (G){L^1(m^{(p)}_\psi) = L^p (G)} is as small as possible and also for those ψ for which L¹(m^(p)_y) = L¹ (G){L^1(m^{(p)}_\psi) = L^1 (G)} is as large as possible. Several results and examples are presented for cases when L^p (G) \subsetneqq L¹(m^(p)_y) \subsetneqq L¹ (G){L^p (G) \subsetneqq L^1(m^{(p)}_\psi) \subsetneqq L^1 (G)}.