✦ LIBER ✦

Nearly acyclic graphs are reconstructible

✍ Scribed by Bennet Manvel; Joseph M. Weinstein

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 815 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020105

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that a graph G is reconstructible if G has a node v with G‐v acyclic. The proof uses colored graphs and shows how to reconstruct some graphs from pieces which share a common subgraph having few automorphisms.

📜 SIMILAR VOLUMES

Bidegreed graphs are edge reconstructibl

Bidegreed graphs are edge reconstructible

✍ W. J. Myrvold; M. N. Ellingham; D. G. Hoffman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 829 KB

An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs

Claw-free graphs are edge reconstructibl

Claw-free graphs are edge reconstructible

✍ M. N. Ellingham; L. Pyber; Xingxing Yu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 1 views

The Edge Reconstruction Conjecture states that all graphs with at least four edges are determined by their edge-deleted subgraphs. We prove that this is true for claw-free graphs, those graphs with no induced subgraph isomorphic to K,,3. This includes line graphs as a special case.

Graphs without short odd cycles are near

Graphs without short odd cycles are nearly bipartite

✍ Ervin Györi; Alexandr V Kostochka; Tomasz Łuczak 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

It is proved that for every constant ~ > 0 and every graph G on n vertices which contains no odd cycles of length smaller than ~n, G can be made bipartite by removing (15/~}ln(10/~)) vertices. This resuIt is best possible except for a constant factor. Moreover, it is shown that one can destroy all o

The reconstruction conjecture is true if

The reconstruction conjecture is true if all 2-connected graphs are reconstructible

✍ Yang Yongzhi 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

It is shown that the Reconstruction Conjecture is true for all finite graphs if it is true for the 2-connected ones. We shall, for the most part, use the terminology of [2] and [ 4 ] . Graphs will be finite, simple, and undirected. Let G be a graph and u E V(G). Denote by d(u) the degree of u in G

Finite undirected graphs which are not r

Finite undirected graphs which are not reconstructible from their large cardinality subgraphs

✍ Václav Nýdl 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 297 KB

Nydl, V., Finite undirected graphs which are not reconstructible from their large cardinality subgraphs, Discrete Mathematics 108 (1992) 373-377. For any integer n, and any real q, 0 < q < 1, we exhibit two nonisomorphic graphs on n > n,, vertices having the same collections of m-vertex subgraphs w

High-Girth Graphs Avoiding a Minor are N

High-Girth Graphs Avoiding a Minor are Nearly Bipartite

✍ Anna Galluccio; Luis A. Goddyn; Pavol Hell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Let H be a fixed graph. We show that any H-minor free graph G of high enough girth has circular chromatic number arbitrarily close to two. Equivalently, each such graph G admits a homomorphism to a large odd circuit. In particular, graphs of high girth and of bounded genus, or of bounded tree width,