On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

On conditional edge-connectivity of graphs

1. IntroductionIn this paper, a graph G ~ (V,E) always means a simple graph (without loops andmultiple edges) with the vertex-set V and the edge-set E. We follow [1] for graph-theoreticalterllilnology and notation not defined here.It is well known that when the underlying topology of a computer interconnectionnetwork is modeled by a graph G, the edge-connectivity A(G) of G is an important measurefor fault-tolerance of the network. However, it has many deficiencies (see [2]). MotiVatedby t…     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

Degree Sums,Connectivity and Dominating Cycles in Graphs

Let G be a graph of order n with connectivity κ≥3 and let α be the independence number of G. Set σ₄(G)= min{∑⁴ _{i =1} d(x _i ):{x ₁,x ₂,x ₃,x ₄} is an independent set of G}. In this paper, we will prove that if σ₄(G)≥n+2κ, then there exists a longest cycle C of G such that V(G−C) is an independent set of G. Furthermore, if the minimum degree of G is at least α, then G is hamiltonian. Received: July 31, 1998?Final version received: October 4, 2000     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

Discrete spectrum in the gaps of a perturbed pseudorelativistic hamiltonian

The pseudorelativistic Hamiltonian is considered under wide conditions on potentials A(x), W(x). It is assumed that a real point λ is regular for G_1/2. Let G_1/2(α)=G_1/2−αV, where α>0, V(x)≥0, and V ∈L _d(ℝ^d). Denote by N(λ, α) the number of eigenvalues of G_1/2(t) that cross the point λ as t increases from 0 to α. A Weyl-type asymptotics is obtained for N(λ, α) as α→∞. Bibliography: 5 titles. To O. A. Ladyzhenskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 249, 1997. pp. 102–117. Translated by A. B. Pushnitskii.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

On the restricted arc-connectivity of s-geodetic digraphs

For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

On simple modules of Hecke algebras of type Dn

This is a continuation of our previous work. We classify all the simple ℋ_q(D _n )-modules via an automorphismh defined on the set { λ | D^λ ≠ 0}. Whenf _n(q) ≠ 0, this yields a classification of all the simple ℋ ^q (D _n)- modules for arbitrary n. In general ( i. e., q arbitrary), if λ⁽¹⁾ = λ⁽²⁾,wegivea necessary and sufficient condition ( in terms of some polynomials ) to ensure that the irreducible ℋ_q,1(B _n )- module D^λ remains irreducible on restriction to ℋ_q(D _n ).     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

3-restricted connectivity of graphs with given girth

Let G = （V, E） be a connected graph. X belong to V（G） is a vertex set. X is a 3-restricted cut of G, if G- X is not connected and every component of G- X has at least three vertices. The 3-restricted connectivity κ3（G） （in short κ3） of G is the cardinality of a minimum 3-restricted cut of G. X is called κ3-cut, if ｜X｜ = κ3. A graph G is κ3-connected, if a 3-restricted cut exists. Let G be a graph girth g ≥ 4, κ3（G） is min{d（x） ＋ d（y） ＋ d（z） - 4 ： xyz is a 2-path of G}. It will be shown that κ3（G） = ξ3（G） under the condition of girth.     

Exponential decay rate of survival probability in a disastrous random environment

Summary. We study the exponential decay rate of the survival probability up to time t>0 of a random walker moving in Zopf; ^d in a temporally and spatially fluctuating random environment. When the random walker has a speed parameter κ>0, we investigate the influence of κ on the exponential decay rate λ(d,κ). In particular we prove that for any fixed d≥1, λ(d,κ) behaves like as logκ as κ↘0. Received: 21 May 1996 / In revised form: 2 February 1997     

Hadwiger number and chromatic number for near regular degree sequences

We consider a problem related to Hadwiger's Conjecture. Let D=(d₁, d₂, …, d_n) be a graphic sequence with 0?d₁?d₂?···?d_n?n?1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D)=max{h(G): G∈R[D]} and χ(D)=max{χ(G): G∈R[D]}, where h(G) and χ(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger's Conjecture implies that h(D)?χ(D). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175–183, 2010     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimization problems of the third edge-connectivity of graphs

The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.     

A Lower Bound for the Norm of the Minimal Residual Polynomial

Let S be a compact infinite set in the complex plane with 0∉S, and let R _n be the minimal residual polynomial on S, i.e., the minimal polynomial of degree at most n on S with respect to the supremum norm provided that R _n (0)=1. For the norm L _n (S) of the minimal residual polynomial, the limit k(S):=lim_n?￥ⁿ?{L_n(S)}\kappa(S):=\lim_{n\to\infty}\sqrt[n]{L_{n}(S)} exists. In addition to the well-known and widely referenced inequality L _n (S)≥κ(S) ⁿ , we derive the sharper inequality L _n (S)≥2κ(S) ⁿ /(1+κ(S)²ⁿ ) in the case that S is the union of a finite number of real intervals. As a consequence, we obtain a slight refinement of the Bernstein–Walsh lemma.