Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

Integers with dense divisors

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are y-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?y. Let D(x,y,z) be the number of positive integers not exceeding x whose divisors are y-dense and whose prime divisors are bigger than z, and let , and . We show that is equivalent, in a large region, to a function d(u,v) which satisfies a difference-differential equation. Using that equation we find that d(u,v)?(1−u/v)/(u+1) for v?3+ε. Finally, we show that d(u,v)=e^−γd(u)+O(1/v), where γ is Euler's constant and d(u)∼x⁻¹D(x,y,1), for fixed u. This leads to a new estimate for d(u).     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Pancyclic oriented graphs

Let D be an oriented graph of order n ≧ 9 and minimum degree n ? 2. This paper proves that D is pancyclic if for any two vertices u and v, either uv ? A(D), or d_D⁺(u) + d_D^?(v) ≧ n ? 3.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

Geodesic-pancyclic graphs

A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by d_G(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,v∈V(G) and for each integer k with d_G(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,v∈V(G), every u-v geodesic lies on every cycle of length k satisfying max{2d_G(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs.     

Global solutions of the fast diffusion equation with gradient absorption terms

We investigate the existence of nonnegative weak solutions to the problem ut=Δ(um)−p|∇u| in Rn×(0,∞) with ⁺(1−2/n)<m<1. It will be proved that: (i) When 1<p<2, if the initial datum u₀∈D(Rn) then there exists a solution; (ii) When 1<p<(2+mn)/(n+1), if the initial datum u₀(x) is a bounded and nonnegative measure then the solution exists; (iii) When (2+mn)/(n+1)?p<2, if the initial datum is a Dirac mass then the solution does not exist. We also study the large time behavior of the L¹-norm of solutions for 1<p?(2+mn)/(n+1), and the large time behavior of t1/β‖u(⋅,t)−Ec(⋅,t)L^∞_‖ for (2+mn)/(n+1)<p<2.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Existence and uniqueness of nonnegative solutions for a boundary blow-up problem

Assume that Ω is a bounded domain in RN (N?3) with smooth boundary ∂Ω. In this work, we study existence and uniqueness of blow-up solutions for the problem −Δp(u)+c(x)|∇u|^p−1+F(x,u)=0 in Ω, where 2?p. Under some conditions related to the function F, we give a sufficient condition for existence and nonexistence of nonnegative blow-up solutions. We study also the uniqueness of these solutions.     

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).     

On a nonlocal problem for semilinear differential equations with upper semicontinuous nonlinearities in general Banach spaces

Sufficient conditions on the existence of mild solutions for the following semilinear nonlocal evolution inclusion with upper semicontinuous nonlinearity: u^′(t)∈A(t)u(t)+F(t,u(t)), 0<t?d, u(0)=g(u), are given when g is completely continuous and Lipschitz continuous in general Banach spaces, respectively. An example concerning the partial differential equation is also presented.     

Asymptotic behaviour of solutions to some pseudoparabolic equations

The aim of this paper is to investigate the behaviour as t→∞ of solutions to the Cauchy problem u_t−△u_t−v△u−(b,∇u)=∇⋅F(u),u(x,0)=u₀(x), where v>0 is a fixed constant, t≥0, x∈Ω, Ω is a bounded domain in Rⁿ. We will first establish an a priori estimate. Then, we establish the global existence, uniqueness and continuous dependence of the weak solution for the Sobolev-Galpern type equation with the Dirichlet boundary.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Multiple positive solutions of nonhomogeneous elliptic systems with strongly indefinite structure and critical Sobolev exponents

In this paper, we study the existence of multiple positive solutions to some Hamiltonian elliptic systems −Δv=λu+u^p+εf(x), −Δu=μv+v^q+δg(x) in Ω;u,v>0 in Ω; u=v=0 on ∂Ω, where Ω is a bounded domain in R^N (N?3); 0?f, g∈L∞(Ω); 1/(p+1)+1/(q+1)=(N−2)/N, p,q>1; λ,μ>0. Using sub- and supersolution method and based on an adaptation of the dual variational approach, we prove the existence of at least two nontrivial positive solutions for all λ,μ∈(0,λ₁) and ε,δ∈(0,δ₀), where λ₁ is the first eigenvalue of the Laplace operator −Δ with zero Dirichlet boundary conditions and δ₀ is a positive number.     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

Primitive digraphs with smallest large exponent

A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies α_n?γ(D)?w_n, where α_n=⌊w_n/2⌋+2 and w_n=(n-1)²+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to α_n is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent α_n and n+2 arcs. These constructions extend to digraphs with some exponents between α_n and w_n. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent α_n and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2.     

Study of weak solutions for parabolic equations with nonstandard growth conditions

The authors of this paper study the existence and uniqueness of weak solutions of the initial and boundary value problem for ut=div((uσ+d₀)|∇u|^p(x,t)−2∇u)+f(x,t). Localization property of weak solutions is also discussed.     

A short proof of Fan's theorem

In this note, we give a new short proof of the following theorem: Let G be a 2-connected graph of order n. If for any two vertices u and v with d(u,v)=2,max{d(u),d(v)}?c/2, then the circumference of G is at least c, where 3?c?n and d(u,v) is the distance between u and v in G.