Density Conditions For Triangles In Multipartite Graphs

We consider the problem of finding a large or dense triangle-free subgraph in a given graph G. In response to a question of P. Erdős, we prove that, if the minimum degree of G is at least 9|V (G)|/10, the largest triangle-free subgraphs are precisely the largest bipartite subgraphs in G. We investigate in particular the case where G is a complete multipartite graph. We prove that a finite tripartite graph with all edge densities greater than the golden ratio has a triangle and that this bound is best possible. Also we show that an infinite-partite graph with finite parts has a triangle, provided that the edge density between any two parts is greater than 1/2.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Nonseparating cycles in K-Connected graphs

We show that every k-connected graph with no 3-cycle contains an edge whose contraction results in a k-connected graph and use this to prove that every (k + 3)-connected graph contains a cycle whose deletion results in a k-connected graph. This settles a problem of L. Lovász.     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

On hypohamiltonian graphs

Herz, Duby and Vigué [9] conjectured that every hypohamiltonian graph has girth 5. In the present note hypohamiltonian graphs of girth 3 and 4 are described. Also two conjectures on hypohamiltonian graphs made by Bondy and Chvátal, respectively, are disproved.     

Reconstructibility versus edge reconstructibility of infinite graphs

For every cardinal $\text{α > ?}{}_{\mathrm{D}}$ there exists an α regular graph which is reconstructible but not e reconstructible.     

On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

Edge-decompositions of highly connected graphs into paths

We prove that a graph of edge-connectivity at least has an edge-decomposition into paths of length 4 if and only its size is divisible by 4. We also prove that a graph of girth >m and of edge-connectivity at least 8 ^m has an edge-decomposition into paths of length m provided its size is divisible by m, and m is a power of 2.      

The ArNe-N2O van der Waals trimer: a high resolution spectroscopic study of its rotational spectrum,structure and dynamics

A new ternary van der Waals complex of the type rare gas-rare gas'-linear molecule, ArNe-N₂O, was investigated using a pulsed molecular beam cavity Fourier transform microwave spectrometer. The rotational spectra of six isotopomers of the trimer were studied in detail. These include Ar²⁰Ne-¹⁴N¹⁴NO, Ar²²Ne-¹⁴N¹⁴NO, Ar²⁰Ne-15N¹⁴NO, Ar²²Ne-¹⁵N¹⁴N0, Ar²⁰Ne-¹⁴N¹⁵NO and Ar²²Ne-¹⁴N¹⁵NO. Nuclear quadrupole hyperfine structures of the rotational transitions that are due to the one or two ¹⁴N nuclei were resolved and analysed. The resulting spectroscopic constants were used to provide structural and dynamical information about the trimer. Based on the quartic centrifugal distortion constants, a harmonic force field analysis was performed to estimate the frequencies of the van der Waals vibrational modes. A perturbation of the electronic charge distribution at the site of the central ¹⁴N nucleus of N²0 upon complex formation was detected and discussed. Differences of structural parameters of the trimer as compared to those of the respective dimer units are indicative of the presence of significant three-body non-additive contributions to the interaction energy.