✦ LIBER ✦

A note on some embedding problems for oriented graphs

✍ Scribed by Andrew Treglown

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 88 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20586

No coin nor oath required. For personal study only.

✦ Synopsis

We conjecture that every oriented graph G on n vertices with + (G), -(G) ≥ 5n / 12 contains the square of a Hamilton cycle. We also give a conjectural bound on the minimum semidegree which ensures a perfect packing of transitive triangles in an oriented graph. A link between Ramsey numbers and perfect packings of transitive tournaments is also considered.

📜 SIMILAR VOLUMES

A note on vertex pancyclic oriented grap

A note on vertex pancyclic oriented graphs

✍ Bang-Jensen, J�rgen; Guo, Yubao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

A note on the bottleneck graph partition

A note on the bottleneck graph partition problem

✍ Klinz, Bettina; Woeginger, Gerhard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 47 KB 👁 2 views

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem wit

A note on a problem of Smirnov. A graph

A note on a problem of Smirnov. A graph theoretic interpretation

✍ Ronald Alter; Bennet Lientz 📂 Article 📅 1970 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

Deferred-query: An efficient approach fo

Deferred-query: An efficient approach for some problems on interval graphs

✍ Chang, Maw-Shang; Peng, Sheng-Lung; Liaw, Jenn-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 2 views

This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(

A Note on Multiple Solutions of Some Sem

A Note on Multiple Solutions of Some Semilinear Elliptic Problems

✍ E.N. Dancer; Yihong Du 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 228 KB

We discuss the existence of multiple solutions of nonlinear elliptic equations by a combination of variational, topological methods and the generalized Conley index theory. We obtain several positive solutions and sign-changing solutions. Our main point is to show the usefulness of the Morse inequal

On a Mutation Problem for Oriented Matro

On a Mutation Problem for Oriented Matroids

✍ Jürgen Bokowski; Holger Rohlfs 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 469 KB

For uniform oriented matroids M with n elements, there is in the realizable case a sharp lower bound L r (n) for the number mut(M) of mutations of M : L r (n) = n ≤ mut(M), see Shannon [17]. Finding a sharp lower bound L(n) ≤ mut(M) in the non-realizable case is an open problem for rank d ≥ 4. Las V