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.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

On the vanishing of Selmer groups for elliptic curves over ring class fields

Let E/Q be an elliptic curve of conductor N without complex multiplication and let K be an imaginary quadratic field of discriminant D prime to N. Assume that the number of primes dividing N and inert in K is odd, and let Hc be the ring class field of K of conductor c prime to ND with Galois group Gc over K. Fix a complex character χ of Gc. Our main result is that if LK(E,χ,1)≠0 then Selp(E/Hc)χ_⊗W=0 for all but finitely many primes p, where Selp(E/Hc) is the p-Selmer group of E over Hc and W is a suitable finite extension of Zp containing the values of χ. Our work extends results of Bertolini and Darmon to almost all non-ordinary primes p and also offers alternative proofs of a χ-twisted version of the Birch and Swinnerton-Dyer conjecture for E over Hc (Bertolini and Darmon) and of the vanishing of Selp(E/K) for almost all p (Kolyvagin) in the case of analytic rank zero.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Periodic solutions of semilinear equations of evolution of compact type

The existence of solutions in a weak sense of x′ + (A + B(t, x))x = f(t, x), x(0) = x(T) is established under the conditions that A generates a semigroup of compact type on a Hilbert space H; B(t,x) is a bounded linear operator and f(t, x) a function with values in H; for each square integrable ?(t) the problem with B(t, ?(t)) and f(t, ?(t)) in place of B(t, x) and f(t, x) has a unique solution; and B and f satisfy certain boundedness and continuity conditions.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

On systems of finite sets with constraints on their unions and intersections

Let F be a family of subsets of an n-element set. F is said to be of type (n, r, s) if A ∈ F, B ∈ F implies that |A ∪ B| ? n ? r, and |A ∩ B| ? s. Let f(n, r, s) = max {|F| : F is of type (n, r, s)}. We prove that f(n, r, s) ? f(n ? 1, r ? 1, s) + f(n ? 1, r + 1, s) if r > 0, n > s. And this result is used to give simple and unified proofs of Katona's and Frankl's results on f(n, r, s) when s = 0 and s = 1.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

Diameter-girth sufficient conditions for optimal extraconnectivity in graphs

For a connected graph G, the rth extraconnectivity κ_r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ₀(G) and κ₁(G), respectively. The minimum r-tree degree of G, denoted by ξ_r(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ₁(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κ_r-optimal, if κ_r(G)?ξ_r(G). In this paper, we present some sufficient conditions that guarantee κ_r(G)?ξ_r(G) for r?2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.     

Minimal prime ideals of skew polynomial rings and near pseudo-valuation rings

Let R be a ring. We recall that R is called a near pseudo-valuation ring if every minimal prime ideal of R is strongly prime. Let now σ be an automorphism of R and δ a σ-derivation of R. Then R is said to be an almost δ-divided ring if every minimal prime ideal of R is δ-divided. Let R be a Noetherian ring which is also an algebra over ? (? is the field of rational numbers). Let σ be an automorphism of R such that R is a σ(*)-ring and δ a σ-derivation of R such that σ(δ(a)) = δ(σ(a)) for all a ∈ R. Further, if for any strongly prime ideal U of R with σ(U) = U and δ(U) ? δ, U[x; σ, δ] is a strongly prime ideal of R[x; σ, δ], then we prove the following:

1. R is a near pseudo valuation ring if and only if the Ore extension R[x; σ, δ] is a near pseudo valuation ring.
2. R is an almost δ-divided ring if and only if R[x; σ, δ] is an almost δ-divided ring.

     

A note on k-potence preserving maps

Let M_n be the algebra of all n×n complex matrices and Γ_n the set of all k-potent matrices in M_n. Suppose ?:M_n→M_n is a map satisfying A-λB∈Γ_n implies ?(A)-λ?(B)∈Γ_n, where A, B∈M_n, λ∈C. Then either ? is of the form ?(A)=cTAT^-1, A∈M_n, or ? is of the form ?(A)=cTA^tT^-1, A∈M_n, where T∈M_n is an invertible matrix, c∈C satisfies c^k=c.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Super s-restricted edge-connectivity of vertex-transitive graphs

Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.     

On the lifting of elliptic cusp forms to cusp forms on quaternionic unitary groups

Let H be a definite quaternion algebra over Q with discriminant DH and R a maximal order of H. We denote by Gn a quaternionic unitary group and put Γn=Gn(Q)∩GL2n(R). Let Sκ(Γn) be the space of cusp forms of weight κ with respect to Γn on the quaternion half-space of degree n. We construct a lifting from primitive forms in Sk(SL₂(Z)) to Sk+2n−2(Γn) and a lifting from primitive forms in Sk(Γ₀(d)) to Sk+2(Γ₂), where d is a factor of DH. These liftings are generalizations of the Maass lifting investigated by Krieg.     

On some friends of the sociable numbers

Let s(n) denote the sum of the proper divisors of n. Set s ₀(n) = n, and for k > 0, put s _k (n) := s(s _k-1(n)) if s _k-1(n) > 0. Thus, perfect numbers are those n with s(n)?=?n and amicable numbers are those n with s(n) ?? n but s ₂(n)?=?n. We prove that for each fixed k ?? 1, the set of n which divide s _k (n) has density zero, and similarly for the set of n for which s _k (n) divides n. These results generalize the theorem of Erd?s that for each fixed k, the set of n for which s _k (n)?=?n has density zero.     

Lower bounds on covering codes via partition matrices

Let Kq(n,R) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σq(n,s;r) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound Kq(n,n−2) and σq(n,s;s−2) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on Kq(n,n−2) and to the new bound Kq(n,n−2)?3q−2n+2, improving the first iff 5?n<q?2n−4. We determine Kq(q,q−2)=q−2+σ₂(q,2;0) if q?10. Moreover, we obtain the new powerful recursive bound Kq+1(n+1,R+1)?min{2(q+1),Kq(n,R)+1}.