Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

The Signed k-Submatchings in Graphs

A signed k-submatching of a graph G is a function f : E(G) → {?1,1} satisfying f (E _G (v)) ≤ 1 for at least k vertices ${v \in V(G)}$ . The maximum of the values of f (E(G)), taken over all signed k-submatchings f, is called the signed k-submatching number and is denoted by ${\beta_S^{k}(G)}$ . In this paper, sharp bounds on ${\beta_S^{k}(G)}$ for general graphs are presented. Exact values of ${\beta_S^{k}(G)}$ for several classes of graphs are found.     

Convolutions of random measures on compact groups

LetG be a compact group andM ₁(G) be the convolution semigroup of all Borel probability measures onG with the weak topology. We consider a stationary sequence {μ _n } _n=?∞ ^+∞ of random measures μ _n =μ _n (ω) inM ₁(G) and the convolutions $$v_{m,n} (\omega ) = \mu _m (\omega )* \cdots *\mu _{n - 1} (\omega ), m< n$$ and $$\alpha _n^{( + k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n,n + i} (\omega ),} \alpha _n^{( - k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n - i,n} (\omega )} $$ We describe the setsA _m ⁺ (ω) andA _n ⁺ (ω) of all limit points ofv _m,n(ω) asm→?∞ orn→+∞ and the setA _∞(ω) of its two-sided limit points for typical realizations of {μ _n (ω)} _n=?∞ ^+∞ . Using an appropriate random ergodic theorem we study the limit random measures ρ _n ^(±) (ω)=lim _k→∞ α _n ^(±k) (ω).     

Inversion complexity of self-correcting circuits for a certain sequence of boolean functions

The asymptotics L _k ^? (f ₂ ⁿ ) ?? n min{k+1, p} is obtained for the sequence of Boolean functions $f_2^n \left( {x_1 , \ldots ,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n}$ for any fixed k, p ?? 1 and growing n, here L _k ^? (f ₂ ⁿ ) is the inversion complexity of realization of the function f ₂ ⁿ by k-self-correcting circuits of functional elements in the basis B = {&, ?}, p is the weight of a reliable invertor.     

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.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

Long time small solutions to nonlinear parabolic equations

A sharp result on global small solutions to the Cauchy problem $$u_t = \Delta u + f\left( {u,Du,D^2 u,u_t } \right)\left( {t > 0} \right),u\left( 0 \right) = u_0 $$ In Rⁿ is obtained under the the assumption thatf is C^1+r forr>2/n and ‖u ₀‖C²(R ⁿ ) +‖u ₀‖W ₁ ² (R ⁿ ) is small. This implies that the assumption thatf is smooth and ‖u ₀ ‖W ₁ ^k (R ⁿ )+‖u ₀‖W ₂ ^k (R ⁿ ) is small fork large enough, made in earlier work, is unnecessary.     

The Signed Edge-Domatic Number of a Graph

For a nonempty graph G = (V, E), a signed edge-domination of G is a function ${f: E(G) \to \{1,-1\}}$ such that ${\sum_{e'\in N_{G}[e]}{f(e')} \geq 1}$ for each ${e \in E(G)}$ . The signed edge-domatic number of G is the largest integer d for which there is a set {f ₁,f ₂, . . . , f _d } of signed edge-dominations of G such that ${\sum_{i=1}^{d}{f_i(e)} \leq 1}$ for every ${e \in E(G)}$ . This paper gives an original study on this concept and determines exact values for some special classes of graphs, such as paths, cycles, stars, fans, grids, and complete graphs with even order.     

A special f-edge cover-coloring of multigraphs

An edge cover-coloring of G is called a special (f,g)-edge cover-coloring, if each color appears at each vertex at least f(v) times and the number of multiple edges receive the same color is at most g(vw) for vw∈E(G). Let $\chi_{f_{g}}''$ denote the maximum positive integer k for which using k colors a special (f,g)-edge cover-coloring of G exists. The existence of $\chi_{f_{g}}''$ is discussed and the lower bound of $\chi_{f_{g}}''$ is obtained.     

О некоторых свойства х частичных сумм рядо в Фурье—Уолша—Пэли

In this paper we consider the behaviour of partial sums of Fourier—Walsh—Paley series on the group62-01. We prove the following theorems: Theorem 1. Let {n _k } _k ^=1/∞ be some increasing convex sequence of natural numbers such that $$\mathop {\lim sup}\limits_m m^{ - 1/2} \log n_m< \infty $$ . Then for anyf∈L ^∞(G) $$\left( {\frac{1}{m}\sum\limits_{j = 1}^m {|Sn_j (f;0)|^2 } } \right)^{1/2} \leqq C \cdot \left\| f \right\|_\infty $$ . Theorem 2. Let {n _k } _k ^=1/∞ be a lacunary sequence of natural numbers,n _k+1/n _k≧q>1. Then for anyfεL ^∞(G) $$\sum\limits_{j = 1}^m {|Sn_j (f;0)| \leqq C_q \cdot m^{1/2} \cdot \log n_m \cdot \left\| f \right\|_\infty } $$ . Theorems. Let µ _k =2 ^k +2 ^k-2+2 ^k-4+...+2^α ₀,α ₀=0,1. Then $$\begin{gathered} \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in L^\infty (G)\} = \{ \{ a_k \} _{k = 1}^\infty ;\sum\limits_{k = 1}^m {a_k^2 = 0(m)^2 \} .} \hfill \\ \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in C(G)\} = \{ \{ a_k \} _{k = 1}^\infty ;\sum\limits_{k = 1}^m {a_k^2 = o(m)^2 \} = } \hfill \\ = \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in C(G),f(0) = 0\} \hfill \\ \end{gathered} $$ . Theorem 4. {{S ₂ k(f: 0)} _k ^=1/∞ ,f∈L ^∞(G)}=m. $$\{ \{ S_{2_k } (f:0\} _{k = 1}^\infty ;f \in C(G)\} = c. \{ \{ S_{2_k } (f:0\} _{k = 1}^\infty ;f \in C(G),f(0) = 0\} = c_0 $$ .     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

Local linear independence of the translates of a box spline

Let Ξ=(ξ _i ) _l ⁿ be a sequence of vectors inR ^m . The box splineM _Ξ is defined as the distribution given by $$M_\Xi :\varphi \to \int_{[0,1]^n } \varphi \left( {\sum\limits_{i = 1}^n {\lambda (i)\xi _i } } \right)d\lambda ,\varphi \in C_c^\infty (R^m ).$$ . Suppose that Ξ contains a basis forR ^m . ThenM _Ξ∈L _∞(R ^m ). Assume $$\Xi \subset V: = z^m .$$ . Consider the translatesM _v :=M _Ξ(·?v),v∈V. It is known that (M _v ) _V is linearly dependent unless (*) $$|\det Z| = 1forallbasesZ \subset \Xi$$ . This paper demonstrates that under condition (*), (M _v ) _V is locally linearly independent, i.e., $$\{ M_v ;\sup p M_v \cap A \ne \not 0\}$$ is linearly independent over any open setA.     

Quasikonvexe Multiplikatoren starker Konvergenz

пУсть {f _k; f _k ^* ?X×X^* — пОлНАь БИОРтОгОНАльНАь сИс тЕМА В БАНАхОВОМ пРОстРАН стВЕ X (X^* — сОпРьжЕННОЕ пРОст РАНстВО). пУсть (?→+0) $$\begin{gathered} S_n f = \sum\limits_{k = 0}^n {f_k^* (f)f_k ,} K(f,t) = \mathop {\inf }\limits_{g \in Z} (\left\| {f - g} \right\|_x + t\left| g \right|_z ), \hfill \\ X_0 = \{ f \in X:\mathop {\lim }\limits_{n \to \infty } \left\| {S_n f - f} \right\|_x = 0\} ,X_\omega = \{ f \in X:K(f,t) = 0(\omega (t))\} , \hfill \\ \end{gathered} $$ гДЕZ?X — НЕкОтОРОЕ пОД пРОстРАНстВО с пОлУН ОРМОИ ¦·¦ И Ω — МОДУль НЕпРЕРыВНО стИ УДОВлЕтВОРьУЩИИ Усл ОВИУ sup Ω(t)/t=∞. пОслЕДОВАтЕ льНОстьΤ={Τ _k} кОМплЕксНых ЧИ сЕл НАжыВАЕтсь МНОжИтЕл ЕМ сИльНОИ схОДИМОст И ДльX _Τ, жАпИсьΤ?М[X _Τ,X _Τ], ЕслИ Д ль кАжДОгО ЁлЕМЕНтАf?X _Τ сУЩЕстВ УЕт тАкОИ ЁлЕМЕНтf ^τ?х₀, ЧтОf _k ^* (f ^τ)=Τ_kf _k ^* (f) Дль ВсЕхk. ДОкА жАНО сРЕДИ ДРУгИх слЕДУУЩ ЕЕ УтВЕРжДЕНИЕ. тЕОРЕМА. пУсmь {f_k; f _k ^* } —Н ЕкОтОРыИ (с, 1)-БАжИс тАк ОИ, ЧтО ВыпОлНьУтсь НЕРАВЕН стВА тИпА НЕРАВЕНстВА ДжЕ ксОНА с пОРьДкОМ O(?_n) u тИ пА НЕРАВЕНстВА БЕРНшmЕИ НА с пОРьДкОМ O(1/?_n). ЕслИ пОслЕДОВАтЕл ьНОсть Τ кВАжИВыпУкл А И ОгРАНИЧЕНА, тО $$\tau \in M[X_{\omega ,} X_0 ] \Leftrightarrow \omega (\varphi _n )\tau _n \left\| {S_n } \right\|_{[X,X]} = o(1).$$ ЁтОт ОБЩИИ пОДхОД НЕМ ЕДлЕННО ДАЕт клАссИЧ ЕскИЕ РЕжУльтАты, ОтНОсьЩИ Есь к ОДНОМЕРНыМ тРИгОНОМЕтРИЧЕскИМ РьДАМ. НО тЕпЕРь ВОжМО жНы ДАльНЕИшИЕ пРИлОжЕН Иь, НАпРИМЕР, к РАжлОжЕНИьМ пО пОлИ НОМАМ лЕжАНДРА, лАгЕР РА ИлИ ЁРМИтА.     

A system of functions

A system of functions $$f_k (x) = \sum\nolimits_{i = 1}^r a _i \varphi _\iota (x)^k + b_i \overline {\varphi _\iota } (x)^k , k = 1,2,...$$ is considered on the interval [0,l]. Under certain conditions on the? _i(x), it is proved that the system 1 ∪ {f_k(x)} _k=1 ^∞ is complete in the space L_p(0,l). In the case r=1 it is proved, under certain additional assumptions, that the system {f_k(x)} _k=0 ^∞ is minimal.     

The crossing function of a graph

The crossing function of a graphG with orientable genusn is defined as a mapping \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) for whichf(k)=cr _k (G) the crossing number ofG on the orientable surface of genusk. It is proved that any decreasing convex function \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) with \(f(n) = \not 0\) is the crossing function of some connected graph.     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Limit ultraspherical series and their approximation properties

We study new series of the form $\sum\nolimits_{k = 0}^\infty {f_k^{ - 1} \hat P_k^{ - 1} (x)} $ in which the general term $f_k^{ - 1} \hat P_k^{ - 1} (x)$ , k = 0, 1, …, is obtained by passing to the limit as α→?1 from the general term $\hat f_k^\alpha \hat P_k^{\alpha ,\alpha } (x)$ of the Fourier series $\sum\nolimits_{k = 0}^\infty {f_k^\alpha \hat P_k^{\alpha ,\alpha } (x)} $ in Jacobi ultraspherical polynomials $\hat P_k^{\alpha ,\alpha } (x)$ generating, for α> ?1, an orthonormal system with weight (1 ? x ₂)α on [?1, 1]. We study the properties of the partial sums $S_n^{ - 1} (f,x) = \sum\nolimits_{k = 0}^n {f_k^{ - 1} \hat P_k^{ - 1} (x)} $ of the limit ultraspherical series $\sum\nolimits_{k = 0}^\infty {f_k^{ - 1} \hat P_k^{ - 1} (x)} $ . In particular, it is shown that the operator S _n ^?1 (f) = S _n ^?1 (f, x) is the projection onto the subspace of algebraic polynomials p _n = p _n (x) of degree at most n, i.e., S _n (p _n ) = p _n ; in addition, S _n ^?1 (f, x) coincides with f(x) at the endpoints ±1, i.e., S _n ^?1 (f,±1) = f(±1). It is proved that the Lebesgue function Λ _n (x) of the partial sums S _n ^?1 (f, x) is of the order of growth equal to O(ln n), and, more precisely, it is proved that $\Lambda _n (x) \leqslant c(1 + \ln (1 + n\sqrt {1 - x^2 } )), - 1 \leqslant x \leqslant 1$ .     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2

It is shown that the conjunction complexity L _k ^& (f ₂ ⁿ ) of monotone symmetric Boolean functions \(f_2^n (x_1 , \ldots ,x_n ) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j\) realized by k-self-correcting circuits in the basis B = {&, ?} asymptotically equals to (k + 2)n for growing n providing the price of a reliable conjunctor is ≥ k + 2.