A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.
We consider the stochastic equation \[ X_t=x_0+\int _0^t b(u,X_{u})\mathrm{d}B_u,\quad t\ge 0, \] where $B$ is a one-dimensional Brownian motion, $x_0\in \mathbb{R}$ is the initial value, and $b\:[0,\infty )\times \mathbb{R}\rightarrow \mathbb{R}$ is a time-dependent diffusion coefficient. While the existence of solutions is well-studied for only measurable diffusion coefficients $b$, beyond the homogeneous case there is no general result on the uniqueness in law of the solution. The purpose of the present note is to give conditions on $b$ ensuring the existence as well as the uniqueness in law of the solution.
Let {Xn} be a stationary and ergodic time series taking values from a finite or countably infinite set X and that f(X) is a function of the process with finite second moment. Assume that the distribution of the process is otherwise unknown. We construct a sequence of stopping times λn along which we will be able to estimate the conditional expectation E(f(Xλn+1)|X0,…,Xλn) from the observations (X0,…,Xλn) in a point wise consistent way for a restricted class of stationary and ergodic finite or countably infinite alphabet time series which includes among others all stationary and ergodic finitarily Markovian processes. If the stationary and ergodic process turns out to be finitarily Markovian (in particular, all stationary and ergodic Markov chains are included in this class) then limn→∞nλn>0 almost surely. If the stationary and ergodic process turns out to possess finite entropy rate then λn is upper bounded by a polynomial, eventually almost surely.
The radio antipodal number of a graph G is the smallest integer c such that there exists an assignment f : V (G) → {1, 2, . . . , c} satisfying |f(u) − f(v)| ≥ D − d(u, v) for every two distinct vertices u and v of G, where D is the diameter of G. In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin and P. Zhang, Math. Bohem. 127 (2002), 57– 69]. We also show the connections between this colouring and radio labelings.
We prove that a rank ≥3 Dowling geometry of a group H is partition representable if and only if H is a Frobenius complement. This implies that Dowling group geometries are secret-sharing if and only if they are multilinearly representable., František Matúš and Aner Ben-Efraim., and Obsahuje bibliografické odkazy
When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector, which is a desired property in some practical situations.
Let $R$ be an associative ring with identity and let $J(R)$ denote the Jacobson radical of $R$. $R$ is said to be semilocal if $R/J(R)$ is Artinian. In this paper we give necessary and sufficient conditions for the group ring $RG$, where $G$ is an abelian group, to be semilocal.