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     

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999     

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

Score Lists in Tripartite Hypertournaments

Given non-negative integers l, m, n, α, β and γ with l ≥ α ≥ 1, m ≥ β ≥ 1 and n ≥ γ ≥ 1, an [α,β,γ]-tripartite hypertournament on l + m + n vertices is a four tuple (U, V, W, E), where U, V and W are three sets of vertices with |U| = l , |V| = m and |W| = n, and E is a set of (α + β + γ)-tuples of vertices, called arcs, with exactly α vertices from U, exactly β vertices from V,and exactly γ vertices from W, such that any subset U₁∪ V₁∪ W₁ of U∪ V∪ W, E contains exactly one of the (α + β + γ)! (α + β + γ) − tuples whose entries belong to U₁∪ V₁∪ W₁. We obtain necessary and sufficient conditions for three lists of non-negative integers in non-decreasing order to be the losing score lists or score lists of some [α, β, γ]-tripartite hypertournament. Supported by National Science Foundation of China (No.10501021).     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

Zur Theorie der Stetigen Teilbarkeitshalbgruppen

O. CallS:=(S,·,∩) a d-semigroup ifS satisfies the axioms (A1) (S,·) is a semigroup, (A2) (S,∩) is a semilattice (A3), (S,·,∩) is a semiring, (A4) a ≤b⇒bε aS ∩ Sa. Call tεS positive if ÅaεS: ta ≥a≤at. Let S⁺ denote the set {t‖t positive}. Every d-semigroup is closed under sup and (s,·,∪) is a semiring, (S, ∩, ∪) is a distributive lattice. Denote by D□X the implication s=Xa_i⇒x□s□y=X(x□a_i□y) where □ε{·,∩,∪} and Xε{∪,∩}. CallS continuous ifS satisfies all D□X. The theory of d-semigroups (divisibility-semigroups) was established in [3], [4], [5], and is continued here by some contributions to the theory of continuous d-semigroups the main results of which are the two propositions: (1) LetS be a d-semigroup with 1. ThenS satisfies D□X iffS ⁺ satisfies this axiom. (2) LetS be continuous. Then (S,·) is commutative. Obviously Proposition (2) is an improvement of Iwasawa's theorem concerning conditionally complete lattice ordered groups.

---

Zur Theorie der Stetigen Teilbarkeitshalbgruppen

---

Klaus Wagner zum 70. Geburtstag gewidmet     

A Neighborhood Condition for Graphs to Have [a, b]-Factors II

 Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N _G (x ₁)∪⋯ ∪N _G (x _t )|≥(a|G|+2m)/(a+b) for every independent set {x ₁,…,x _t }⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292). Received: October, 2001 Final version received: September 17, 2002 RID="*" ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 13740084, 2001     

Sausages are good packings

LetB ^d be thed-dimensional unit ball and, for an integern, letC _n ={x ¹,...,x ⁿ } be a packing set forB ^d , i.e.,|x ⁱ −x ^j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C _n )+ρB ^d )≥V(conv(S _n )+ρB ^d ), whereS _n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d ⁻²,V(conv(C _n )+ρK)≥V(conv(S _n )+ρK), whereC _n is a packing set with respect toK andS _n is a minimal “sausage” arrangement ofK, holds.     

A large-deviation result for the range of random walk and for the Wiener sausage

Let {S _n } be a random walk on ℤ ^d and let R _n be the number of different points among 0, S ₁,…, S _{n −1}. We prove here that if d≥ 2, then ψ(x) := lim _{n →∞}(−:1/n) logP{R _n ≥nx} exists for x≥ 0 and establish some convexity and monotonicity properties of ψ(x). The one-dimensional case will be treated in a separate paper. We also prove a similar result for the Wiener sausage (with drift). Let B(t) be a d-dimensional Brownian motion with constant drift, and for a bounded set A⊂ℝ ^d let Λ _t = Λ _t (A) be the d-dimensional Lebesgue measure of the `sausage' ∪_{0≤ s ≤ t} (B(s) + A). Then φ(x) := lim _t→∞: (−1/t) log P{Λ _t ≥tx exists for x≥ 0 and has similar properties as ψ. Received: 20 April 2000 / Revised version: 1 September 2000 / Published online: 26 April 2001     

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x ₁, x ₂, x ₃, x ₄} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.     

On Cramer Approximations under Violation of Cramer's Condition

Let X ₁, X ₂,... be independent identically distributed random variables with distribution function F, S ₀ = 0, S _n = X ₁ + ⋯ + X _n , and Sˉ _n = max_1⩽k⩽n S _k . We obtain large-deviation theorems for S _n and Sˉ _n under the condition 1 − F(x) = P{X ₁ ⩾ x} = e^−l(x), l(x) = x ^α L(x), α ∈ (0, 1), where L(x) is a slowly varying function as x → ∞. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 447–456, October–December, 2005.     

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     

Extremal probabilities for Gaussian quadratic forms

 Denote by Q an arbitrary positive semidefinite quadratic form in centered Gaussian random variables such that E(Q)=1. We prove that for an arbitrary x>0, inf _Q P(Q≤x)=P(χ² _n /n≤x), where χ _n ² is a chi-square distributed rv with n=n(x) degrees of freedom, n(x) is a non-increasing function of x, n=1 iff x>x(1)=1.5364…, n=2 iff x[x(2),x(1)], where x(2)=1.2989…, etc., n(x)≤rank(Q). A similar statement is not true for the supremum: if 1<x<2 and Z ₁ ,Z ₂ are independent standard Gaussian rv's, then sup_0≤λ≤1/2 P{λZ ₁ ² +(1−λ)Z ₂ ² ≤x} is taken not at λ=0 or at λ=1/2 but at 0<λ=λ(x)<1/2, where λ(x) is a continuous, increasing function from λ(1)=0 to λ(2)=1/2, e.g. λ(1.5)=.15…. Applications of our theorems include asymptotic quantiles of U and V-statistics, signal detection, and stochastic orderings of integrals of squared Gaussian processes. Received: 24 June 2002 / Revised version: 26 January 2003 Published online: 15 April 2003 Research supported by NSA Grant MDA904-02-1-0091 Mathematics Subject Classification (2000): Primary 60E15, 60G15; Secondary 62G10     

Hamiltonism and Partially Square Graphs

 Given a graph G, we define its partially square graph G ^* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N _G[x]⊆N _G[u]∪N _G [v], where N _G[x]=N _G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K _1,3). Obviously G⊆G ^*⊆G ², where G ² is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G ^*) of G ^* does not exceed k. If we replace G ^* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G ^* is replaced by G ² then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G ^* for other hamiltonian properties are also given in this paper. Received: June 17, 1996 Revised: October 30, 1998     

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:

Rational points of bounded height on Del Pezzo surfaces of degree six

LetK be a number field. Denote byV ₃ a split Del Pezzo surface of degree six overK and by ω its canonical divisor. Denote byW ₃ the open complement of the exceptional lines inV ₃. LetN _{W s}(−ω, X) be the number ofK-rational points onW ₃ whose anticanonical heightH _−ω is bounded byX. Manin has conjectured that asymptoticallyN _{W 3}(−ω, X) tends tocX(logX)³, wherec is a constant depending only on the number field and on the normalization of the height. Our goal is to prove the following theorem: For each number fieldK there exists a constantc _K such thatN _{W 3}(−ω, X)≤c_KX(logX)^3+2r , wherer is the rank of the group of units ofO _K. The constantc _K is far from being optimal. However, ifK is a purely imaginary quadratic field, this proves an upper bound with a correct power of logX. The proof of Manin's conjecture for arbitrary number fields and a precise treatment of the constants would require a more sophisticated setting, like the one used by [Peyre] to prove Manin's conjecture and to compute the correct asymptotic constant (in some normalization) in the caseK=ℚ. Up to now the best result for arbitraryK goes back, as far as we know, to [Manin-Tschinkel], who gives an upper boundN _{W 3}(−ω,X)≤cX^l+ε. The author would like to express his gratitude to Daniel Coray and Per Salberger for their generous and indispensable support.     

On subgroups of the general linear group that contain a maximal nonsplit torus

The paper deals with the structure of intermediate subgroups of the general linear group GL(n, k) of degree n over a field k of odd characteristic that contain a nonsplit maximal torus related to a radical extension of degree n of the ground field k. The structure of ideal nets over a ring that determine the structure of intermediate subgroups containinga transvection is given. Let K = k( ⁿ?{d} ) K = k\left( {\sqrt[n]{d}} \right) be a radical degree-n extension of a field k of odd characteristic, and let T =(d) be a nonsplit maximal torus, which is the image of the multiplicative group of the field K under the regular embedding in G =GL(n, k). In the paper, the structure of intermediate subgroups H, T ≤ H ≤ G, that contain a transvection is studied. The elements of the matrices in the torus T = T (d) generate a subring R(d) in the field k.Let R be an intermediate subring, R(d) ⊆ R ⊆ k, d ∈ R. Let σ_R denote the net in which the ideal dR stands on the principal diagonal and above it and all entries of which beneath the principal diagonal are equal to R. Let σ^R denote the net in which all positions on the principal diagonal and beneath it are occupied by R and all entries above the principal diagonal are equal to dR. Let E(σ_R) be the subgroup generated by all transvections from the net group G(σ_R). In the paper it is proved that the product TE(σ_R) is a group (and thus an intermediate subgroup). If the net σ associated with an intermediate subgroup H coincides with σ_R,then TE(σ_R) ≤ H ≤ N(σ_R),where N(σ_R) is the normalizer of the elementary net group E(σ_R) in G. For the normalizer N(σ_R),the formula N(σ_R)= TG(σ^R) holds. In particular, this result enables one to describe the maximal intermediate subgroups. Bibliography: 13 titles.     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.