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

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

On the Existence of a Long Path Between Specified Vertices in a 2-Connected Graph

 Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d _G(u), d _G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d _G(u,v)=2. Then x and y are connected by a path of length at least d−|W|. Received: February 5, 1998 Revised: April 13, 1998     

Simultaneous determination of source terms in a linear parabolic problem from the final overdetermination: Weak solution approach

The problem of determining the pair w:={F(x,t);T₀(t)} of source terms in the parabolic equation u_t=(k(x)u_x)_x+F(x,t) and Robin boundary condition −k(l)u_x(l,t)=v[u(l,t)−T₀(t)] from the measured final data μ_T(x)=u(x,T) is formulated. It is proved that both components of the Fréchet gradient of the cost functional can be found via the same solution of the adjoint parabolic problem. Lipschitz continuity of the gradient is derived. The obtained results permit one to prove existence of a quasi-solution of the considered inverse problem, as well as to construct a monotone iteration scheme based on a gradient method.     

A distance approximating trees

A 1-approximation of connected graph G=(V,E) is a tree T=(V,E^′) with the same vertex set such that for every two vertices |d_G(u,v)−d_T(u,v)|1. A polynomial time algorithm is designed for finding such a tree.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

On local connectivity of graphs with given clique number

For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010     

Special Uniform Approximations of Continuous Vector-Valued Functions. Part I: Special Approximations in CX(T)

In this paper, we give special uniform approximations of functions u from the spaces C_X(T) and C_∞(T,X), with elements of the tensor products C_Γ(T)X, respectively C₀(T,Γ)X, for a topological space T and a Γ-locally convex space X. We call an approximation special, if satisfies additional constraints, namely supp vu⁻¹(X\{0}) and (T) co(u(T)) (resp. co(u(T){0})). In Section 3, we give three distinct applications, which are due exactly to these constraints: a density result with respect to the inductive limit topology, a Tietze–Dugundji's type extension new theorem and a proof of Schauder–Tihonov's fixed point theorem.