𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum directed cuts in digraphs with degree restriction

✍ Scribed by Jenö Lehel; Frédéric Maffray; Myriam Preissmann

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
173 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For integers m, k≥1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k. © 2009 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Maximum directed cuts in acyclic digraph
Maximum directed cuts in acyclic digraphs
✍ Noga Alon; Béla Bollobás; András Gyárfás; Jenő Lehel; Alex Scott 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract It is easily shown that every digraph with __m__ edges has a directed cut of size at least __m__/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in __acyclic__ digraphs, and prove a number of related results concerning cuts

On the existence of a specified cycle in
On the existence of a specified cycle in digraphs with constraints on degrees
✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by

Subgraphs with Restricted Degrees of the
Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds
✍ S. Jendrol’; H.-J. Voss 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 276 KB

Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G on M, which has at least (8k 2 + 6k -6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4k

Very rapidly mixing Markov chains for 2Δ
Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4
✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A