✦ LIBER ✦

Iterating the branching operation on a directed graph

✍ Scribed by Athanasiadis, Christos A.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 118 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199703)24:3<257::aid-jgt7>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D 2 (G), . . .) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D 2 (G) = D(G).

📜 SIMILAR VOLUMES

On the spectral radius of a directed gra

On the spectral radius of a directed graph

✍ Kwapisz, Jaroslaw 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB 👁 1 views

We provide upper estimates on the spectral radius of a directed graph. In particular w e prove that the spectral radius is bounded by the maximum of the geometric mean of in-degree and out-degree taken over all vertices.

On the cycle polytope of a directed grap

On the cycle polytope of a directed graph

✍ Egon Balas; Maarten Oosten 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 1 views

A note on mixed graphs and directed spli

A note on mixed graphs and directed splitting off

✍ Enni, Steffen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 329 KB 👁 2 views

We give counterexamples to two conjectures of Bill Jackson in Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs (Journal of Graph Theory 12(3):429-436, 1988) concerning orientations of mixed graphs and splitting off in digraphs, and prove the first conjecture

Iterative Deoxypropionate Synthesis Base

Iterative Deoxypropionate Synthesis Based on a Copper-Mediated Directed Allylic Substitution

✍ Bernhard Breit; Christian Herber 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

A branch and cut algorithm for the Stein

A branch and cut algorithm for the Steiner problem in graphs

✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

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