Path-pairability of infinite planar grids

Periodica Mathematica Hungarica - For a given integer $$k\ge 1$$ , a graph G with at least 2k vertices is called k-path-pairable, if for any set of k disjoint pairs of vertices, $$s_i,t_i$$ ,...     

Minimal non-neighborhood-perfect graphs

Neighborhood-perfect graphs form a subclass of the perfect graphs if the Strong Perfect Graph Conjecture of C. Berge is true. However, they are still not shown to be perfect. Here we propose the characterization of neighborhood-perfect graphs by studying minimal non-neighborhood-perfect graphs (MNNPG). After presenting some properties of MNNPGs, we show that the only MNNPGs with neighborhood independence number one are the 3-sun and 3K₂. Also two further classes of neighborhood-perfect graphs are presented: line-graphs of bipartite graphs and a 3K₂-free cographs. © 1996 John Wiley & Sons, Inc.     

Surface Buckling and Subsurface Oxygen: Atomistic Insights into the Surface Oxidation of Pt(111)

Platinum is a catalyst of choice in scientific investigations and technological applications, which are both often carried out in the presence of oxygen. Thus, a fundamental understanding of platinum’s (electro)catalytic behavior requires a detailed knowledge of the structure and degree of oxidation of platinum surfaces in operando. ReaxFF reactive force field calculations of the surface energies for structures with up to one monolayer of oxygen on Pt(111) reveal four stable surface phases characterized by pure adsorbate, high‐ and low‐coverage buckled, and subsurface‐oxygen structures, respectively. These structures and temperature programmed desorption (TPD) spectra simulated from them compare favorably with and complement published scanning tunneling microscopy (STM) and TPD experiments. The surface buckling and subsurface oxygen observed here influence the surface oxidation process, and are expected to impact the (electro)catalytic properties of partially oxidized Pt(111) surfaces.     

An asymmetric approach to the radiosynthesis of both enantiomers of α-[11C]methyldopa and α-[11C]methyltyrosine for positron emission tomography

In PET, α-methyl amino acids can play a dual role: a) precursors of neurotransmitters analogues for the study of neurodegenerative diseases; b) non-metabolised analogues of proteinogenic amino acids for the study of amino acids uptake into normal and cancer cells. The difference in the uptake rates during a PET scan could visualise cancer cells in a human body. Clinical applications of such amino acids are strongly limited due to their poor availability. For the synthesis of α-[¹¹C]methyl-tryptohan, an industrial procedure was adopted. All attempts to prepare enantiomerically pure α-[¹¹C]methylated tyrosine failed. We carried out [¹¹C]methylation of metalocomplex synthons derived from protected DOPA or tyrosine. Individual diastereomers were successfully separated by preparative HPLC, diluted with excess of water and extracted on C₁₈ cartridges. Optimisation of the procedure followed by hydrolysis of the complexes and purification of the enantiomers of α-[¹¹C]methylDOPA and α-[¹¹C]methyltyrosine is underway.     

Toughness, hamiltonicity and split graphs

Related to Chvátal's famous conjecture stating that every 2-tough graph is hamiltonian, we study the relation of toughness and hamiltonicity on special classes of graphs.

First, we consider properties of graph classes related to hamiltonicity, traceability and toughness concepts and display some algorithmic consequences. Furthermore, we present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete.

We show that every split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to .     

The minimum number of triangles covering the edges of a graph

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number t_min(G) of triangles that cover the edges of G. We prove that ?(n - 1)/2? ? t_min(G) with equality attained only by 3-cactii and by strongly related graphs. We obtain sharp upper bounds: if G is not a 4-clique, then. The triangle cover number t_min(G) is also bounded above by Γ(G) = m - n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for t_min(G) ? Γ(G) and characterize the family of all extremal graphs satisfying equality.     

Ramsey unsaturated and saturated graphs

A graph is Ramsey unsaturated if there exists a proper supergraph of the same order with the same Ramsey number, and Ramsey saturated otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles C_n and paths P_n on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

Heavy Transversals and Indecomposable Hypergraphs

A weighted hypergraph is a hypergraph H = (V, E) with a weighting function , where R is the set of reals. A multiset S V generates a partial hypergraph H ^S with edges , where both the cardinality and the total weight w(S) are counted with multiplicities of vertices in S. The transversal number of H is represented by (H). We prove the following: there exists a function f(n) such that, for any weighted n-Helly hypergraph H, (H ^B ) 1, for all multisets B V if and only if (H ^A ) 1, for all multisets A V with . We provide lower and upper bounds for f(n) using a link between indecomposable hypergraphs and critical weighted n-Helly hypergraphs.* On leave from Computing and Automation Research Institute, Hungarian Academy of Sciences.     

Upper bound on the order of τ-critical hypergraphs

The right order of magnitude for the maximal number of vertices in an r-uniform τ-critical hypergraph H is achieved by obtaining an upper bound of O(τ(H)^r?1).