The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

Optimal threat strategies of bimatrix games

A bi-matrix threat game is defined as a triple (A,B,S) whereA andB arem×n payoff matrices, andS is a closed convex subset of the plane, with (a _ij,B _ij) εS for eachi,j. Given (threat) mixed strategiesx andy,Nash's model suggests that the eventual outcome will be that point (u, v) εS which maximizes the product (u ?xAy ^t) (v ?xBy ^t) subject tou ≥xAy ^t,v ≥xBy ^t. Optimality of the threat strategies is then defined in the obvious way. A constructive proof of existence of optimal threat strategies is given; in particular, it is shown that they are optimal strategies for the matrix gameA-kB, wherek is to be determined. In this paper,k is approximated by aNewton-Raphson technique. Two examples are solved in detail.     

On the existence of bounded solutions for a nonlinear elliptic system

This work deals with the system (?Δ) ^m u?= a(x) v ^p , (?Δ) ^m v?=?b(x)?u ^q with Dirichlet boundary condition in a domain ${\Omega\subset\mathbb{R}^n}$ , where Ω is a ball if n ≥ 3 or a smooth perturbation of a ball when n?=?2. We prove that, under appropriate conditions on the parameters (a, b, p, q, m, n), any nonnegative solution (u, v) of the system is bounded by a constant independent of (u, v). Moreover, we prove that the conditions are sharp in the sense that, up to some border case, the relation on the parameters are also necessary. The case m?=?1 was considered by Souplet (Nonlinear Partial Differ Equ Appl 20:464–479, 2004). Our paper generalize to m ≥ 1 the results of that paper.     

Properties of the set of positive solutions to Dirichlet boundary value problems with time singularities

The paper investigates the structure and properties of the set S of all positive solutions to the singular Dirichlet boundary value problem u″(t) + au′(t)/t ? au(t)/t ² = f(t, u(t),u′(t)), u(0) = 0, u(T) = 0. Here a ∈ (?∞,?1) and f satisfies the local Carathéodory conditions on [0,T]×D, where D = [0,∞)×?. It is shown that S _c = {u ∈ S: u′(T) = ?c} is nonempty and compact for each c ≥ 0 and S = ∪ _c≥0 S _c . The uniqueness of the problem is discussed. Having a special case of the problem, we introduce an ordering in S showing that the difference of any two solutions in S _c ,c≥ 0, keeps its sign on [0,T]. An application to the equation v″(t) + kv′(t)/t = ψ(t)+g(t, v(t)), k ∈ (1,∞), is given.     

Power Values of Derivations with Annihilator Conditions on Lie Ideals in Prime Rings

Let R be a prime ring of char R ≠ 2, d a nonzero derivation of R, U a noncentral Lie ideal of R, and a ∈ R. If au ^{n ₁} d(u) ^{n ₂} u ^{n ₃} d(u) ^{n ₄} u ^{n ₅} … d(u) ^{n _k?1} u ^{n _k}  = 0 for all u ∈ U, where n ₁, n ₂,…,n _k are fixed non-negative integers not all zero, then a = 0 and if a(u ^s d(u)u ^t ) ⁿ  ∈ Z(R) for all u ∈ U, where s ≥ 0, t ≥ 0, n ≥ 1 are some fixed integers, then either a = 0 or R satisfies S ₄, the standard identity in four variables.     

Graph Equation for Line Graphs and m-Step Graphs

Given a graph G, the m-step graph of G, denoted by S _m (G), has the same vertex set as G and an edge between two distinct vertices u and v if there is a walk of length m from u to v. The line graph of G, denoted by L(G), is a graph such that the vertex set of L(G) is the edge set of G and two vertices u and v of L(G) are adjacent if the edges corresponding to u and v share a common end vertex in G. We characterize connected graphs G such that S _m (G) and L(G) are isomorphic.     

3-(v, 4, 1) covering designs with chromatic numbers 2 and 3

A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, C_λ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Z_m such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ^?1(c)∣ c ∈ Z_m differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5^a 13^b 17^c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5^a 13^b 17^c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc.     

Asymptotic behavior of the least common multiple of consecutive arithmetic progression terms

Let l and m be two integers with l > m ≥ 0, and let a and b be integers with a ≥ 1 and a + b ≥ 1. In this paper, we prove that log lcm _{mn < i ≤ ln} {ai + b} = An + o(n), where A is a constant depending on l, m and a.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

A characterization of the groups L3(2n)

This note is concerned with finite groups in which a Sylow two-subgroup S has an elementary Abelian subgroup E of order 2²ⁿ, n≥2, such that E=A × z(S), ¦A¦=2ⁿ, and C_S(a)=E for any involutiona ∈ A. It is proved that a simple group satisfying this condition is isomorphic to L₃,(2ⁿ).     

Orders in regular rings with minimal condition for principal right ideals

ABSTRACT

A ring R is called an n-clean (resp. Σ-clean) ring if every element in R is n-clean (resp. Σ-clean). Clean rings are 1-clean and hence are Σ-clean. An example shows that there exists a 2-clean ring that is not clean. This shows that Σ-clean rings are a proper generalization of clean rings. The group ring ?_(p) G with G a cyclic group of order 3 is proved to be Σ-clean. The m× m matrix ring M _m (R) over an n-clean ring is n-clean, and the m×m (m>1) matrix ring M _m (R) over any ring is Σ-clean. Additionally, rings satisfying a weakly unit 1-stable range were introduced. Rings satisfying weakly unit 1-stable range are left-right symmetric and are generalizations of abelian π-regular rings, abelian clean rings, and rings satisfying unit 1-stable range. A ring R satisfies a weakly unit 1-stable range if and only if whenever a ₁ R + ˙˙˙ a _m R = dR, with m ≥ 2, a ₁,…, a _m, d ∈ R, there exist u ₁ ∈ U(R) and u ₂,…, u _m ∈ W(R) such that a ₁ u ₁ + ? a _m u _m = Rd.     

On stable range conditions

In this paper, we show that a ring R satisfies unit 1-stable range if and only if a₁R + ? + a_mR = dR with m ≥ 2,a ₁, ?a_m ?R implies that there exist u₁ , ?u_m ? U(R) such that a₁u₁ +?+a_mu_m = d and an exchange ring R has stable range one if and only if a₁R+?+a_mR = dR with m ≥ 2,a ₁,?,a_m ? R implies that there exist unit-regular w ₁,?,w_m ? R such that a₁w₁ +?+ a_mw_m = d. Also we show that an exchange ring R satisfies the n-stable range condition if and only if a( ⁿR)+bR = dR with a ? Rⁿ,b,d ? R implies that there exist unimodular regular w ? ⁿ R and: y ? R such that aw+by = d.     

Probabilities of dominant candidates based on first-place votes

Suppose each of an odd number n of voters has a strict preference order on the three ‘candidates’ in {1,2,3} and votes for his most preferred candidate on a plurality ballot. Assume that a voter who votes for i is equally likely to have ijk and ikj as his preference order when {i,j,k} = {1,2,3}.Fix an integer m between $\text{1}\text{2}$(n + 1) and n inclusive. Then, given that n_i of the n voters vote for i, let f_m(n₁,n₂,n₃) be the probability that one of the three candidates is preferred by m or more voters to each of the other two.This paper examines the behavior of f_m over the lattice points in L_n, the set of triples of non-negative integers that sum to n. It identifies the regions in L_n where f_m is 1 and where f_m is 0, then shows that f_m(a,b + 1, c)>f_m(a + 1,b,c) whenever a + b + c + 1 = n, a≤c≤b, a<c<m and c≤n ? m. These results are used to partially identify the points in L_n where f_m is minimized subject to f_m>0. It is shown that at least two of the n_i are equal at minimizing points.     

Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L ^k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G ^k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T,  h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G,  h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1.     

Mutually independent bipanconnected property of hypercube

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v₀, v₁, … , v_m〉 is a sequence of adjacent vertices. Two paths with equal length P₁ = 〈 u₁, u₂, … , u_m〉 and P₂ = 〈 v₁, v₂, … , v_m〉 from a to b are independent if u₁ = v₁ = a, u_m = v_m = b, and u_i ≠ v_i for 2 ? i ? m − 1. Paths with equal length from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d_G(u, v) ? l ? ∣V(G) − 1∣ with (l − d_G(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d_Qn(u,v)?n-1, is (n − 1, l)-mutually independent bipanconnected for every with (l-d_Qn(u,v)) being even. As for d_Qn(u,v)?n-2, it is also (n − 1, l)-mutually independent bipanconnected if l?d_Qn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=d_Qn(u,v).     

Generalized rational identities and rings with involution

The main goal of this paper is to present the following generalization of a theorem of Desmarais: LetD be a fixed division ring and letE?D be a division ring with involution * and with infinite centerC such that (E:C)=∞. ItS is the set of all 2m-tuples of the form (a ₁,a ₂, ...,a _m ,a ₁ ^* ,a ₂ ^* , ...,a _m ^* ),a _i ∈E, then any generalized rational identity (overD) vanishing onS (where defined) must in fact vanish onE ^2m (where defined). The result follows as a corollary to Bergman's generalization of Amitsur's basic result on rational identities, and for completeness we present Cohn's account of Bergman's result.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

A symmetry relationship for a class of partitions

Let S(n, k, v) denote the number of vectors (a₀,…, a_n?1) with nonnegative integer components that satisfy a₀ + … + a_{n ? 1} = k and Σ_i=0^n?1ia_i ≡ v (mod n). Two proofs are given for the relation S(n, k, v) = S(k, n, v). The first proof is by algebraic enumeration while the second is by combinatorial construction.     

Coloring BIBDs with block size 4

It is shown that for each integer m ≥ 1 there exists a lower bound, v_m, with the property that for all v ≥ v_m with v ≡ 1, 4 (mod 12) there exists an m-chromatic S(2, 4, v) design. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 403–409, 1998