✦ LIBER ✦

Atoll decompositions of graphs

✍ Scribed by Fred Buckley

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 352 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060308

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An island decomposition of a graph G consists of a set of vertex‐disjoint paths which cover the vertex set of G. If the endpoints of the paths are mutually nonadjacent, then we have an atoll decomposition. We characterize graphs requiring two paths in an island decomposition yet having no atoll decomposition. Results are given relating atoll decompositions to cutpoints and Hamiltonian blocks.

📜 SIMILAR VOLUMES

Commuting decompositions of complete gra

Commuting decompositions of complete graphs

✍ Saieed Akbari; Allen Herman 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract We say that two graphs __G__ and __H__ with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number __r__, the complete multigraph __K__ is decomposable into commuting perfect matchings if and only if __n__ is a 2‐power. Also

Decompositions of graphs into trees

✍ Zbigniew Lonc 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

Circuit Decompositions of Eulerian Graph

Circuit Decompositions of Eulerian Graphs

✍ Genghua Fan; Cun-Quan Zhang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 312 KB

P4-decompositions of regular graphs

✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

Hamilton decompositions of some line gra

Hamilton decompositions of some line graphs

✍ David A. Pike 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

## Abstract The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if __G__ is a bipartite (2__k__ + 1)‐regular graph that is Hamilton decomposable, then the line graph, __L__(__G__), of __G__ is also Hamilton decomposable. A similar

Circuit decompositions of join-covered g

Circuit decompositions of join-covered graphs

✍ Marcelo H. de Carvalho; C. H. C. Little 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching cov