✦ LIBER ✦

Minimum bandwidth problem for embedding graphs in cycles

✍ Scribed by Lin, Yixun

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 98 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199705)29:3<135::aid-net1>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

For the bandwidth B(G) and the cyclic bandwidth B c (G) of a graph G, it is known that 1 2 B(G) °Bc (G) °B(G). In this paper, the criterion conditions for two extreme cases B c (G) Å B(G) and B c (G) Å 1 2 B(G) are studied. From this, some exact values of B c (G) for special graphs can be obtained.

📜 SIMILAR VOLUMES

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB

Minimum-weight cycles in 3-separable gra

Minimum-weight cycles in 3-separable graphs

✍ Coullard, Collette R.; Gardner, L. Leslie; Wagner, Donald K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, deltawye, w

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 1 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

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

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 1 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be

Examples of embedded eigenvalues for pro

Examples of embedded eigenvalues for problems in acoustic waveguides

✍ M. D. Groves 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

## Communicated by P. Werner This short article discusses the spectrum of the Neumann Laplacian in the infinite domain L1L, n\*2 created by inserting a compact obstacle P into the uniform cylinder "( !R, R); . The main result is the existence of at least one embedded eigenvalue when P is an (n!2)-