✦ LIBER ✦

Enumerating Consecutive and Nested Partitions for Graphs

✍ Scribed by F.K. Hwang; G.J. Chang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 116 KB
Volume: 19
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1997.0145

No coin nor oath required. For personal study only.

✦ Synopsis

Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. We extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph. A subset of vertices is considered consecutive if the subgraph induced by the subset is connected. In this sense the partition problem on a set of integers can be treated as a special case when the graph is a line. In this paper we give the number of consecutive and nested partitions when the graph is a cycle. We also give a partial order on general graphs with respect to these numbers.

📜 SIMILAR VOLUMES

Optimality of consecutive and nested tre

Optimality of consecutive and nested tree partitions

✍ Chang, G. J.; Hwang, F. K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called cons

Cycle-cocycle partitions and faithful cy

Cycle-cocycle partitions and faithful cycle covers for locally finite graphs

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract By a result of Gallai, every finite graph __G__ has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in __G__. However, we show that, for t

Sharp bounds for the number of 3-indepen

Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs

✍ F. M. Dong; K. M. Koh; K. L. Teo; C. H. C. Little; M. D. Hendy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract Given a graph __G__ and an integer __k__ ≥ 1, let α(__G, k__) denote the number of __k__‐independent partitions of __G__. Let 𝒦^−s^(__p,q__) (resp., 𝒦~2~^−s^(__p,q__)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph __K~p,q