✦ LIBER ✦

The spectrum problem for the Petersen graph

✍ Scribed by Adams, Peter; Bryant, Darryn E.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 305 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199606)22:2<175::aid-jgt8>3.0.co;2-k

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that there exists a decomposition of K,, into edge-disjoint copies of the Petersen graph if and only if 'u = 1 or 10 (mod 151, 'u # 10.

📜 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

Decomposition algorithms for the maximum

Decomposition algorithms for the maximum-weight connected graph problem

✍ Heungsoon Felix Lee; Daniel R. Dooly 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB

Tabu search for the Steiner problem in g

Tabu search for the Steiner problem in graphs

✍ Celso C. Ribeiro; Maurício C. De Souza 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 2 views

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based o

A note on the bottleneck graph partition

A note on the bottleneck graph partition problem

✍ Klinz, Bettina; Woeginger, Gerhard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 47 KB 👁 2 views

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem wit

A branch and cut algorithm for the Stein

A branch and cut algorithm for the Steiner problem in graphs

✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

The cardinality-constrained shortest pat

The cardinality-constrained shortest path problem in 2-graphs

✍ Geir Dahl; Bjørnar Realfsen 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB