On positive-influence target-domination

Consider a graph \(G=(V,E)\) and a vertex subset \(A \subseteq V\). A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. For a target vertex subset \(S \subseteq V\), a vertex subset A is a positive-influence target-dominating set for target set S if every vertex in S is positive-influence dominated by A. Given a graph G and a target vertex subset S, the positive-influence target-dominating set (PITD) problem is to find the minimum positive-influence dominating set for target S. In this paper, we show two results: (1) The PITD problem has a polynomial-time \((1 + \log \lceil \frac{3}{2} \Delta \rceil )\)-approximation in general graphs where \(\Delta \) is the maximum vertex-degree of the input graph. (2) For target set S with \(|S|=\Omega (|V|)\), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs.     

Hitting times of sequences

Let X be an ergodic Markov chain on a finite state space S₀ and let s and t be finite sequences of elements from S₀. We give an easily computable formula for the expected time of completing t, given that s was just observed. If A₀ is a finite set of such sequences, we show how that formula may be used to compute the hitting distribution on A₀.     

Menger's Theorem for Graphs Containing no Infinite Paths

Menger's theorem can be stated as follows: Let G = (V, E) be a finite graph, and let A and B be subsets of V. Then there exists a family F of vertex-disjoint paths from A to B and a subset S of V which separates A and B, such that S consists of a choice of precisely one vertex from each path in F.Erdös conjectured that in this form the theorem can be extended to infinite graphs. We prove this to be true for graphs containing no infinite paths, by showing that in this case the problem can be reduced to the case of bipartite graphs.     

Time-varying minimum cost flow problems

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,c_r,c_w) be a network with an arc set A and a vertex set V. Each a∈A is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost c_r(a,t), and a positive capacity limit l(a,t). Each x∈V is associated with two integer parameters: a waiting cost c_w(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,… The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.     

Tensor products and preservation of limits, for acts over monoids

In 1971, Stenström published one of the first papers devoted to the problem of when, for a monoid S and a right S -act A _S , the functor A? (from the category of left acts over S into the category of sets) has certain limit preservation properties. Attention at first focused on when this functor preserves pullbacks and equalizers but, since that time, a large number of related articles have appeared, most having to do with when this functor preserves monomorphisms of various kinds. All of these properties are often referred to as flatness properties of acts . Surprisingly, little attention has so far been paid to the obvious questions of when A _S ? preserves all limits, all finite limits, all products, or all finite products. The present article addresses these matters.     

On deformations of crossed products

Let A∗Γ be a crossed product algebra, where A is semisimple, finitely generated over its center and Γ is a finite group. We give a necessary and sufficient condition in terms of the outer action of Γ on A for the existence of a multi-parametric semisimple deformation of the form A((t₁,…,t_n))∗Γ (with the induced outer action). The main tool in the proof is the solution of the so-called twisting problem. We also give an example which shows that the condition is not sufficient if one drops the condition on the finite generation of A over its center.     

Invariant bilinear forms on a vertex algebra

In this paper we construct a linear space that parameterizes all invariant bilinear forms on a given vertex algebra with values in a arbitrary vector space. Also we prove that every invariant bilinear form on a vertex algebra is symmetric. This is a generalization of the result of Li (J. Pure Appl. Algebra 96(3) (1994) 279), who proved this for the case when the vertex algebra is non-negatively graded and has finite dimensional homogeneous components.As an application, we introduce a notion of a radical of a vertex algebra. We prove that a radical-free vertex algebra A is non-negatively graded, and its component A₀ of degree 0 is a commutative associative algebra, so that all structural maps and operations on A are A₀-linear. We also show that in this case A is simple if and only if A₀ is a field.     

The endomorphism spectrum of a monounary algebra

The endomorphism spectrum specA of an algebra A is defined as the set of all positive integers, which are equal to the number of elements in an endomorphic image of A, for all endomorphisms of A. In this paper we study finite monounary algebras and their endomorphism spectrum. If a finite set S of positive integers is given, one can look for a monounary algebra A with S = specA. We show that for countably many finite sets S, no such A exists. For some sets S, an appropriate A with spec A = S are described. For n ∈ ? it is easy to find a monounary algebra A with {1, 2, ..., n} = specA. It will be proved that if i ∈ ?, then there exists a monounary algebra A such that specA skips i consecutive (consecutive eleven, consecutive odd, respectively) numbers. Finally, for some types of finite monounary algebras (binary and at least binary trees) A, their spectrum is shown to be complete.     

Subpullback flat S-posets need not be subequalizer flat

If S is a monoid, a right S-act A _S is a set A, equipped with a “right S-action” A×S→A sending the pair (a,s)∈ A×S to as, that satisfies the conditions (i) a(st)=(as)t and (ii) a1=a for all a∈A and s,t∈S. If, in addition, S is equipped with a compatible partial order and A is a poset, such that the action is monotone (when A×S is equipped with the product order), then A _S is called a right S-poset. Left S-acts and S-posets are defined analogously. For a given S-act (resp. S-poset) a tensor product functor A _S ?? from left S-acts to sets (resp. left S-posets to posets) exists, and A _S is called pullback flat or equalizer flat (resp. subpullback flat or subequalizer flat) if this functor preserves pullbacks or equalizers (resp. subpullbacks or subequalizers). By analogy with the Lazard-Govorov Theorem for R-modules, B. Stenström proved in 1971 that an S-act is isomorphic to a directed colimit of finitely generated free S -acts if and only if it is both pullback flat and equalizer flat. Some 20 years later, the present author showed that, in fact, pullback flatness by itself is sufficient. (A new, more direct proof of that result is contained in the present article.) In 2005, Valdis Laan and the present author obtained a version of the Lazard-Govorov Theorem for S-posets, in which subpullbacks and subequalizers now assume the role previously played by pullbacks and equalizers. The question of whether subpullback flatness implies subequalizer flatness remained unsolved. The present paper provides a negative answer to this question.     

Jacobi method for symmetric 4 × 4 matrices converges for every cyclic pivot strategy

The paper studies the global convergence of the Jacobi method for symmetric matrices of size 4. We prove global convergence for all 720 cyclic pivot strategies. Precisely, we show that inequality S(A ^[t+3]) ≤ γ S(A ^[t]), t ≥ 1, holds with the constant γ < 1 that depends neither on the matrix A nor on the pivot strategy. Here, A ^[t] stands for the matrix obtained from A after t full cycles of the Jacobi method and S(A) is the off-diagonal norm of A. We show why three consecutive cycles have to be considered. The result has a direct application on the J-Jacobi method.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Matching Properties in Total Domination Vertex Critical Graphs

A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ _t (G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _t (G?v) < γ _t (G). A total domination vertex critical graph G is called k-γ _t -critical if γ _t (G) = k. In this paper we first show that every 3-γ _t -critical graph G of even order has a perfect matching if it is K _1,5-free. Secondly, we show that every 3-γ _t -critical graph G of odd order is factor-critical if it is K _1,5-free. Finally, we show that G has a perfect matching if G is a K _1,4-free 4-γ _t (G)-critical graph of even order and G is factor-critical if G is a K _1,4-free 4-γ _t (G)-critical graph of odd order.     

The growth series of H(ℤ × ℤ2)

Let H be a group with finite generating set A, and growth series η(t) with respect to A. Then the growth series of H?(?×?₂) with respect to the finite generating set A∪ {(1, 0), (0,1)} is explicitly calculated, in terms of η(t).     

The operator-valued Feynman-Kac formula with noncommutative operators

Let X(t) be a right-continuous Markov process with state space E whose expectation semigroup S(t), given by S(t) φ(x) = E_x[φ(X(t))] for functions φ mapping E into a Banach space L, has the infinitesimal generator A. For each x?E, let V(x) generate a strongly continuous semigroup T_x(t) on L. An operator-valued Feynman-Kac formula is developed and solutions of the initial value problem $\text{?u}\text{?t}\text{= Au + V(x)u, u(0) = φ}$ are obtained. Fewer conditions are assumed than in known results; in particular, the semigroups {T_x(t)} need not commute, nor must they be contractions. Evolution equation theory is used to develop a multiplicative operative functional and the corresponding expectation semigroup has the infinitesimal generator A + V(x) on a restriction of the domain of A.     

The Lyapunov order for real matrices

The real Lyapunov order in the set of real n×n matrices is a relation defined as follows: A?B if, for every real symmetric matrix S, SB+B^tS is positive semidefinite whenever SA+A^tS is positive semidefinite. We describe the main properties of the Lyapunov order in terms of linear systems theory, Nevenlinna-Pick interpolation and convexity.     

Survival in a quasi-death process

We consider a Markov chain in continuous time with one absorbing state and a finite set S of transient states. When S is irreducible the limiting distribution of the chain as t→∞, conditional on survival up to time t, is known to equal the (unique) quasi-stationary distribution of the chain. We address the problem of generalizing this result to a setting in which S may be reducible, and show that it remains valid if the eigenvalue with maximal real part of the generator of the (sub)Markov chain on S has geometric (but not, necessarily, algebraic) multiplicity one. The result is then applied to pure death processes and, more generally, to quasi-death processes. We also show that the result holds true even when the geometric multiplicity is larger than one, provided the irreducible subsets of S satisfy an accessibility constraint. A key role in the analysis is played by some classic results on M-matrices.