On product-cordial index sets and friendly index sets of 2-regular graphs and generalized wheels

A vertex labeling f : V → Z2 of a simple graph G = (V, E) induces two edge labelings f+ , f*: E → Z2 defined by f+ (uv) = f(u)+f(v) and f*(uv) = f(u)f(v). For each i∈Z2 , let vf(i) = |{v ∈ V : f(v) = i}|, e+f(i) = |{e ∈ E : f+(e) = i}| and e*f(i)=|{e∈E:f*(e)=i}|. We call f friendly if |vf(0)-vf(1)|≤ 1. The friendly index set and the product-cordial index set of G are defined as the sets{|e+f(0)-e+f(1)|:f is friendly} and {|e*f(0)-e*f(1)| : f is friendly}. In this paper we study and determine the connection between the friendly index sets and product-cordial index sets of 2-regular graphs and generalized wheel graphs.     

Minus total domination in graphs

A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ _t ⁻(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ _t ⁻(G).     

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

Strong labelings of linear forests

A （p, q）-graph G is called super edge-magic if there exists a bijective function f ： V（G） U E（G） →{1, 2 p＋q} such that f（u）＋ f（v）＋f（uv） is a constant for each uv C E（G） and f（Y（G）） = {1,2,...,p}. In this paper, we introduce the concept of strong super edge-magic labeling as a particular class of super edge-magic labelings and we use such labelings in order to show that the number of super edge-magic labelings of an odd union of path-like trees （mT）, all of them of the same order, grows at least exponentially with m.     

On friendly index sets of 2-regular graphs

Let G be a graph with vertex set V and edge set E, and let A be an abelian group. A labeling f:V→A induces an edge labeling f^∗:E→A defined by f^∗(xy)=f(x)+f(y). For i∈A, let v_f(i)=card{v∈V:f(v)=i} and e_f(i)=card{e∈E:f^∗(e)=i}. A labeling f is said to be A-friendly if |v_f(i)−v_f(j)|≤1 for all (i,j)∈A×A, and A-cordial if we also have |e_f(i)−e_f(j)|≤1 for all (i,j)∈A×A. When A=Z₂, the friendly index set of the graph G is defined as {|e_f(1)−e_f(0)|:the vertex labelingf is Z₂-friendly}. In this paper we completely determine the friendly index sets of 2-regular graphs. In particular, we show that a 2-regular graph of order n is cordial if and only if n?2 (mod 4).     

T-Colorings and T-Edge Spans of Graphs

 Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C ^d _n of the n-cycle C _n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C _n ^d for n≡0 or (mod d+1), and lower and upper bounds for other cases. Received: May 13, 1996 Revised: December 8, 1997     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Highest weight representations of a family of Lie algebras of Block type

For an additive subgroup G of a field F of characteristic zero, a Lie algebra B（G） of Block type is defined with basis {Lα,i｜ α∈G, i∈Z＋} and relations [Lα,i, Lβ,j] = （β-α）Lα＋β,i＋j＋（αj-βi）Lα＋β,Lα＋β,i＋j-1.It is proved that an irreducible highest weight B（Z）-module is quasifinite if and only if it is a proper quotient of a Verma module. Furthermore, for a total order λ on G and any ∧∈B（G）0^＊（the dual space of B（G）0 = span{L0,i｜i∈Z＋}）, a Verma B（G）-module M（∧,λ） is defined, and the irreducibility of M（A,λ） is completely determined.     

Conjugacy classes and finite p-groups

Let G be a finite p-group, where p is a prime number, and a ∈ G. Denote by Cl(a) = {gag⁻¹| g ∈ G} the conjugacy class of a in G. Assume that |Cl(a)| = pⁿ. Then Cl(a) Cl(a⁻¹) = {xy | x ∈ Cl(a), y ∈ Cl(a⁻¹)} is the union of at least n(p − 1) + 1 distinct conjugacy classes of G. Received: 16 December 2004     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Norm conditions for real-algebra isomorphisms between uniform algebras

Let A and B be uniform algebras. Suppose that α ≠ 0 and A ₁ ⊂ A. Let ρ, τ: A ₁ → A and S, T: A ₁ → B be mappings. Suppose that ρ(A ₁), τ(A ₁) and S(A ₁), T(A ₁) are closed under multiplications and contain expA and expB, respectively. If ‖S(f)T(g) − α‖_∞ = ‖ρ(f)τ(g) − α‖_∞ for all f, g ∈ A ₁, S(e ₁)⁻¹ ∈ S(A ₁) and S(e ₁) ∈ T(A ₁) for some e ₁ ∈ A ₁ with ρ(e ₁) = 1, then there exists a real-algebra isomorphism $ \tilde S $ \tilde S : A → B such that $ \tilde S $ \tilde S (ρ(f)) = S(e ₁)⁻¹ S(f) for every f ∈ A ₁. We also give some applications of this result.     

On the Cohen–Lusk theorem

Let G be a finite group and X be a G-space. For a map f: X → ℝ ^m , the partial coincidence set A(f, k), k ≤ |G|, is the set of points x ∈ X such that there exist k elements g ₁,…, g _k of the group G, for which f(g ₁ x) = ⋅⋅⋅ = f(g _k x) holds. We prove that the partial coincidence set is nonempty for G = ℤ _p ⁿ under some additional assumptions. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 61–67, 2007.     

A construction of weakly inverse semigroups

Let S° be an inverse semigroup with semilattice biordered set E° of idempotents and E a weakly inverse biordered set with a subsemilattice Ep = { e ∈ E ｜ arbieary f ∈ E, S（f , e） loheain in w（e）} isomorphic to E° by θ：Ep→E°. In this paper, it is proved that if arbieary f, g ∈E, f ←→ g→→ f°θD^s° g°θand there exists a mapping φ from Ep into the symmetric weakly inverse semigroup P J（E∪ S°） satisfying six appropriate conditions, then a weakly inverse semigroup ∑ can be constructed in P J（S°）, called the weakly inverse hull of a weakly inverse system （S°, E, θ, φ） with I（∑） ≌ S°, E（∑） ∽- E. Conversely, every weakly inverse semigroup can be constructed in this way. Furthermore, a sufficient and necessary condition for two weakly inverse hulls to be isomorphic is also given.     

On linguistic dynamical systems,families of graphs of large girth,and cryptography

The paper is devoted to the study of a linguistic dynamical system of dimension n ≥ 2 over an arbitrary commutative ring K, i.e., a family F of nonlinear polynomial maps f _α : K ⁿ → K ⁿ depending on “time” α ∈ {K − 0} such that f _α ⁻¹ = f _−αM, the relation f _α1 (x) = f _α2 (x) for some x ∈ Kⁿ implies α₁ = α₂, and each map f _α has no invariant points. The neighborhood {f _α (υ)∣α ∈ K − {0}} of an element v determines the graph Γ(F) of the dynamical system on the vertex set Kⁿ. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α₁, υ, α₂), s ≤ d, where α_i + α_i+1 is a nonzero divisor for i = 1, υ, d − 1, the vertices υ _a = f _α1 × ⋯ × f _αs (υ) in the graph are connected by a unique path. For each commutative ring K and each even integer n ≠= 0 mod 3, there is a family of linguistic dynamical systems L_n(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system L_n(q). If K = F_q, the graphs L(n, F_q) form a new family of graphs of large girth. The projective limit L(K) of L(n, K), n → ∞, is well defined for each commutative ring K; in the case of an integral domain K, the graph L(K) is a forest. If K has zero divisors, then the girth of K drops to 4. We introduce some other families of graphs of large girth related to the dynamical systems L_n(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric cryptographic algorithms. These graphs allow us to establish the best known upper bounds on the minimal order of regular graphs without cycles of length 4n, with odd n ≥ 3. Bibliography: 42 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 214–234.     

Packing cycles with modularity constraints

We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ _e∈E(C) γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle.     

Existence of singular solutions of a degenerate equation in R 2

Let a₁,a₂, . . . ,a_m ∈ ℝ², 2≤f ∈ C([0,∞)), g_i ∈ C([0,∞)) be such that 0≤g_i(t)≤2 on [0,∞) ∀i=1, . . . ,m. For any p>1, we prove the existence and uniqueness of solutions of the equation u_t=Δ(logu), u>0, in satisfying and logu(x,t)/log|x|→−f(t) as |x|→∞, logu(x,t)/log|x−a_i|→−g_i(t) as |x−a_i|→0, uniformly on every compact subset of (0,T) for any i=1, . . . ,m under a mild assumption on u₀ where We also obtain similar existence and uniqueness of solutions of the above equation in bounded smooth convex domains of ℝ² with prescribed singularities at a finite number of points in the domain.     

Correlation structure of intermittency in the parabolic Anderson model

Consider the Cauchy problem ∂u(x, t)/∂t = ℋu(x, t) (x∈ℤ^d, t≥ 0) with initial condition u(x, 0) ≡ 1 and with ℋ the Anderson Hamiltonian ℋ = κΔ + ξ. Here Δ is the discrete Laplacian, κ∈ (0, ∞) is a diffusion constant, and ξ = {ξ(x): x∈ℤ ^d } is an i.i.d.random field taking values in ℝ. G?rtner and Molchanov (1990) have shown that if the law of ξ(0) is nondegenerate, then the solution u is asymptotically intermittent. In the present paper we study the structure of the intermittent peaks for the special case where the law of ξ(0) is (in the vicinity of) the double exponential Prob(ξ(0) > s) = exp[−e ^{s /θ}] (s∈ℝ). Here θ∈ (0, ∞) is a parameter that can be thought of as measuring the degree of disorder in the ξ-field. Our main result is that, for fixed x, y∈ℤ ^d and t→∈, the correlation coefficient of u(x, t) and u(y, t) converges to ∥w _ρ∥⁻² _ℓ2Σ_{z ∈ℤd} w _ρ(x+z)w _ρ(y+z). In this expression, ρ = θ/κ while w _ρ:ℤ^d→ℝ⁺ is given by w _ρ = (v _ρ)^{⊗ d} with v _ρ: ℤ→ℝ⁺ the unique centered ground state (i.e., the solution in ℓ²(ℤ) with minimal l ²-norm) of the 1-dimensional nonlinear equation Δv + 2ρv log v = 0. The uniqueness of the ground state is actually proved only for large ρ, but is conjectured to hold for any ρ∈ (0, ∞). empty It turns out that if the right tail of the law of ξ(0) is thicker (or thinner) than the double exponential, then the correlation coefficient of u(x, t) and u(y, t) converges to δ _{x, y} (resp.the constant function 1). Thus, the double exponential family is the critical class exhibiting a nondegenerate correlation structure. Received: 5 March 1997 / Revised version: 21 September 1998     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

Highest weight representations of a Lie algebra of Block type

For a field F of characteristic zero and an additive subgroup G of F, a Lie algebra B(G) of the Block type is defined with the basis {Lα,i, c|α∈G, -1≤i∈Z} and the relations [Lα,i,Lβ,j] = ((i 1)β- (j 1)α)Lα β,i j αδα,-βδi j,-2c,[c, Lα,i] = 0. Given a total order (?) on G compatible with its group structure, and anyα∈B(G)0*, a Verma B(G)-module M(A, (?)) is defined, and the irreducibility of M(A,(?)) is completely determined. Furthermore, it is proved that an irreducible highest weight B(Z )-module is quasifinite if and only if it is a proper quotient of a Verma module.     

Applications of operator semigroups to Fourier analysis

Of concern are semigroups of linear norm one operators on Hilbert space of the form (discrete case)T={T ⁿ /n=0,1,2,...} or (continuous case)T={T(t)/t=≥0}. Using ergodic theory and Hilbert-Schmidt operators, the Cesàro limits (asn→∞) of |〈T ⁿ f,f〉|², |〈T (n)f,f〉|² are computed (withn∈ℤ⁺ orn∈ℤ⁺). Specializing the Hilbert space to beL ²(T,μ) (discrete case) orL ²(ℝ,μ) (continuous case) where μ is a Borel probability measure on the circle group or the line, the Cesàro limit of (asn→±∞, with,n∈ℤ orn∈ℝ) is obtained and interpreted. Extensions toT ^M , and ℝ ^M are given. Finally, we discuss recent operator theoretic extensions from a Hilbert to a Banach space context. Partially supported by an NSF grant