A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

An elementary operator with log-hyponormal, p-hyponormal entries

A Hilbert space operator A∈B(H) is p-hyponormal, A∈(p-H), if |A^∗|^2p?|A|^2p; an invertible operator A∈B(H) is log-hyponormal, A∈(?-H), if log(TT^∗)?log(T^∗T). Let d_AB=δ_AB or ?_AB, where δ_AB∈B(B(H)) is the generalised derivation δ_AB(X)=AX-XB and ?_AB∈B(B(H)) is the elementary operator ?_AB(X)=AXB-X. It is proved that if A,B^∗∈(?-H)∪(p-H), then, for all complex λ, , the ascent of (d_AB-λ)?1, and d_AB satisfies the range-kernel orthogonality inequality ‖X‖?‖X-(d_AB-λ)Y‖ for all X∈(d_AB-λ)^-1(0) and Y∈B(H). Furthermore, isolated points of σ(d_AB) are simple poles of the resolvent of d_AB. A version of the elementary operator E(X)=A₁XA₂-B₁XB₂ and perturbations of d_AB by quasi-nilpotent operators are considered, and Weyl’s theorem is proved for d_AB.     

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.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

A limiting absorption principle for Schrödinger operators with spherically symmetric exploding potentials

LetH=?Δ+V(r) be a Schrödinger operator with a spherically symmetric exploding potential, namely,V(r)=V _S(r)+V _L(r), whereV _S(r) is short-range and the exploding partV _L(r) satisfies the following assumptions: (a) Λ=lim sup _r→∞ V _L(r)<∞ (but Λ=?∞ is possible). Denote Λ⁺= max(Λ,0). (b)V _L(r)∈C ^2k (r ₀, ∞) and, with someδ>0 such that 2kδ>1: (d/dr) ^j V _L(r) · (Λ⁺?V _L(r))^?1=O(r ^jδ) asr → ∞,j=1, ..., 2k. (c) ∫ _r0 ^∞ dr|V _L(r|^1/2 dr|V _L(r)|^1/2=∞. (d) (d/dr)V _L(r)≦0. Under these assumptions a limiting absorption principle forR(z)=(H?z)^?1 is established. More specifically, ifK ?C ⁺={zImz≧0} is compact andK ∩ (?∞, Λ]=Ø thenR (z) can be extended as a continuous map ofK intoB (Y, Y*) (with the uniform operator topology), whereY ?L ²(R ⁿ) is a weighted-L ² space. To ensure uniqueness of solutions of (H?z)u=f, z ∈K, a suitable radiation condition is introduced.     

Additive maps derivable or Jordan derivable at zero point on nest algebras

Let AlgN be a nest algebra associated with the nest N on a (real or complex) Banach space X. Assume that every N∈N is complemented whenever N_-=N. Let δ:AlgN→AlgN be an additive map. It is shown that the following three conditions are equivalent: (1) δ is derivable at zero point, i.e., δ(AB)=δ(A)B+Aδ(B) whenever AB=0; (2) δ is Jordan derivable at zero point, i.e., δ(AB+BA)=δ(A)B+Aδ(B)+Bδ(A)+δ(B)A whenever AB+BA=0; (3) δ has the form δ(A)=τ(A)+cA for some additive derivation τ and some scalar c. It is also shown that δ is generalized derivable at zero point, i.e., δ(AB)=δ(A)B+Aδ(B)-Aδ(I)B whenever AB=0, if and only if δ is an additive generalized derivation. Finer characterizations of above maps are given for the case dimX=∞.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Ultracritical and hypercritical binary structures

A binary structure is an arc-coloured complete digraph, without loops, and with exactly two coloured arcs (u,v) and (v,u) between distinct vertices u and v. Graphs, digraphs and partial orders are all examples of binary structures. Let B be a binary structure. With each subset W of the vertex set V(B) of B we associate the binary substructure B[W] of B induced by W. A subset C of V(B) is a clan of B if for any c,d∈C and v∈V(B)?C, the arcs (c,v) and (d,v) share the same colour and similarly for (v,c) and (v,d). For instance, the vertex set V(B), the empty set and any singleton subset of V(B) are clans of B. They are called the trivial clans of B. A binary structure is primitive if all its clans are trivial.With a primitive and infinite binary structure B we associate a criticality digraph (in the sense of [11]) defined on V(B) as follows. Given v≠w∈V(B), (v,w) is an arc of the criticality digraph of B if v belongs to a non-trivial clan of B[V(B)?{w}]. A primitive and infinite binary structure B is finitely critical if B[V(B)?F] is not primitive for each finite and non-empty subset F of V(B). A finitely critical binary structure B is hypercritical if for every v∈V(B), B[V(B)?{v}] admits a non-trivial clan C such that |V(B)?C|≥3 which contains every non-trivial clan of B[V(B)?{v}]. A hypercritical binary structure is ultracritical whenever its criticality digraph is connected.The ultracritical binary structures are studied from their criticality digraphs. Then a characterization of the non-ultracritical but hypercritical binary structures is obtained, using the generalized quotient construction originally introduced in [1].     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

Berezin kernels and analysis on Makarevich spaces

Following ideas of van Dijk and Hille we study the link which exists between maximal degenerate representations and Berezin kernels.We consider the conformal group Conf(V) of a simple real Jordan algebra V. The maximal degenerate representations π_s (s ε ℂ) we shall study are induced by a character of a maximal parabolic subgroup P¯ of Conf(V). These representations π_s can be realized on a space I_s of smooth functions on V. There is an invariant bilinear form ℬ_s on the space Is. The problem we consider is to diagonalize this bilinear form ℬ_s, with respect to the action of a symmetric subgroup G of the conformal group Conf(V). This bilinear form can be written as an integral involving the Berezin kernel B_v an invariant kernel on the Riemannian symmetric space G/K, which is a Makarevich symmetric space in the sense of Bertram. Then we can use results by van Dijk and Pevzner who computed the spherical Fourier transform of B_v. From these, one deduces that the Berezin kernel satisfies a remarkable Bernstein identity: D(_ν)B_ν=b(ν)B_ν+1, where D(_ν) is an invariant differential operator on G/K and b(ν) is a polynomial. By using this identity we compute a Hua type integral which gives the normalizing factor for an intertwining operator from I_−s to I_s. Furthermore, we obtain the diagonalization of the invariant bilinear form with respect to the action of the maximal compact group U of the conformal group Conf(V).     

Domination with exponential decay

Let G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define if v⁄∈S, and w_S(v)=2 if v∈S. If, for each v∈V(G), we have w_S(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γ_e(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γ_e(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then .     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

Precoloring extension for 2-connected graphs with maximum degree three

Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K₄ then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Doubly nonlinear evolution equations governed by time-dependent subdifferentials in reflexive Banach spaces

We prove the existence of solutions of the Cauchy problem for the doubly nonlinear evolution equation: dv(t)/dt+V_∂φt(u(t))∋f(t), v(t)∈H_∂ψ(u(t)), 0<t<T, where H_∂ψ (respectively, V_∂φt) denotes the subdifferential operator of a proper lower semicontinuous functional ψ (respectively, φt explicitly depending on t) from a Hilbert space H (respectively, reflexive Banach space V) into (−∞,+∞] and f is given. To do so, we suppose that V?H≡H^∗?V^∗ compactly and densely, and we also assume smoothness in t, boundedness and coercivity of φt in an appropriate sense, but use neither strong monotonicity nor boundedness of H_∂ψ. The method of our proof relies on approximation problems in H and a couple of energy inequalities. We also treat the initial-boundary value problem of a non-autonomous degenerate elliptic-parabolic problem.     

Jordan zero-product preserving additive maps on operator algebras

Let Φ:A→B be an additive surjective map between some operator algebras such that AB+BA=0 implies Φ(A)Φ(B)+Φ(B)Φ(A)=0. We show that, under some mild conditions, Φ is a Jordan homomorphism multiplied by a central element. Such operator algebras include von Neumann algebras, C^∗-algebras and standard operator algebras, etc. Particularly, if H and K are infinite-dimensional (real or complex) Hilbert spaces and A=B(H) and B=B(K), then there exists a nonzero scalar c and an invertible linear or conjugate-linear operator U:H→K such that either Φ(A)=cUAU⁻¹ for all A∈B(H), or Φ(A)=cUA^∗U⁻¹ for all A∈B(H).     

Rank one operators and norm of elementary operators

Let A be a standard operator algebra acting on a (real or complex) normed space E. For two n-tuples A = (A₁, … , A_n) and B = (B₁, … , B_n) of elements in A, we define the elementary operator R_A,B on A by the relation for all X in A. For a single operator A∈A, we define the two particular elementary operators L_A and R_A on A by L_A(X) = AX and R_A(X) = XA, for every X in A. We denote by d(R_A,B) the supremum of the norm of R_A,B(X) over all unit rank one operators on E. In this note, we shall characterize: (i) the supremun d(R_A,B), (ii) the relation , (iii) the relation d(L_A − R_B) = ∥A∥ + ∥B∥, (iv) the relation d(L_AR_B − L_BR_A) = 2∥A∥ + ∥B∥. Moreover, we shall show the lower estimate d(L_A − R_B) ? max{sup_λ∈V(B)∥A − λI∥, sup_λ∈V(A)∥B − λI∥} (where V(X) is the algebraic numerical range of X in A).     

Schauder estimates for a class of second order elliptic operators on a cube

We consider a class of second order elliptic operators on a d-dimensional cube S_d. We prove that if the coefficients are of class C^k+δ(S_d), with k=0,1 and δ∈(0,1), then the corresponding elliptic problem admits a unique solution u belonging to C^k+2+δ(S_d) and satisfying non-standard boundary conditions involving only second order derivatives.     

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E), a family W of sets W⊆V of vertices (areas), and a requirement function r:W→Z⁺ (where Z⁺ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1 for each W∈W, and polynomially solvable in the uniform case of r(W)=r?2 for each W∈W. In this paper, we show that the problem can be solved in time, even if r(W)?2 holds for each W∈W, where n=|V|, m=|{{u,v}|(u,v)∈E}|, p=|W|, and r^*=max{r(W)∣W∈W}.