Edge-connectivity and edge-disjoint spanning trees

Given a graph G, for an integer c∈{2,…,|V(G)|}, define λ_c(G)=min{|X|:X⊆E(G),ω(G−X)≥c}. For a graph G and for an integer c=1,2,…,|V(G)|−1, define,

     

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.     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

Degree-bounded factorizations of bipartite multigraphs and of pseudographs

For d≥1, s≥0 a (d,d+s)-graph is a graph whose degrees all lie in the interval {d,d+1,…,d+s}. For r≥1, a≥0 an (r,r+a)-factor of a graph G is a spanning (r,r+a)-subgraph of G. An (r,r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r,r+a)-factors. A graph is (r,r+a)-factorable if it has an (r,r+a)-factorization.We prove a number of results about (r,r+a)-factorizations of (d,d+s)-bipartite multigraphs and of (d,d+s)-pseudographs (multigraphs with loops permitted). For example, for t≥1 let β(r,s,a,t) be the least integer such that, if d≥β(r,s,a,t) then every (d,d+s)-bipartite multigraph G is (r,r+a)-factorable with x(r,r+a)-factors for at least t different values of x. Then we show that

     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

The multiple originator broadcasting problem in graphs

Given a graph G and a vertex subset S of V(G), the broadcasting time with respect toS, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by b_k(G), is defined by b_k(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph G and two vertex subsets S, S^′ of V(G), define , d(S,S^′)=min{d(u,v)|u∈S, v∈S^′}, and for all v∈V(G). For all k, 1?k?|V(G)|, the k-radius of G, denoted by r_k(G), is defined as r_k(G)=min{d(G,S)|S⊆V(G), |S|=k}.In this paper, we study the relation between the k-radius and the k-broadcasting numbers of graphs. We also give the 2-radius and the 2-broadcasting numbers of the grid graphs, and the k-broadcasting numbers of the complete n-partite graphs and the hypercubes.     

Boundedness of singular integral operators with variable kernels

Let K be a generalized Calderón-Zygmund kernel defined on Rn×(Rn?{0}). The singular integral operator with variable kernel given by

     

On a Sobolev-type inequality related to the weighted p-Laplace operator

In this paper we deal with some Sobolev-type inequalities with weights that were proved by Maz'ya in [V.G. Maz'ja, Sobolev Spaces, Springer-Verlag, Berlin, 1980] and by Caffarelli, Kohn and Nirenberg in [L. Caffarelli, R. Kohn, L. Nirenberg, First order interpolation inequalities with weight, Compos. Math. 53 (1984) 259-275]. For integers 1?k?N denote points ξ∈RN=Rk×RN−k as pairs (x,y). Let p∈(1,N), q∈(p,p^∗] and assume . Then there exists c>0 such that

     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Decomposition rank and absorbing extensions of type I algebras

We prove the following: Let A and B be separable C^*-algebras. Suppose that B is a type I C^*-algebra such that

(i)

B has only infinite dimensional irreducible *-representations, and

(ii)

B has finite decomposition rank.

If

0→B→C→A→0     

Matrix refinement type equations

Taking advantage of perpetuities and the asymptotic behavior of products of random matrices we obtain the direct form of the Fourier transform of an L¹-solution of the following random matrix refinement type equation

f(x)=_∫Ω|detL(ω)|C(ω)f(L(ω)x-M(ω))P(dω),     

Mapping properties for oscillatory integrals in d-dimensions

For aj,bj?1, j=1,2,…,d, we prove that the operator maps into itself for , where , and k(x,y)=φ(x,y)eig(x,y), φ(x,y) satisfies (1.2) (e.g. φ(x,y)=|x−y|^iτ,τ real) and the phase g(x,y)=xa⋅yb. We study operators with more general phases and for these operators we require that aj,bj>1, j=1,2,…,d, or al=bl?1 for some l∈{1,2,…,d}.     

Endomorphisms of the shift dynamical system, discrete derivatives, and applications

All continuous endomorphisms f_∞ of the shift dynamical system S on the 2-adic integers Z₂ are induced by some , where n is a positive integer, B_n is the set of n-blocks over {0, 1}, and f_∞(x)=y₀y₁y₂… where for all i∈N, y_i=f(x_ix_i+1…x_i+n−1). Define D:Z₂→Z₂ to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z₂→Z₂ by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z₂→Z₂ to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any m∈Z⁺, there exists some n∈N such that R⁻¹(m) has binary representation of the form or .     

An extension of the Vu-Sine theorem and compact-supercyclicity

If (Tt)_t?0 is a bounded C₀-semigroup in a Banach space X and there exists a compact subset K⊆X such that

     

Turán’s theorem inverted

In this note we complete an investigation started by Erd?s in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let be the complete r-partite graph with parts of sizes s₁≥2,s₂,…,s_r with an edge added to the first part. Letting t_r(n) be the number of edges of the r-partite Turán graph of order n, we prove that:For all r≥2 and all sufficiently small c>0, every graph of sufficiently large order n with t_r(n)+1 edges contains a .We also give a corresponding stability theorem and two supporting results of wider scope.     

Nonlinear dissipative wave equations with space-time dependent potential

We study the long time behavior of solutions for damped wave equations with absorption. These equations are generally accepted as models of wave propagation in heterogeneous media with space-time dependent friction a(t,x)u_t and nonlinear absorption |u|^p−1u (Ikawa (2000) [17]). We consider 1<p<(n+2)/(n−2) and separable a(t,x)=λ(x)η(t) with λ(x)∼(1+|x|)^−α and η(t)∼(1+t)^−β satisfying conditions (A1) or (A2) which are given. The main results are precise decay estimates for the energy, L² and L^p+1 norms of solutions. We also observe the following behavior: if α∈[0,1), β∈(−1,1) and 0<α+β<1, there are three different regions for the decay of solutions depending on p; if α∈(−∞,0) and β∈(−1,1), there are only two different regions for the decay of the solutions depending on p.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.     

Spectral conditions for admissibility of evolution equations in Hilbert space

We study properties of solutions of the evolution equation , where B is a closable operator on the space AP(R,H) of almost periodic functions with values in a Hilbert space H such that B commutes with translations. The operator B generates a family of closed operators on H such that (whenever eiλtx∈D(B)). For a closed subset Λ⊂R, we prove that the following properties (i) and (ii) are equivalent: (i) for every function f∈AP(R,H) such that σ(f)⊆Λ, there exists a unique mild solution u∈AP(R,H) of Eq. (∗) such that σ(u)⊆Λ; (ii) is invertible for all λ∈Λ and .