On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

The Virtual Poincaré Polynomials of Homogeneous Spaces

We factor the virtual Poincaré polynomial of every homogeneous space G/H, where G is a complex connected linear algebraic group and H is an algebraic subgroup, as t^2u (t²–1)^r Q_G/H(t²) for a polynomial Q_G/H with nonnegative integer coefficients. Moreover, we show that Q_G/H(t²) divides the virtual Poincaré polynomial of every regular embedding of G/H, if H is connected.     

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.     

Nonlinear parabolic equations with p-growth and unbounded data

The purpose of this paper is to prove the existence of a solution for a nonlinear parabolic equation in the form u_t - div(a(t, x, u, Du)) = H(t, x, u, Du) - div(g(t, x)) in Q_T =]0,T[×Ω, Ω ⊂ R^N, with an initial condition u(0) = u₀, where u₀ is not bounded, |H(t,x, u, ξ)⩽ β|ξ|^p + f(t,x) + βe^λ₁^|u|f, |g|^p/(p-1) ∈ L^r(Q_T) for some r = r{N) ⩾ 1, and - div(a(t,x,u, Du)) is the usual Leray-Lions operator.     

The Dichotomy Theorem for evolution bi-families

We prove that the operator G, the closure of the first-order differential operator −d/dt+D(t) on L₂(R,X), is Fredholm if and only if the not well-posed equation u^′(t)=D(t)u(t), t∈R, has exponential dichotomies on R₊ and R₋ and the ranges of the dichotomy projections form a Fredholm pair; moreover, the index of this pair is equal to the Fredholm index of G. Here X is a Hilbert space, D(t)=A+B(t), A is the generator of a bi-semigroup, B(⋅) is a bounded piecewise strongly continuous operator-valued function. Also, we prove some perturbations results and consider various examples of not well-posed problems.     

Rate of convergence in a class of singular perturbations

Let V_?, W_?, W and X be Hilbert spaces (0 < ? ? 1) with V_? ? W_? ? W ? X algebraically and topologically, each space being dense in the one that follows it. For each t? [0, T] let a_?(t; u, v), b_?(t; u, v) and b(t; u, v) be continuous sesqui-linear forms on V_?, W_? and W, respectively, which satisfy certain ellipticity conditions. Consider the two equations a_?(t; u_?, v) + b_?(t; u_?, v) = 〈f_?, v〉 (v?V_?) and (u′, v)_x + b(t; u, v) = 〈f, v〉 (v?W). Estimates are obtained on the rate of convergence of u_? to u, assuming a_?(t; u, v) → (u, v)_x and b_?(t; u, v) → b(t; u, v) in an appropriate sense. These results are then applied to singular perturbation of a class of parabolic boundary value problems.     

Strong homology and dimension

We show that strong homology groups H̄_p(X; G) of a space X vanish if p is greater than the shape dimension sd X. For p=sd X, H̄_p(X; G) coincides with the Čech homology groups Ȟ_p(X; G). We also show that there exist 1-dimensional spaces, which do not admit 1-dimensional ANR-resolutions. Therefore, the vanishing of H̄_p(X; G) for p>dim X is a nontrivial fact.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Stability of the Absolutely Continuous Spectrum of Random Schrödinger Operators on Tree Graphs

According to the Smolukowski-Kramers approximation, we show that the solution of the semi-linear stochastic damped wave equations μ u _tt (t,x)=Δu(t,x)?u _t (t,x)+b(x,u(t,x))+Q (t),u(0)=u ₀, u _t (0)=v ₀, endowed with Dirichlet boundary conditions, converges as μ goes to zero to the solution of the semi-linear stochastic heat equation u _t (t,x)=Δ u(t,x)+b(x,u(t,x))+Q (t),u(0)=u ₀, endowed with Dirichlet boundary conditions. Moreover we consider relations between asymptotics for the heat and for the wave equation. More precisely we show that in the gradient case the invariant measure of the heat equation coincides with the stationary distributions of the wave equation, for any μ>0.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

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.     

Stability of solutions bifurcating from multiple eigenvalues

Let X and Y be real Banach spaces and G:X × $\text{R}$ be a twice continuously differentiate function which is not necessarily linear. Suppose G(u₀, α₀) = 0 and the dimension of the null space of G_u(u₀, α₀) is m, where 1 ? m < ∞. Usually, S = {(u, α):G(u, α) = 0}, in a neighborhood of (u₀, α₀), consists of a finite number of curves emanating from (u₀, α₀). We will determine the stability of points, (u, α), in S (i.e., the maximum of the real parts of the spectrum of G_u(u, α) for each (u, α) ∈ S) using a general perturbation theorem of Kato. Our results contain as a special case the stability theorems of Crandall and Rabinowitz for the case m = 1. We will also tie our stability theorems together with some bifurcation results of Decker and Keller. Finally we apply our results to systems of reaction diffusion equations.     

Classes of matrices associated with the optimal assignment problem

Let E=[e_ij] be a matrix with integral elements, and let x be an indeterminate defined over the rational field Q. We investigate matrices of the form X=[x^e_ij] (i = 1,…, m; j = 1,…, n; m ⩽ n). We may multiply the lines (rows or columns) of the matrix X by suitable integral powers of x in various ways and thereby transform X into a matrix Y=[x^f_ij] such that the f_ij are nonnegative integers and each line of Y contains at least one element x⁰ = 1. We call Y a normalized form of X, and we denote by S(X) the class of all normalized forms associated with a given matrix X. The classes S(X) have a fascinating combinatorial structure, and the present paper is a natural outgrowth and extension of an earlier study. We introduce new concepts such as an elementary transformation called an interchange. We prove, for example, that two matrices in the same class are transformable into one another by interchanges. Our analysis of the class S(X) also yields new insights into the structure of the optimal assignments of the matrix E by way of the diagonal products of the matrix X.     

Existence and asymptotic behavior of a functional differential equation in Banach space

Existence and asymptotic behavior of solutions are given for the equation u′(t) = ?A(t)u(t) + F(t,u_t) (t ? 0) and u₀ = ? ? C([?r,0]; X)  C. The space X is a Banach space; the family $\text{{A(t) ¦ 0 ? t ? T}}$ of unbounded linear operators defined on D(A) ? X → X generates a linear evolution system and F: C → X is continuous with respect to a fractional power of A(t₀) for some t₀ ? [0, T].     

Excursions above high levels by Gaussian random fields

For a two-dimensional, homogeneous, Gaussian random field X(t) and compact, convex S ? R² we show that as u → ∞ the set A_u = {t ∈ S : X(t) ? u} possesses, with probabilityapproaching one, components that are approximately convex. Furthermore, the function X is also approximately concave over A_u. One of the main aims of the paper is, at the cost of losing some detail, to simplify the analytic complexity of previous results about high level excursions of Gaussian fields by judicious use of concepts from integral and differential geometry.     

The evaluation subgroup of a fibre inclusion

Let be a fibration of simply connected CW complexes of finite type with classifying map . We study the evaluation subgroup Gn(E,X;j) of the fibre inclusion as an invariant of the fibre-homotopy type of ξ. For spherical fibrations, we show the evaluation subgroup may be expressed as an extension of the Gottlieb group of the fibre sphere provided the classifying map h induces the trivial map on homotopy groups. We extend this result after rationalization: We show that the decomposition G_∗(E,X;j)⊗Q=(G_∗(X)⊗Q)⊕(π_∗(B)⊗Q) is equivalent to the condition Q(h_?)=0.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

Differential Harnack inequalities for heat equations with potentials under geometric flows

In the paper we consider a closed Riemannian manifold M with a time-dependent Riemannian metric g _ij (t) evolving by ? _t g _ij  = ?2S _ij , where S _ij is a symmetric two-tensor on (M,g(t)). We prove some differential Harnack inequalities for positive solutions of heat equations with potentials on (M,g(t)). Some applications of these inequalities will be obtained.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.