On list‐coloring outerplanar graphs

We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors L (v ) for each vertex v such that (resp., ) can be L‐list‐colored (except when the graph is K₃ with identical 2‐lists). These results are best possible for each condition in the hypotheses and bounds. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 59–74, 2008     

A brief historical introduction to Euler's formula for polyhedra,topology, graph theory and networks

This article is essentially devoted to a brief historical introduction to Euler's formula for polyhedra, topology, theory of graphs and networks with many examples from the real-world. Celebrated Königsberg seven-bridge problem and some of the basic properties of graphs and networks for some understanding of the macroscopic behaviour of real physical systems are included. We also mention some important and modern applications of graph theory or network problems from transportation to telecommunications. Graphs or networks are effectively used as powerful tools in industrial, electrical and civil engineering, communication networks in the planning of business and industry. Graph theory and combinatorics can be used to understand the changes that occur in many large and complex scientific, technical and medical systems. With the advent of fast large computers and the ubiquitous Internet consisting of a very large network of computers, large-scale complex optimization problems can be modelled in terms of graphs or networks and then solved by algorithms available in graph theory. Many large and more complex combinatorial problems dealing with the possible arrangements of situations of various kinds, and computing the number and properties of such arrangements can be formulated in terms of networks. The Knight's tour problem, Hamilton's tour problem, problem of magic squares, the Euler Graeco-Latin squares problem and their modern developments in the twentieth century are also included.     

Formulations for the Minimum 2-Connected Dominating Set Problem

Three formulations for the Minimum 2-Connected Dominating Set Problem, valid inequalities, a primal heuristic and Branch-and-Cut algorithms are introduced in this paper. As shown here, the preliminary computational results so far obtained indicate that these algorithms are quite promising.     

Approximating the maximum 2- and 3-edge-colorable subgraph problems

For a fixed value of a parameter k≥2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be -hard for all k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 and k=3, having approximation ratios of 5/6 and 4/5, respectively.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

Cayley digraphs with normal adjacency matrices

In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset S. It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group G is normal iff G is either abelian or has the form for some non-negative integer n, where Q₈ is the quaternion group and is the abelian group of order 2ⁿ and exponent 2.     

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.

     

Closed‐form formulas for Kirchhoff index

We find closed‐form expressions for the resistance, or Kirchhoff index, of certain connected graphs using Foster's theorems, random walks, and the superposition principle. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 135–140, 2001     

An Improved Plotting Package Applied to Chemical Graphing Problems

Abstract

A plotting package, written in LINC assembly language, is described. It produces high quality graphs and labels the graphs for direct submission to professional journals. A μ-LINC (Laboratory INstrument (Computer) is used to compute least-squares fitted curves and lines from data entered either on-or off-line and to draw the graphs directly on an incremental plotter. Bar graphs, line graphs, and fitted data can be plotted with options to suppress the lines and/or the points.     

Complete graph conjecture for inner-core electrons: homogeneous index case

The complete graph conjecture that encodes the inner-core electrons of atoms with principal quantum number n >or= 2 with complete graphs, and especially with odd complete graphs, is discussed. This conjecture is used to derive new values for the molecular connectivity and pseudoconnectivity basis indices of hydrogen-suppressed chemical pseudographs. For atoms with n = 2 the new values derived with this conjecture are coincident with the old ones. The modeling ability of the new homogeneous basis indices, and of the higher-order terms, is tested and compared with previous modeling studies, which are centered on basis indices that are either based on quantum concepts or partially based on this new conjecture for the inner-core electrons. Two similar algorithms have been proposed with this conjecture, and they parallel the two "quantum" algorithms put forward by molecular connectivity for atoms with n > 2. Nine properties of five classes of compounds have been tested: the molecular polarizabilities of a class of organic compounds, the dipole moment, molar refraction, boiling points, ionization energies, and parachor of a series of halomethanes, the lattice enthalpy of metal halides, the rates of hydrogen abstraction of chlorofluorocarbons, and the pED(50) of phenylalkylamines. The two tested algorithms based on the odd complete graph conjecture give rise to a highly interesting model of the nine properties, and three of them can even be modeled by the same set of basis indices. Interesting is the role of some basis indices all along the model.