The class reconstruction number of maximal planar graphs

The reconstruction numberrn(G) of a graphG was introduced by Harary and Plantholt as the smallest number of vertex-deleted subgraphsG _i =G – v _i in the deck ofG which do not all appear in the deck of any other graph. For any graph theoretic propertyP, Harary defined theP-reconstruction number of a graph G P as the smallest number of theG _i in the deck ofG, which do not all appear in the deck of any other graph inP We now study the maximal planar graph reconstruction numberrn(G), proving that its value is either 1 or 2 and characterizing those with value 1.     

Some remarks on automorphisms of bounded displacement and bounded cocycles

Some time agoTits has considered the question of characterizingB(G), and more generally, of finding the automorphisms of bounded displacement ofG, particularly whenG is a connected real Lie group. Our purpose here is to extend these results to various other cases as well as to deal with the analogous questions for 1-cocycles. We concern ourselves, among other things, with the question of sufficient conditions forB(G)=Z(G), the center, or more generally, forG to have no non-trivial automorphisms of bounded displacement. The significance of such conditions can be seen in work of the author together withF. Greenleaf andL. Rothschild where, for example, the Selberg form of the Borel density theorem is considerably generalized. These conditions are therefore closely related to, but not identical with, sufficient conditions for the Zariski density of a closed subgroupH ofG withG/H having finite volume, see [11]. For this reason it is enlightening to compare these results with those of [11]. On the cocycle level, we give sufficient conditions for the points with bounded orbit under a linear representation to be fixed and more generally, for a bounded 1-cocycle to be identically zero. These conditions actually play a role in [11]; they are among the sufficient conditions necessary to establish Zariski density ofH inG. We also deal with certain converse questions and applications to homogeneous spaces of finite volume. For example, ifG/H has finite volume and is an automorphism ofG leavingH pointwise fixed, then has bounded displacement. If is a 1-cocycle and /H is trivial, then is itself bounded.Research partially supported by NSF Grant=MPS 75-08268.     

Duals of orbit spaces in groups with relatively compact inner automorphism groups are hypergroups

For a locally compact groupG and a groupB of topological automorphisms containing the inner automorphisms ofG and being relatively compact with respect to Birkhoff topology (that isG[FIA] _B,B I(G)) the spaceG _B of -orbits is a commutative hypergroup (=commutative convo inJewett's terminology) in a natural way asJewett has shown. Identifying the space of hypergroup characters ofG _B withE(G, B) (the extreme points ofB-invariant positive definite continuous functionsp withp (e)=1, endowed with the topology of compact convergence) we prove thatE(G, B) is a hypergroup, the hypergroup dual ofG _B.     

Linear equations depending differentiably on a parameter

We investigate operator functionsT(x) inBanach spaces, depending differentiably (meaning of classC orC ) on a parameterx and enjoying a certain regularity property. Iff is a given differentiable function such that the equationT(x)e=f(x) is solvable for eachx then the existence of a functione is proved which belongs to the same differentiability class asf andT, solving the equationT(x)e(x)f(x) identically inx. As an application we extend a result ofJ. Leiterer [9] and give a comprehensive answer to a question posed byJ.L. Taylor in [15] concerning the exactness of certain cochain complexes.     

Tracking poles and representing Hankel operators directly from data

Summary We propose and analyse a method of estimating the poles near the unit circleT of a functionG whose values are given at a grid of points onT: we give an algorithm for performing this estimation and prove a convergence theorem. The method is to identify the phase for an estimate by considering the peaks of the absolute value ofG onT, and then to estimate the modulus by seeking a bestL ² fit toG over a small arc by a first order rational function. These pole estimates lead to the construction of a basis ofL ² which is well suited to the numerical representation of the Hankel operator with symbolG and thereby to the numerical solution of the Nehari problem (computing the bestH , analytic, approximation toG relative to theL norm), as analysed in [HY]. We present the results of numerical tests of these algorithms.Partially supported by grants from the AFOSR and NSF     

In the square of graphs,hamiltonicity and pancyclicity,Hamiltonian connectedness and panconnectedness are equivalent concepts

The squareG ² of a graphG has the same point set asG, and two points ofG ² are adjacent inG ² if and only if their distance inG is at most two. The result thatG ² is Hamiltonian ifG is two-connected, has been established early in 1971. A conjecture (ofA. Bondy) followed immediately: SupposeG ² to have a Hamiltonian cycle; is it true that for anyvV(G), there exist cyclesC _j containingv and having arbitrary lengthj, 3j|V(G)|. The proof of this conjecture is one of the two main results of this paper. The other main result states that ifG ² contains a Hamiltonian pathP(v, w) joining the pointsv andw, thenG ² contains for anyj withd _G ² (v, w)j|V(G)|–1 a pathP _j (v, w) of lengthj joiningv andw. By this, a conjecture ofF. J. Faudree andR. H. Schelp is proved and generalized for the square of graphs.However, to prove these two results extensive preliminary work is necessary in order to make the proof of the main results transparent (Theorem 1 through 5); and Theorem 3 plays a central role for the main results. As can be seen from the statement of Theorem 3, the following known results follow in a stronger form: (a) IfG is two-connected, thenG ² is Hamiltonian-connected; (b) IfG is two-connected, thenG ² is 1-Hamiltonian.Dedicated to Prof. Dr. E. Hlawka on the occasion of his 60th birthday     

Continuity of operators commuting with translations for compact groups

In this note we show for certain Frechet spacesF(G) of functions (distributions) on a compact groupG that if every translation invariant linear functional onF(G) is continuous then every linear operatorT:F(G)F(G) commuting with translations is continuous. This solves partially a problem in [7] ofG. H. Meisters and improves the result [5] ofC. J. Lester. An application for compact groups which do not have the mean zero weak containment property follows by the result [10] ofG. A. Willis.     

The exponent of convergence of poincaré series

This paper continues the systematic study of the exponent of convergence (G) of a Fuchsian groupG begun byA. F. Beardon. The object is to show that in various senses (G) is a continuous function ofG. In view of the incompleteness of our knowledge about (G) considerable attention is paid to illustrative examples.     

Complementing lattice-ordered groups: The finite-valued case

A complementedl-groupG is one in which to eacha G there exists ab G so that¦a¦ ¦b¦=0, while¦a¦ ¦b¦ is a unit ofG. IfG is anl-subgroup ofH, and the latter is complemented, then we say thatH is a complementation ofG ifG ^c , the convex hull ofG inH, is a strongly rigid extension ofG andG ^c is az-subgroup ofH. This article presents necessary and sufficient conditions for a finite-valuedl-subgroup to admit a complementation.Presented by M. Henriksen.     

Computation of a lower bound of the lengths of schedules

For a graphG of strict partial ordering, the lower estimates T₁ T₂T₃T₄ of the lengths of m-processor schedules are given depending on the extent of the details known about graphG. The best estimate, T₄, is obtained if the partitions of the set of vertices ofG into levels from above and from below are known. The complexity of obtaining the estimate T₄ is equal to O(n), where n=G.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 35–40, 1983.     

Classes of graphs that exclude a tree and a clique and are not vertex ramsey

A class of graphs is vertex Ramsey if for allH there existsG such that for all partitions of the vertices ofG into two parts, one of the parts contains an induced copy ofH. Forb (T,K) is the class of graphs that induce neitherT norK. LetT(k, r) be the tree with radiusr such that each nonleaf is adjacent tok vertices farther from the root than itself. Gyárfás conjectured that for all treesT and cliquesK, there exists an integerb such that for allG in Forb(T,K), the chromatic number ofG is at mostb. Gyárfás' conjecture implies a weaker conjecture of Sauer that for all treesT and cliquesK, Forb(T,K) is not vertex Ramsey. We use techniques developed for attacking Gyárfás' conjecture to prove that for allq, r and sufficiently largek, Forb(T(k,r),K _q ) is not vertex Ramsey.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Linearly independent zeros of quadratic forms over number-fields

LetK be an algebraic number-field of degree [K:Q] =n 1 and letO denote some fixed order ofK. Let, be a quadratic form which represents zero for some. For the special caseK =Q,O =Z, theorems ofCassels and ofDavenport provide estimates for the magnitude (in terms of the coefficients off(x)) of a zero and of a pair of linearly independent zeros off, respectively. Recently,Raghavan extendedCassels' result to arbitraryK. In this article, a new proof ofDavenport's theorem for a pair of linearly independent zeros is given which not only provides explicit constants in the estimates but also extends to generalK. A refinement of this proof leads to effectively computable bounds for rational representations of a numbern0 byf.     

Schwach irreduzible Markoff-Operatoren

For any weakly irreducible Markov operatorT on the space of continuous functions on a compact space and any continuous functionf we show that pointwise convergence of (T ⁿf) already implies uniform convergence. This improves a result ofJamison [2]. We also study convergence whenf is only measurable and give results related to the zero-two law. Finally two characterizations of uniform ergodicity for this class of operators are given. In particular a question ofLotz [4] is answered.     

Time-optimal controls of the equation of evolution in a separable and reflexive Banach space

Let a variable, closed, bounded, and convex subset ofX, a separable and reflexive Banach space, be denoted byG(t). Suppose thatG(t) varies upper-semicontinuously with respect to inclusion ast varies in [0,T]. We say that the strongly measurable mapu from [0,T] toX is an admissible control if, for almost everyt in [0,T],u(t) is an element ofU, a closed, bounded, and convex subset ofX, and u _p M ^1p, where p>1 andM>0.Ifx ^u is the weak solution todx/dt+A(t)x=u(t), 0tT, whereA(t) is as defined by Tanabe in Ref. 1, we say that the responsex ^u to the controlu hits the target in timeT ^u ifx ^u (0)=0 andx ^u (T ^u ) is an element ofG(T ^u ). If there is a control with this property, then there is a time-optimal control.     

Prime ideals in the C*-algebra of a nilpotent group

We say that a locally compact groupG hasT ₁ primitive ideal space if the groupC ^*-algebra,C ^*(G), has the property that every primitive ideal (i.e. kernel of an irreducible representation) is closed in the hull-kernel topology on the space of primitive ideals ofC ^*(G), denoted by PrimG. This means of course that every primitive ideal inC ^*(G) is maximal. Long agoDixmier proved that every connected nilpotent Lie group hasT ₁ primitive ideal space. More recentlyPoguntke showed that discrete nilpotent groups haveT ₁ primitive ideal space and a few month agoCarey andMoran proved the same property for second countable locally compact groups having a compactly generated open normal subgroup. In this note we combine the methods used in [3] with some ideas in [9] and show that for nilpotent locally compact groupsG, having a compactly generated open normal subgroup, closed prime ideals inC ^*(G) are always maximal which implies of course that PrimG isT ₁.     

Mortality of iterated Gallai graphs

For a finite or infinite graphG, theGallai graph (G) ofG is defined as the graph whose vertex set is the edge setE(G) ofG; two distinct edges ofG are adjacent in (G) if they are incident but do not span a triangle inG. For any positive integert, thetth iterated Gallai graph ^t (G) ofG is defined by ( ^t–1(G)), where ⁰(G):=G. A graph is said to beGallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways.     

Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen

The main result states: Lete ₁,e ₂,e ₃ be three lines incident to the pointv (degv4) of the connected bridgeless graphG such thate ₁ ande ₃ belong to different blocks ifv is a cutpoint. Split the pointv in two ways: Lete ₁,e _j ,j=2, 3, be incident to a new pointv _1j and leave the remainder ofG unchanged, thus obtainingG _1j . Then at least one of the two graphsG ₁₂,G ₁₃ is connected and bridgeless. — A classical result ofFrink follows from this theorem which is the key to a simple proof of Petersen's theorem. Moreover, the above result can be used to prove practically all classical results on Eulerian graphs, including best upper and lower bounds for the number of Eulerian trails in a connected Eulerian graph. In the theory of Eulerian graphs, it can be viewed as the basis for good algorithms checking on several properties of this class of graphs.

---

---

Herrn Prof. Dr. H. Hornich zum 70. Geburtstag gewidmet     

Local Tree-Width,Excluded Minors,and Approximation Algorithms

The local tree-width of a graph G=(V,E) is the function ltw^G : that associates with every r the maximal tree-width of an r-neighborhood in G. Our main grapht heoretic result is a decomposition theorem for graphs with excluded minors, which says that such graphs can be decomposed into trees of graphs of almost bounded local tree-width.As an application of this theorem, we show that a number of combinatorial optimization problems, suchas Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

Abelian cocycles for nonsingular ergodic transformations and the genericity of type III1 transformations

The authors prove that in the space of nonsingular transformations of a Lebesgue probability space the type III₁ ergodic transformations form a denseG set with respect to the coarse topology. They also prove that for any locally compact second countable abelian groupH, and any ergodic type III transformationT, it is generic in the space ofH-valued cocycles for the integer action given byT that the skew product ofT with the cocycle is orbit equivalent toT. Similar results are given for ergodic measure-preserving transformations as well.Research supported in part by: Nat. Sci. and Eng. Res. Council #A7163 and # U0080 F.C.A.C. Quebec, NSF Grants # MCS-8102399 and # DMS-8418431.