Pairs of Disjoint Dominating Sets in Connected Cubic Graphs

For a connected cubic graph G of order n, we prove the existence of two disjoint dominating sets D ₁ and D ₂ with |D₁|+|D₂| ￡ \frac157198n+\frac89{|D_1|+|D_2|\leq \frac{157}{198}n+\frac{8}{9}}.     

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)}}.     

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

Maximum IPP Codes of Length 3

Let Q be an alphabet with q elements. For any code C over Q of length n and for any two codewords a = (a ₁, . . . , a _n ) and b = (b ₁, . . . , b _n ) in C, let ${D({\bf a, b}) = \{(x_1, . . . , x_n) \in {Q^n} : {x_i} \in \{a_i, b_i\}\,{\rm for}\,1 \leq i \leq n\}}Let Q be an alphabet with q elements. For any code C over Q of length n and for any two codewords a = (a ₁, . . . , a _n ) and b = (b ₁, . . . , b _n ) in C, let D(a, b) = {(x₁, . . . , x_n) ? Qⁿ : x_i ? {a_i, b_i} for 1 ￡ i ￡ n}{D({\bf a, b}) = \{(x_1, . . . , x_n) \in {Q^n} : {x_i} \in \{a_i, b_i\}\,{\rm for}\,1 \leq i \leq n\}}. Let C^* = è_{a, b ? C}D(a, b){C^* = {{\bigcup}_{\rm {a,\,b}\in{C}}}D({\bf a, b})}. The code C is said to have the identifiable parent property (IPP) if, for any x ? C^*{{\rm {\bf x}} \in C^*}, ?_{x ? D(a, b)}{a, b} 1 ?{{\bigcap}_{{\rm x}{\in}D({\rm a,\,b})}\{{\bf a, b}\}\neq \emptyset} . Codes with the IPP were introduced by Hollmann et al [J. Combin. Theory Ser. A 82 (1998) 21–133]. Let F(n, q) = max{|C|: C is a q-ary code of length n with the IPP}.T? and Safavi-Naini [SIAM J. Discrete Math. 17 (2004) 548–570] showed that 3q + 6 - 6 é?{q+1}ù ￡ F(3, q) ￡ 3q + 6 - é6 ?{q+1}ù{3q + 6 - 6 \lceil\sqrt{q+1}\rceil \leq F(3, q) \leq 3q + 6 - \lceil 6 \sqrt{q+1}\rceil}, and determined F (3, q) precisely when q ≤ 48 or when q can be expressed as r ² + 2r or r ² + 3r +2 for r ≥ 2. In this paper, we establish a precise formula of F(3, q) for q ≥ 24. Moreover, we construct IPP codes of size F(3, q) for q ≥ 24 and show that, for any such code C and any x ? C^*{{\rm {\bf x}} \in C^*}, one can find, in constant time, a ? C{{\rm {\bf a}} \in C} such that if x ? D (c, d){{\rm {\bf x}} \in D ({\bf c, d})} then a ? {c, d}{{\rm {\bf a}} \in \{{\rm {\bf c, d}}\}}.     

Uniform estimates for order statistics and Orlicz functions

We establish uniform estimates for order statistics: Given a sequence of independent identically distributed random variables ξ ₁, … , ξ _n and a vector of scalars x = (x ₁, … , x _n ), and 1 ≤ k ≤ n, we provide estimates for \mathbb E   k-min_{1 ￡ i ￡ n} |x_ix_i|{\mathbb E \, \, k-{\rm min}_{1\leq i\leq n} |x_{i}\xi _{i}|} and \mathbb E k-max_{1 ￡ i ￡ n}|x_ix_i|{\mathbb E\,k-{\rm max}_{1\leq i\leq n}|x_{i}\xi_{i}|} in terms of the values k and the Orlicz norm ||y_x||_M{\|y_x\|_M} of the vector y _x  = (1/x ₁, … , 1/x _n ). Here M(t) is the appropriate Orlicz function associated with the distribution function of the random variable |ξ ₁|, G(t) = \mathbb P ({ |x₁| ￡ t}){G(t) =\mathbb P \left(\left\{ |\xi_1| \leq t\right\}\right)}. For example, if ξ ₁ is the standard N(0, 1) Gaussian random variable, then G(t) = ?{\tfrac2p}ò₀^t e^-\fracs22ds {G(t)= \sqrt{\tfrac{2}{\pi}}\int_{0}^t e^{-\frac{s^{2}}{2}}ds }  and M(s)=?{\tfrac2p}ò₀^se^-\frac12t2dt{M(s)=\sqrt{\tfrac{2}{\pi}}\int_{0}^{s}e^{-\frac{1}{2t^{2}}}dt}. We would like to emphasize that our estimates do not depend on the length n of the sequence.     

An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(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 total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

A Remark on the Growth of the Denominators of Convergents

For log\frac1+?52 ￡ l_* ￡ l^* < ￥{\rm log}\frac{1+\sqrt{5}}{2}\leq \lambda_\ast \leq \lambda^\ast < \infty , let E(λ_*, λ^*) be the set {x ? [0,1): liminf_{n ? ￥}\fraclogq_n(x)n=l_*, limsup_{n ? ￥}\fraclogq_n(x)n=l^*}. \left\{x\in [0,1):\ \mathop{\lim\inf}_{n \rightarrow \infty}\frac{\log q_n(x)}{n}=\lambda_{\ast}, \mathop{\lim\sup}_{n \rightarrow \infty}\frac{\log q_n(x)}{n}=\lambda^{\ast}\right\}. It has been proved in [1] and [3] that E(λ_*, λ^*) is an uncountable set. In the present paper, we strengthen this result by showing that dimE(l_*, l^*) 3 \fracl_* -log\frac1+?522l^*\dim E(\lambda_{\ast}, \lambda^{\ast}) \ge \frac{\lambda_{\ast} -\log \frac{1+\sqrt{5}}{2}}{2\lambda^{\ast}}     

Abelian coverings of finite general linear groups and an application to their non-commuting graphs

In this paper we introduce and study a family A_n(q)\mathcal{A}_{n}(q) of abelian subgroups of GL_n(q){\rm GL}_{n}(q) covering every element of GL_n(q){\rm GL}_{n}(q). We show that A_n(q)\mathcal{A}_{n}(q) contains all the centralizers of cyclic matrices and equality holds if q>n. For q>2, we obtain an infinite product expression for a probabilistic generating function for |A_n(q)||\mathcal{A}_{n}(q)|. This leads to upper and lower bounds which show in particular that

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.     

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.     

On the Mean Value of the Index of Composition of an Integer

For each integer n l(n)=[(log n)/(log g(n))]\lambda(n)={{\rm log}\, n\over{\rm log}\, \gamma(n)} be the index of composition of n, where g(n)=?_p|np\gamma(n)=\prod_{p\vert n}p . For convenience, we write ?_{x ￡ n ￡ x+?x}l(n)\sum_{x\le n\le x+\sqrt{x}}\lambda(n) and ?_{n ￡ x}l(n)\sum_{n\le x}\lambda(n) , as well as for ?_{x ￡ n ￡ x+?x}1/l(n)\sum_{x\le n\le x+\sqrt{x}}1/\lambda(n) and ?_{n ￡ x}1/l(n)\sum_{n\le x}1/\lambda(n) . Finally we study the sum of running over shifted primes.     

Takács’ Asymptotic Theorem and Its Applications: A Survey

The book of Lajos Takács Combinatorial Methods in the Theory of Stochastic Processes has been published in 1967. It discusses various problems associated with

Cancellation in primely generated refinement monoids

We prove that any primely generated refinement monoid M has separative cancellation, and even strong separative cancellation provided M has no nonzero idempotents. A form of multiplicative cancellation also holds: na ￡ nb na\leq nb implies a ￡ b a\leq b for a,b ? M a,b \in M and n ? {1,2,3,?} n \in \{1,2,3,\ldots\} . In addition, M is a semilattice in the sense that, given c₁,c₂ ? M c_1,c_2 \in M , there is an element d ? M d \in M such that c₁,c₂ ￡ d c_1,c_2 \leq d and, for all a ? M, c₁,c₂ ￡ a a \in M, c_1,c_2 \leq a implies d ￡ a d \leq a . Finally, we prove that any finitely generated refinement monoid is primely generated; in fact, this holds for any refinement monoid with a set of generators satisfying the descending chain condition.     

Extinction of solutions of semilinear higher order parabolic equations with degenerate absorption potential

We study the first vanishing time for solutions of the Cauchy–Dirichlet problem for the 2m-order (m ≥ 1) semilinear parabolic equation ${u_t + Lu + a(x) |u|^{q-1}u=0,\,0 < q < 1}We study the first vanishing time for solutions of the Cauchy–Dirichlet problem for the 2m-order (m ≥ 1) semilinear parabolic equation u_t + Lu + a(x) |u|^q-1u=0, 0 < q < 1{u_t + Lu + a(x) |u|^{q-1}u=0,\,0 < q < 1} with a(x) ≥ 0 bounded in the bounded domain W ì \mathbb R^N{\Omega \subset \mathbb R^N}. We prove that if N 1 2m{N \ne 2m} and ò₀¹ s^-1 (meas\nolimits {x ? W: |a(x)| ￡ s })^q ds < ￥, q = min(\frac2mN,1){\int_0^1 s^{-1} (\mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \})^\theta {\rm d}s < \infty,\ \theta=\min\left(\frac{2m}N,1\right)}, then the solution u vanishes in a finite time. When N = 2m, the same property holds if ${\int_0^1 s^{-1} \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) \ln \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) {\rm d}s > - \infty}${\int_0^1 s^{-1} \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) \ln \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) {\rm d}s > - \infty}.     

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

Improved Decay for Solutions to the Linear Wave Equation on a Schwarzschild Black Hole

We prove that sufficiently regular solutions to the wave equation ${\square_g\phi=0}We prove that sufficiently regular solutions to the wave equation \square_gf = 0{\square_g\phi=0} on the exterior of the Schwarzschild black hole obey the estimates |f| ￡ C_d v₊^-\frac32+d{|\phi|\leq C_\delta v_+^{-\frac{3}{2}+\delta}} and |?_tf| ￡ C_d v₊^-2+d{|\partial_t\phi|\leq C_{\delta} v_+^{-2+\delta}} on a compact region of r, including inside the black hole region. This is proved with the help of a new vector field commutator that is analogous to the scaling vector field on Minkowski spacetime. This result improves the known decay rates in the region of finite r and along the event horizon.     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

On Some Ramsey Numbers for Quadrilaterals Versus Wheels

For given graphs G ₁ and G ₂, the Ramsey number R(G ₁, G ₂) is the least integer n such that every 2-coloring of the edges of K _n contains a subgraph isomorphic to G ₁ in the first color or a subgraph isomorphic to G ₂ in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C ₄, W _n ) for 14 ≤ n ≤ 17.     

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.     

Quermassintegrals of a random polytope in a convex body

Let K be a convex body in \mathbbRⁿ \mathbb{R}^n with volume |K| = 1 |K| = 1 . We choose N 3 n+1 N \geq n+1 points x₁,?, x_N x_1,\ldots, x_N independently and uniformly from K, and write C(x₁,?, x_N) C(x_1,\ldots, x_N) for their convex hull. Let f : \mathbbR⁺ ? \mathbbR⁺ f : \mathbb{R^+} \rightarrow \mathbb{R^+} be a continuous strictly increasing function and 0 ￡ i ￡ n-1 0 \leq i \leq n-1 . Then, the quantity¶¶E (K, N, f °W_i) = ò_K ?ò_K f[W_i(C(x₁, ?, x_N))]dx_N ?dx₁ E (K, N, f \circ W_{i}) = \int\limits_{K} \ldots \int\limits_{K} f[W_{i}(C(x_1, \ldots, x_N))]dx_{N} \ldots dx_1 ¶¶is minimal if K is a ball (W_i is the i-th quermassintegral of a compact convex set). If f is convex and strictly increasing and 1 ￡ i ￡ n-1 1 \leq i \leq n-1 , then the ball is the only extremal body. These two facts generalize a result of H. Groemer on moments of the volume of C(x₁,?, x_N) C(x_1,\ldots, x_N) .