Norms and perfect graphs

The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987.     

Circuit-switching networks with FIFO plus justifying blockout service on infinite graphs

A class of circuit-switching open queueing networks is discussed. The main result of the paper is that if extra message flows are not too intensive and the path distribution is mainly concentrated on the paths of (graph) distance 1 (nearest neighbour connections), then the network has a unique stationary working regime, no matter how large the configuration graph of the network is. Standard properties of this regime are established such as decay of correlation and continuity.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Asymptotically independent topological indices on random trees

Topological indices are graph invariants used in computational chemistry to encode molecules. A frequent problem when performing structure-activity studies is that topological indices are inter-correlated. We consider a simple topological index and show asymptotic independence for a random tree model. This continues previous work on the correlation among topological indices. These findings suggest that a size-dependence in a certain class of distance-based topological indices can be eliminated.AMS subject classification: 05C80, 60E10, 92E10     

Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks

Summary Global relations between RNA sequences and secondary structures are understood as mappings from sequence space into shape space. These mappings are investigated by exhaustive folding of allGC andAU sequences with chain lengths up to 30. The computed structural data are evaluated through exhaustive enumeration and used as an exact reference for testing analytical results derived from mathematical models and sampling based on statistical methods. Several new concepts of RNA sequence to secondary structure mappings are investigated, among them that ofneutral networks (being sets of sequences folding into the same structure). Exhaustive enumeration allows to test several previously suggested relations: the number of (minimum free energy) secondary structures as a function of the chain length as well as the frequency distribution of structures at constant chain length (commonly resulting in generalized forms ofZipf's law).

---

Analyse der Beziehungen zwischen RNA-Sequenzen und Sekundärstrukturen durch vollständige Faltung, 1. Mitt. Faltung, Neutrale Netzwerke

Zusammenfassung Die globalen Benziehungen zwischen RNA-Sequenzen und Sekundärstrukturen werden als Abbildungen aus einem Raum aller Sequenzen in einen Raum aller Strukturen aufgefaßt. Diese Abbildungen werden durch Falten aller binären Sequenzen desGC-undAU-Alphabets mit Kettenlängen bis zun=30 untersucht. Die berechneten Strukturdaten werden durch vollständiges Abzählen ausgewertet und als eine exakte Referenz zum Überprüfen analytischer Resultate aus mathematischen Modellen sowie zum Testen statistisch erhobener Proben verwendet. Einige neuartige Konzepte zur Beschreibung der Beziehungen zwischen Sequenzen und Strukturen werden eingehend untersucht, unter ihnen der Begriff derneutralen Netzwerke. Ein neutrales Netzwerk besteht aus allen Sequenzen, die eine bestimmte Struktur ausbilden. Vollständiges Abzählen ermöglicht beispielsweise die Bestimmung aller Strukturen minimaler freier Energie in Abhängigkeit von der Kettenlänge ebenso wie die Bestimmung der Häufigkeitsverteilungen der Strukturen bei konstanten Kettenlängen. Die letzteren folgen einer verallgemeinerten FormZipfschen Gesetzes.

     

A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.     

Large cycles in random generalized Johnson graphs

This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for different growth rates.     

Spectra of graphs and fractal dimensions II

This paper continues the study of exponentsd(x), d (x), d _R (x) andd (x) for graphG; and the nearest neighbor random walk {X _n } _nN onG, if the starting pointX ₀=x is fixed. These exponents are responsible for the geometric, resistance, diffusion and spectral properties of the graph. The main concern of this paper is the relation of these exponents to the spectral density of the transition matrix. A series of new exponentse, e ,e _R ,e are introduced by allowingx to vary along the vertices. The results suggest that the geometric and resistance properties of the graph are responsible for the diffusion speed on the graph.     

Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.     

Near-perfect matrices

A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x0: Ax } can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.