The connectivity of the basis graph of a branching greedoid

Haitze J. Broersma, Xueliang Li, Xueliang Li

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
38 Downloads (Pure)

Abstract

A result of Korte and Lovász states that the basis graph of every 2- connected greedoid is connected. We prove that the basis graph of every 3-connected branching greedoid is ( -- 1)-connected, where is the minimum in-degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible.
Original languageEnglish
Pages (from-to)233-237
Number of pages5
JournalJournal of graph theory
Volume16
Issue number3
DOIs
Publication statusPublished - 1992

Fingerprint

Branching
Connectivity
Graph in graph theory
Multigraph
Roots

Keywords

  • METIS-140357
  • IR-70971

Cite this

Broersma, Haitze J. ; Li, Xueliang ; Li, Xueliang. / The connectivity of the basis graph of a branching greedoid. In: Journal of graph theory. 1992 ; Vol. 16, No. 3. pp. 233-237.
@article{8553f3150c744b0980be39f5c58410a4,
title = "The connectivity of the basis graph of a branching greedoid",
abstract = "A result of Korte and Lov{\'a}sz states that the basis graph of every 2- connected greedoid is connected. We prove that the basis graph of every 3-connected branching greedoid is ( -- 1)-connected, where is the minimum in-degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible.",
keywords = "METIS-140357, IR-70971",
author = "Broersma, {Haitze J.} and Xueliang Li and Xueliang Li",
year = "1992",
doi = "10.1002/jgt.3190160306",
language = "English",
volume = "16",
pages = "233--237",
journal = "Journal of graph theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",

}

The connectivity of the basis graph of a branching greedoid. / Broersma, Haitze J.; Li, Xueliang; Li, Xueliang.

In: Journal of graph theory, Vol. 16, No. 3, 1992, p. 233-237.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The connectivity of the basis graph of a branching greedoid

AU - Broersma, Haitze J.

AU - Li, Xueliang

AU - Li, Xueliang

PY - 1992

Y1 - 1992

N2 - A result of Korte and Lovász states that the basis graph of every 2- connected greedoid is connected. We prove that the basis graph of every 3-connected branching greedoid is ( -- 1)-connected, where is the minimum in-degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible.

AB - A result of Korte and Lovász states that the basis graph of every 2- connected greedoid is connected. We prove that the basis graph of every 3-connected branching greedoid is ( -- 1)-connected, where is the minimum in-degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible.

KW - METIS-140357

KW - IR-70971

U2 - 10.1002/jgt.3190160306

DO - 10.1002/jgt.3190160306

M3 - Article

VL - 16

SP - 233

EP - 237

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 3

ER -