𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Separability generalizes Dirac's theorem

✍ Scribed by Anne Berry; Jean-Paul Bordat

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
736 KB
Volume
84
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In our study of the extremities of a graph, we define a moplex as a maximal clique module the neighborhood of which is a minimal separator of the graph. This notion enables us to strengthen Dirac's theorem : "Every non-clique triangulated graph has at least two non-adjacent simplicial vertices", restricting the definition of a simplicial vertex; this also enables us to strengthen Fulkerson and Gross' simplicial elimination scheme; thus provides a new characterization for triangulated graphs. Our version of Dirac's theorem generalizes from the class of triangulated graphs to any undirected graph: "Every non-clique graph has at least two non-adjacent moplexes".

To insure a linear-time access to a moplex in any graph, we use an algorithm due to Rose Tarjan and Lueker (1976) for the recognition of triangulated graphs, known as LexBFS: we prove a new invariant for this, true even on non-triangulated graphs.

πŸ“œ SIMILAR VOLUMES

Neighborhood unions and a generalization
Neighborhood unions and a generalization of Dirac's theorem
✍ R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 818 KB

Dirac proved that if each vertex of a graph G of order n 23 has degree at least n/2, then the graph is Hamiltonian. This result will be generalized by showing that if the union of the neighborhoods of each pair of vertices of a 2connected graph G of sufficiently large order n has at least n/2 vertic

A Generalization of a Theorem of Dirac
A Generalization of a Theorem of Dirac
✍ Tristan Denley; Haidong Wu πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 85 KB

In this paper, we give a generalization of a well-known result of Dirac that given any k vertices in a k-connected graph where k 2, there is a circuit containing all of them. We also generalize a result of Ha ggkvist and Thomassen. Our main result partially answers an open matroid question of Oxley.

Some General Separation Theorems
Some General Separation Theorems
✍ Reinhard Nehse πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 438 KB

Separation theorems are known to have fundamental importance for several fields of mathematics. Recently some authors have proved new separation theorems for set.s in real vector spaces and generalizations of such spaces (for instance, convexity spaces), respectively (see The purpose of this paper

Dirac's map-color theorem for choosabili
Dirac's map-color theorem for choosability
✍ BοΏ½hme, T.; Mohar, B.; Stiebitz, M. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 290 KB

It is proved that the choice number of every graph G embedded on a surface of Euler genus Ξ΅ β‰₯ 1 and Ξ΅ = 3 is at most the Heawood number H(Ξ΅) = (7 + √ 24Ξ΅ + 1)/2 and that the equality holds if and only if G contains the complete graph K H(Ξ΅) as a subgraph.

On the Kurosh theorem and separability p
On the Kurosh theorem and separability properties
✍ Rita Gitik; Stuart W. Margolis; Benjamin Steinberg πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 225 KB

We prove a Kurosh-type subgroup theorem for free products of LERF groups. This theorem permits a better understanding of how ΓΏnitely generated subgroups are embedded in ΓΏnite index subgroups. Consequences include the double coset separability of free products of negatively curved surface groups. Oth