Meyniel's theorem for strongly (p,q) - Hamiltonian digraphs

We give the following theorem: Let D = (V, E) be a strongly (p + q + 1)-connected digraph with n ≥ p + q + 1 vertices, where p and q are nonnegative integers, p ≤ n - 2, n ≥ 2. Suppose that, for each four vertices u, v, w, z (not necessarily distinct) such that {u, v} ∩ {w, z} = Ø, (w, u) ? E, (v, z) ? E, we have id(u) + od(v) + od(w + id(z) ≥ 2 (n + p + q)) + 1. Then D is strongly (p, q)-Hamiltonian.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Distance graphs with missing multiples in the distance sets

Given positive integers m, k, and s with m > ks, let D_m,k,s represent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, D_m,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i − j| ∈ D_m,k,s. The chromatic number and the fractional chromatic number of G(Z, D_m,k,s) are denoted by χ(Z, D_m,k,s) and χf(Z, D_m,k,s), respectively. For s = 1, χ(Z, D_m,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, D_m,k,1) for any m and k. This article extends the study of χ(Z, D_m,k,s) and χf(Z, D_m,k,s) to general values of s. We prove χf(Z, D_m,k,s) = χ(Z, D_m,k,s) = k if m < (s + 1)k; and χf(Z, D_m,k,s) = (m + sk + 1)/(s + 1) otherwise. The latter result provides a good lower bound for χ(Z, D_m,k,s). A general upper bound for χ(Z, D_m,k,s) is obtained. We prove the upper bound can be improved to ⌈(m + sk + 1)/(s + 1)⌉ + 1 for some values of m, k, and s. In particular, when s + 1 is prime, χ(Z, D_m,k,s) is either ⌈(m + sk + 1)/(s + 1)⌉ or ⌈(m + sk + 1)/(s + 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, D_m,k,s) are classified into these two possible values of χ(Z, D_m,k,s). Moreover, complete solutions of χ(Z, D_m,k,s) for several families are determined including the case s = 1 (solved in [2]), the case s = 2, the case (k, s + 1) = 1, and the case that k is a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999     

The smooth Banach submanifold B*(E, F) in B(E, F)

Let E,F be two Banach spaces,B(E,F),B+(E,F),Φ(E,F),SΦ(E,F) and R(E,F) be bounded linear,double splitting,Fredholm,semi-Frdholm and finite rank operators from E into F,respectively. Let Σ be any one of the following sets:{T ∈Φ(E,F):Index T=constant and dim N(T)=constant},{T ∈ SΦ(E,F):either dim N(T)=constant< ∞ or codim R(T)=constant< ∞} and {T ∈ R(E,F):Rank T=constant< ∞}. Then it is known that Σ is a smooth submanifold of B(E,F) with the tangent space TAΣ={B ∈ B(E,F):BN(A)-R(A) } for any A ∈Σ. However,for ...     

Existence of Three Positive Pseudo-symmetric Solutions for a One Dimensional Discrete p-Laplacian

We apply the Five Functionals Fixed Point Theorem to verify the existence of at least three positive pseudo-symmetric solutions for the discrete three point boundary value problem, ?(g(?u(t-1)))+a(t))f(u(t))=0, for t∈{a+1,…,b+1} and u(a)=0 with u(v)=u(b+2) where g(v)=|v| ^p-2 v, p>1, for some fixed v∈{a+1,…,b+1} and σ=(b+2+v)/2 is an integer.     

[a,b]-factorizations of graphs

Let a and b be integers with b ? a ? 0. A graph G is called an [a,b]-graph if a ? d_G(v) ? b for each vertex v ∈ V(G), and an [a,b]-factor of a graph G is a spanning [a,b]-subgraph of G. A graph is [a,b]-factorable if its edges can be decomposed into [a,b]-factors. The purpose of this paper is to prove the following three theorems: (i) if 1 ? b ? 2a, every [(12a + 2)m + 2an,(12b + 4)m + 2bn]-graph is [2a, 2b + 1]-factorable; (ii) if b ? 2a ?1, every [(12a ?4)m + 2an, (12b ?2)m + 2bn]-graph is [2a ?1,2b]-factorable; and (iii) if b ? 2a ?1, every [(6a ?2)m + 2an, (6b + 2)m + 2bn]-graph is [2a ?1,2b + 1]-factorable, where m and n are nonnegative integers. They generalize some [a,b]-factorization results of Akiyama and Kano [3], Kano [6], and Era [5].     

On a class of semicommutative modules

Let R be a ring with identity, M a right R-module and S = End _R (M). In this note, we introduce S-semicommutative, S-Baer, S-q.-Baer and S-p.q.-Baer modules. We study the relations between these classes of modules. Also we prove if M is an S-semicommutative module, then M is an S-p.q.-Baer module if and only if M[x] is an S[x]-p.q.-Baer module, M is an S-Baer module if and only if M[x] is an S[x]-Baer module, M is an S-q.-Baer module if and only if M[x] is an S[x]-q.-Baer module.     

The structure of the 3-separations of 3-connected matroids

Tutte defined a k-separation of a matroid M to be a partition (A,B) of the ground set of M such that |A|,|B|k and r(A)+r(B)−r(M)<k. If, for all m<n, the matroid M has no m-separations, then M is n-connected. Earlier, Whitney showed that (A,B) is a 1-separation of M if and only if A is a union of 2-connected components of M. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. When M is 3-connected, this paper describes a tree decomposition of M that displays, up to a certain natural equivalence, all non-trivial 3-separations of M.     

The number of connected sparsely edged graphs. II. Smooth graphs and blocks

A smooth graph is a connected graph without endpoints; f(n, q) is the number of connected graphs, v(n, q) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: W_k, V_k, and U_k are the exponential generating functions of f(n, n + k), v(n, n + k), and u(n, n + k), respectively. For any k ? 1, our reduction method shows that V_k can be deduced at once from W_k, which was found for successive k by the computer method described in our previous paper. Again the reduction method shows that U_k must be a sum of powers (mostly negative) of 1 - X and, given this information, we develop a recurrence method well suited to calculate U_k for successive k. Exact formulas for v(n, n + k) and u(n, n + k) for general n follow at once.     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

On the differences between Szeged and Wiener indices of graphs

Let G be a connected graph and η(G)=Sz(G)−W(G), where W(G) and Sz(G) are the Wiener and Szeged indices of G, respectively. A well-known result of Klav?ar, Rajapakse, and Gutman states that η(G)≥0, and by a result of Dobrynin and Gutman η(G)=0 if and only if each block of G is complete. In this paper, a path-edge matrix for the graph G is presented by which it is possible to classify the graphs in which η(G)=2. It is also proved that there is no graph G with the property that η(G)=1 or η(G)=3. Finally, it is proved that, for a given positive integer k,k≠1,3, there exists a graph G with η(G)=k.     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

Power cocentralizing generalized derivations on prime rings

Let R be a prime ring, U the Utumi quotient ring of R, C = Z(U) the extended centroid of R, L a non-central Lie ideal of R, H and G non-zero generalized derivations of R. Suppose that there exists an integer n ≥ 1 such that (H(u)u − uG(u)) ⁿ = 0, for all u ∈ L, then one of the following holds: (1) there exists c ∈ U such that H(x) = xc, G(x) = cx; (2) R satisfies the standard identity s ₄ and char (R) = 2; (3) R satisfies s ₄ and there exist a, b, c ∈ U, such that H(x) = ax+xc, G(x) = cx+xb and (a − b) ⁿ = 0.     

Quasi‐symmetric designs with fixed difference of block intersection numbers

The following results for proper quasi‐symmetric designs with non‐zero intersection numbers x,y and λ > 1 are proved.

• (1) Let D be a quasi‐symmetric design with z = y ? x and v ≥ 2k. If x ≥ 1 + z + z³ then λ < x + 1 + z + z³.
• (2) Let D be a quasi‐symmetric design with intersection numbers x, y and y ? x = 1. Then D is a design with parameters v = (1 + m) (2 + m)/2, b = (2 + m) (3 + m)/2, r = m + 3, k = m + 1, λ = 2, x = 1, y = 2 and m = 2,3,… or complement of one of these design or D is a design with parameters v = 5, b = 10, r = 6, k = 3, λ = 3, and x = 1, y = 2.
• (3) Let D be a triangle free quasi‐symmetric design with z = y ? x and v ≥ 2k, then x ≤ z + z².
• (4) For fixed z ≥ 1 there exist finitely many triangle free quasi‐symmetric designs non‐zero intersection numbers x, y = x + z.
• (5) There do not exist triangle free quasi‐symmetric designs with non‐zero intersection numbers x, y = x + 2.

© 2006 Wiley Periodicals, Inc. J Combin Designs 15: 49–60, 2007     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

A new infinite class of S(3, {4, 5, 7}, v)

A t‐wise balanced design ( at BD) of order v and block sizes from K , denoted by S ( t , K , v ), is a pair ( X , ??), where X is a v ‐element set and ?? is a set of subsets of X , called blocks , with the property that | B |∈ K for any B ∈?? and every t ‐element subset of X is contained in a unique block. In this article, we shall show that there is an S ( 3 , { 4 , 5 , 7 }, v ) for any positive integer v ≡ 7 ( mod12 ) with v ≠ 19 . Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 20:68–80, 2012     

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Upper and lower bounds of the valence-functional

For the non-negative integerg let (M, g) denote the closed orientable 2-dimensional manifold of genusg. K-realizationsP of (M, g) are geometric cell-complexes inP with convex facets such that set (P) is homeomorphic toM. ForK-realizationsP of (M, g) and verticesv ofP, val (v,P) denotes the number of edges ofP incident withv and the weighted vertex-number Σ(val(v, P)-3) taken over all vertices ofP is called valence-valuev (P) ofP. The valence-functionalV, which is important for the determination of all possiblef-vectors ofK-realisations of (M, g), in connection with Eberhard's problem etc., is defined byV(g):=min[v(P)|P is aK-realization of (M,g)]. The aim of the note is to prove the inequality 2g+1≦V(g)≦3g+3 for every positive integerg.