✦ LIBER ✦

The reduction of graph families closed under contraction

✍ Scribed by Paul A. Catlin

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 633 KB
Volume: 160
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00150-u

No coin nor oath required. For personal study only.

✦ Synopsis

Let 5~ be a family of graphs. Suppose there is a nontrivial graph H such that for any supergraph G of H, G is in 5 e if and only if the contraction G/H is in 5g. Examples of such an 0~: graphs with a spanning closed trail; graphs with at least k edge-disjoint spanning trees; and k-edge-connected graphs (k fixed). We give a reduction method using contractions to find when a given graph is in 5 ~ and to study its structure if it is not in Yr. This reduction method generalizes known special cases.

📜 SIMILAR VOLUMES

A family of graphs with expensive depth-

A family of graphs with expensive depth-reduction

✍ Georg Schnitger 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 443 KB

Stability of families of probability dis

Stability of families of probability distributions under reduction of the number of degrees of freedom

✍ Christophe Vignat; Jan Naudts 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 187 KB

Families of graphs complete for the stro

Families of graphs complete for the strong perfect graph Conjecture

✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true

A graph-theoretic version of the union-c

A graph-theoretic version of the union-closed sets conjecture

✍ El-Zahar, Mohamed H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We introduce the conjecture: Every non-empty graph contains a non-residual edge. This conjecture

Topological quadrangulations of closed t

Topological quadrangulations of closed triangulated surfaces using the Reeb graph

✍ Franck Hétroy; Dominique Attali 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 330 KB

Reductions of the Graph Reconstruction C

Reductions of the Graph Reconstruction Conjecture

✍ R. Statman 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 283 KB

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [l, p. 1 I]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall also show that the Graph Reconstruction Conjecture is