Weak-Geodetically Closed Subgraphs in Distance-Regular Graphs

 Let Γ=(X,R) denote a distance-regular graph with diameter D≥2 and distance function δ. A (vertex) subgraph Ω⊆X is said to be weak-geodetically closed whenever for all x,y∈Ω and all z∈X,

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1 and <Emphasis Type="Italic">a</Emphasis><Subscript>1</Subscript> = 0 < <Emphasis Type="Italic">a</Emphasis><Subscript>2</Subscript>

Let Γ be a distance-regular graph of diameter d ≥ 3 with c ₂ > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:

Strongly Closed Subgraphs in a Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1

Let Γ be a distance-regular graph of diameter d ≥ 3 with c ₂ > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:

A Fan Type Condition For Heavy Cycles in Weighted Graphs

 A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d ^w (v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. max{d ^w (x),d ^w (y)∣d(x,y)=2}≥c/2; 2. w(x z)=w(y z) for every vertex z∈N(x)∩N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result. Received: February 7, 2000 Final version received: June 5, 2001     

Spectral Characterization of Some Generalized Odd Graphs

Suppose G is a connected, k-regular graph such that Spec(G)=Spec(Γ) where Γ is a distance-regular graph of diameter d with parameters a ₁=a ₂=⋯=a _d−1=0 and a _d>0; i.e., a generalized odd graph, we show that G must be distance-regular with the same intersection array as that of Γ in terms of the notion of Hoffman Polynomials. Furthermore, G is isomorphic to Γ if Γ is one of the odd polygon C _2d+1, the Odd graph O _d+1, the folded (2d+1)-cube, the coset graph of binary Golay code (d=3), the Hoffman-Singleton graph (d=2), the Gewirtz graph (d=2), the Higman-Sims graph (d=2), or the second subconstituent of the Higman-Sims graph (d=2). Received: March 28, 1996 / Revised: October 20, 1997     

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.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Equations fonctionnelles et estimations de normes de matrices

We solve independently the equations 1/θ(x)θ(y)=ψ(x)−ψ(y)+φ(x−y)/θ(x−y) and 1/θ(x)θ(y)=σ(x)−σ(y)/θ(x−y)+τ(x)τ(y), τ(0)=0. In both cases we find θ²=aθ⁴+bθ²+c. We deduce estimates for the spectral radius of a matrix of type(1/θ(x _r −x _s )) (the accent meaning that the coefficients of the main diagonal are zero) and we study the case where thex _r are equidistant.

Dédié to à Monsieur le Professeur Otto Haupt à l'occasion de son cententiare avec les meilleurs voeux     

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     

A Higman inequality for regular near polygons

The inequality of Higman for generalized quadrangles of order (s,t) with s>1 states that t≤s ². We generalize this by proving that the intersection number c _i of a regular near 2d-gon of order (s,t) with s>1 satisfies the tight bound c _i ≤(s ²ⁱ −1)/(s ²−1), and we give properties in case of equality. It is known that hemisystems in generalized quadrangles meeting the Higman bound induce strongly regular subgraphs. We also generalize this by proving that a similar subset in regular near 2d-gons meeting the bounds would induce a distance-regular graph with classical parameters (d,b,α,β)=(d,−q,−(q+1)/2,−((−q) ^d +1)/2) with q an odd prime power.     

拟圆周的两个几何性质

§1　IntroductionLetΓbe a Jordan curve of R2 and f∶R2→R2 be a k-quasiconformal mapping,where1≤k<+∞.Γis called a quasicirlce ifΓis the image of the unit circle B2 under f.It is well-known that quasicircles play a very important role in quasiconformalmapping theory,complex dynamics,Fuchsian groups,Teichmuller space theory and lowdimensional topology,( see[1—5] etc.)In1 963 ,Ahlfors obtained the three-point property of quasidisks[6] .Later,Gehring[7] ,Osgood[8] ,Krzyz[9] ,Ch…     

Reciprocal polynomials with all zeros on the unit circle

Let f(x)=a _d x ^d +a _d−1 x ^d−1+⋅⋅⋅+a ₀∈ℝ[x] be a reciprocal polynomial of degree d. We prove that if the coefficient vector (a _d ,a _d−1,…,a ₀) or (a _d−1,a _d−2,…,a ₁) is close enough, in the l ¹-distance, to the constant vector (b,b,…,b)∈ℝ ^d+1 or ℝ ^d−1, then all of its zeros have moduli 1.     

Asymptotic behaviour of a Brownian motion on exterior domains

We study the asymptotic behaviour of the transition density of a Brownian motion in ?, killed at ∂?, where ? ^c is a compact non polar set. Our main result concern dimension d = 2, where we show that the transition density p ^? _t (x, y) behaves, for large t, as u(x)u(y)(t(log t)²)⁻¹ for x, y∈?, where u is the unique positive harmonic function vanishing on (∂?) ^r , such that u(x) ∼ log ∣x∣. Received: 29 January 1999 / Revised version: 11 May 1999     

Pseudo 1-homogeneous distance-regular graphs

Let Γ be a distance-regular graph of diameter d≥2 and a ₁≠0. Let θ be a real number. A pseudo cosine sequence for θ is a sequence of real numbers σ ₀,…,σ _d such that σ ₀=1 and c _i σ _i−1+a _i σ _i +b _i σ _i+1=θ σ _i for all i∈{0,…,d−1}. Furthermore, a pseudo primitive idempotent for θ is E _θ =s ∑ _i=0 ^d σ _i A _i , where s is any nonzero scalar. Let be the characteristic vector of a vertex v∈VΓ. For an edge xy of Γ and the characteristic vector w of the set of common neighbours of x and y, we say that the edge xy is tight with respect to θ whenever θ≠k and a nontrivial linear combination of vectors , and Ew is contained in . When an edge of Γ is tight with respect to two distinct real numbers, a parameterization with d+1 parameters of the members of the intersection array of Γ is given (using the pseudo cosines σ ₁,…,σ _d , and an auxiliary parameter ε). Let S be the set of all the vertices of Γ that are not at distance d from both vertices x and y that are adjacent. The graph Γ is pseudo 1-homogeneous with respect to xy whenever the distance partition of S corresponding to the distances from x and y is equitable in the subgraph induced on S. We show Γ is pseudo 1-homogeneous with respect to the edge xy if and only if the edge xy is tight with respect to two distinct real numbers. Finally, let us fix a vertex x of Γ. Then the graph Γ is pseudo 1-homogeneous with respect to any edge xy, and the local graph of x is connected if and only if there is the above parameterization with d+1 parameters σ ₁,…,σ _d ,ε and the local graph of x is strongly regular with nontrivial eigenvalues a ₁ σ/(1+σ) and (σ ₂−1)/(σ−σ ₂).     

Correlation structure of intermittency in the parabolic Anderson model

Consider the Cauchy problem ∂u(x, t)/∂t = ℋu(x, t) (x∈ℤ^d, t≥ 0) with initial condition u(x, 0) ≡ 1 and with ℋ the Anderson Hamiltonian ℋ = κΔ + ξ. Here Δ is the discrete Laplacian, κ∈ (0, ∞) is a diffusion constant, and ξ = {ξ(x): x∈ℤ ^d } is an i.i.d.random field taking values in ℝ. G?rtner and Molchanov (1990) have shown that if the law of ξ(0) is nondegenerate, then the solution u is asymptotically intermittent. In the present paper we study the structure of the intermittent peaks for the special case where the law of ξ(0) is (in the vicinity of) the double exponential Prob(ξ(0) > s) = exp[−e ^{s /θ}] (s∈ℝ). Here θ∈ (0, ∞) is a parameter that can be thought of as measuring the degree of disorder in the ξ-field. Our main result is that, for fixed x, y∈ℤ ^d and t→∈, the correlation coefficient of u(x, t) and u(y, t) converges to ∥w _ρ∥⁻² _ℓ2Σ_{z ∈ℤd} w _ρ(x+z)w _ρ(y+z). In this expression, ρ = θ/κ while w _ρ:ℤ^d→ℝ⁺ is given by w _ρ = (v _ρ)^{⊗ d} with v _ρ: ℤ→ℝ⁺ the unique centered ground state (i.e., the solution in ℓ²(ℤ) with minimal l ²-norm) of the 1-dimensional nonlinear equation Δv + 2ρv log v = 0. The uniqueness of the ground state is actually proved only for large ρ, but is conjectured to hold for any ρ∈ (0, ∞). empty It turns out that if the right tail of the law of ξ(0) is thicker (or thinner) than the double exponential, then the correlation coefficient of u(x, t) and u(y, t) converges to δ _{x, y} (resp.the constant function 1). Thus, the double exponential family is the critical class exhibiting a nondegenerate correlation structure. Received: 5 March 1997 / Revised version: 21 September 1998     

Delsarte Set Graphs with Small c 2

Let Γ be a Delsarte set graph with an intersection number c ₂ (i.e., a distance-regular graph with a set ${\mathcal{C}}Let Γ be a Delsarte set graph with an intersection number c ₂ (i.e., a distance-regular graph with a set C{\mathcal{C}} of Delsarte cliques such that each edge lies in a positive constant number n_C{n_{\mathcal{C}}} of Delsarte cliques in C{\mathcal{C}}). We showed in Bang et al. (J Combin 28:501–506, 2007) that if ψ ₁ > 1 then c ₂ ≥ 2 ψ ₁ where y₁:=|G₁(x)?C |{\psi_1:=|\Gamma_1(x)\cap C |} for x ? V(G){x\in V(\Gamma)} and C a Delsarte clique satisfying d(x, C) = 1. In this paper, we classify Γ with the case c ₂ = 2ψ ₁ > 2. As a consequence of this result, we show that if c ₂ ≤ 5 and ψ ₁ > 1 then Γ is either a Johnson graph or a folded Johnson graph [`(J)](4s,2s){\overline{J}(4s,2s)} with s ≥ 3.     

A functional equation originating from quadratic forms

In this paper, we obtain the general solution and the stability of the 2-variable quadratic functional equation

f(x+y,z+w)+f(x−y,z−w)=2f(x,z)+2f(y,w).     

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

 Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ₄(G)=min{d(x ₁)+d(x ₂)+ d(x ₃)+d(x ₄) | {x ₁,…,x ₄} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ₄(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002