𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Binary contraction of graphs

✍ Scribed by Patrice Assouad

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
410 KB
Volume
47
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We define the (elementary) binary contraction Gs of a graph G = (V, E) in the following way: if (S) is an induced K,,, not contained into an induced Klv3, then Gs is either the induced subgraph (V\ S), or the graph obtained from (V\S) by adding a new vertex adjacent to those x E V\S such that (S U(x)) has an odd number of edges (according that (S) is contained into an induced K2,* or not). We show that the binary contraction can be performed in some class of graphs such that: the line graphs, the subgraphs of a given root system (and thus the generalized line graphs), the subgraphs of L' (with a given scale and size), the graphs of negative type, . . . .

📜 SIMILAR VOLUMES

Contraction–Deletion Invariants for Grap
Contraction–Deletion Invariants for Graphs
✍ Béla Bollobás; Luke Pebody; Oliver Riordan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 192 KB

We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(GÂe)+T(G&e) for e # E(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditio

Reverse binary graphs
Reverse binary graphs
✍ Sajal K Das; Narsingh Deo; Sushil Prasad 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 889 KB
Some applications of graph contractions
Some applications of graph contractions
✍ László Babai 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

## Abstract Results in diverse areas, such as the Nielsen‐Schreier theorem on subgroups of free groups and a proof of A. T. White's conjecture on the genus of subgroups are shown to be immediate consequences of a lemma which has already proved useful in investigating topological properties and auto

Contractions and hamiltonian line graphs
Contractions and hamiltonian line graphs
✍ Hong-Jian Lai 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

Using the contraction method, we find a best possible condition involving the minimum degree for a triangle-free graph to have a spanning eulerian subgraph.