𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On partitioning the edges of graphs into connected subgraphs

✍ Scribed by M. Jünger; G. Reinelt; W. R. Pulleyblank

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
559 KB
Volume
9
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

For any positive integer s, an s-partition of a graph G = ( ! -( €I is a partition of E into El U E2 U U E k, where 14 = s for 1 I i 5 k -1 and 1 5 1 4 1 5 s and each €; induces a connected subgraph of G. We prove (i) if G is connected, then there exists a 2-partition, but not neces-(ii) if G is 2-edge connected, then there exists a 3-partition, but not (iii) if G is 3-edge connected, then there exists a 4-partition;

(iv) if G is 4-edge connected, then there exists an s-partition for all S.

📜 SIMILAR VOLUMES

Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

On partitioning interval graphs into pro
On partitioning interval graphs into proper interval subgraphs and related problems
✍ Frédéric Gardi 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

In this paper, we establish that any interval graph (resp. circulararc graph) with n vertices admits a partition into at most log 3 n (resp. log 3 n +1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, t

Spanning subgraphs of graphs partitioned
Spanning subgraphs of graphs partitioned into two isomorphic pieces
✍ Anthony Bonato 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract A graph has the neighbor‐closed‐co‐neighbor, or ncc property, if for each of its vertices __x__, the subgraph induced by the neighbor set of __x__ is isomorphic to the subgraph induced by the closed non‐neighbor set of __x__. As proved by Bonato and Nowakowski [5], graphs with the ncc p

Max-min partitioning of grid graphs into
Max-min partitioning of grid graphs into connected components
✍ Becker, Ronald; Lari, Isabella; Lucertini, Mario; Simeone, Bruno 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB 👁 2 views

The partitioning of a rectangular grid graph with weighted vertices into p connected components such that the component of smallest weight is as heavy as possible (the max-min problem) is considered. It is shown that the problem is NP-hard for rectangles with at least three rows. A shifting algorith

Sharp bounds for decompositions of graph
Sharp bounds for decompositions of graphs into completer-partite subgraphs
✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w

On decomposition of r-partite graphs int
On decomposition of r-partite graphs into edge-disjoint hamilton circuits
✍ Renu Laskar; Bruce Auerbach 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 414 KB

Let It'Qn; r) denote the complete s-partite graph Kin, n, '.., n). it is shown hzre that for all even n(r -I) 2, Kfn; P) is the union of n(r -'I)/2 of its Hamilton circrlits which are mutually edge-disjoint, and for all odd nfr -1) 3 1, K(n; P) is the union of b(P -f) -r,,rs f l t ii o I s amilton c