✦ LIBER ✦

The Separator Theorem for Rooted Directed Vertex Graphs

✍ Scribed by B.S. Panda

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 109 KB
Volume: 81
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2001

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we point out a flaw in the separator theorem for rooted directed vertex graphs due to C. L. Monma and V. K. Wei (1986, J. Combin. Theory Ser. B 41, 141 181), and present a modified separator theorem for the same class of graphs.

📜 SIMILAR VOLUMES

The Isomorphism Problem For Directed Pat

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

✍ L. Babel; I.N. Ponomarenko; G. Tinhofer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 237 KB

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path

Exact algorithms for the vertex separato

Exact algorithms for the vertex separator problem in graphs

✍ Cid C. de Souza; Victor F. Cavalcante 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

An 11-vertex theorem for 3-connected cub

An 11-vertex theorem for 3-connected cubic graphs

✍ R. E. L. Aldred; BauSheng; D. A. Holton; Gordon F. Royle 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 451 KB 👁 1 views

In this paper w e determine the circumstances under which a set of 11 vertices in a 3-connected cubic graph lies on a cycle. In addition, w e consider the number of such cycles that exist and characterize those graphs in which a set of 9 vertices lies in exactly two cycles.

On the greedoid polynomial for rooted gr

On the greedoid polynomial for rooted graphs and rooted digraphs

✍ Elizabeth W. McMahon 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 499 KB

## Abstract We examine some properties of the 2‐variable greedoid polynomial __f__(__G·,t,z__) when __G__ is the branching greedoid associated to a rooted graph or a rooted directed graph. For rooted digraphs, we show a factoring property of __f__(__G·,t,z__) determines whether or not the rooted di

The Closed Graph Theorem for Nonlinear M

The Closed Graph Theorem for Nonlinear Maps

✍ Antonio Tineo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 75 KB

A Criterion for the t-Vertex Condition o

A Criterion for the t-Vertex Condition of Graphs

✍ Sven Reichard 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 126 KB

Combining two concepts of regularity of graphs, namely k-isoregularity and the t-vertex condition, a generalization of a classical result by Hestenes and Higman is presented. As an application it is shown that two infinite series of graphs constructed by Brouwer, Ivanov, and Klin which are not rank