✦ LIBER ✦

Star partitions of graphs

✍ Scribed by Egawa, Y.; Kano, M.; Kelmans, Alexander K.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 78 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199707)25:3<185::aid-jgt2>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition

, and (ii) for every subset S of V (G), G \ S has at most n|S| components with the property that each of their blocks is an odd order complete graph.

📜 SIMILAR VOLUMES

The bottleneck graph partition problem

✍ Hochbaum, Dorit S.; Pathria, Anu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 401 KB 👁 2 views

The bottleneck graph partition problem is to partition the nodes of a graph into two equally sized sets, so that the maximum edge weight in the cut separating the two sets is minimum. Whereas the graph partition problem, where the sum of the edge weights in the cut is to be minimized, is NP-hard, th

Algorithms for graph partitioning on the

Algorithms for graph partitioning on the planted partition model

✍ Anne Condon; Richard M. Karp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

Partition graphs for finite symmetric gr

Partition graphs for finite symmetric groups

✍ Conder, Marston; Morton, Margaret; Praeger, Cheryl E. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

This paper outlines an investigation of a class of arc-transitive graphs admitting a f inite symmetric group S n acting primitively on vertices, with vertex-stabilizer isomorphic to the wreath product S m wr S r (preserving a partition of {1, 2, . . . , n} into r parts of equal size m). Several prop

Hamiltonian-laceability of star graphs

✍ Sun-Yuan Hsieh; Gen-Huey Chen; Chin-Wen Ho 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 1 views

Star factorizations of graph products

✍ Darryn E. Bryant; Saad I. El-Zanati; Charles Vanden Eynden 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

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 👁 1 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