𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The edge-bandwidth of theta graphs

✍ Scribed by Dennis Eichhorn; Dhruv Mubayi; Kevin O'Bryant; Douglas B. West

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
129 KB
Volume
35
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

An edge-labeling f of a graph G is an injection from E(G) to the set of integers. The edge-bandwidth of G is B H (G) min f {B H (f )}, where B H (f ) is the maximum difference between labels of incident edges of G. The theta graph Γ‚(l 1 , F F F ,l m ) is the graph consisting of m pairwise internally disjoint paths with common endpoints and lengths l 1 Á Á Á l m . We determine the edge-bandwidth of all theta graphs.

πŸ“œ SIMILAR VOLUMES

Bandwidth of theta graphs with short pat
Bandwidth of theta graphs with short paths
✍ G.W. Peck; Aditya Shastri πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 628 KB

Peck, G.W. and A. Shastri, Bandwidth of theta graphs with short paths, Discrete Mathematics 103 (1992) 177-187. The bandwidth problem for a graph is that of labelling its vertices with distinct integers so that the maximum difference across an edge is minimized. We here solve this problem for all

On the Chromatic Roots of Generalized Th
On the Chromatic Roots of Generalized Theta Graphs
✍ Jason I. Brown; Carl Hickman; Alan D. Sokal; David G. Wagner πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 242 KB

The generalized theta graph G s1, ..., sk consists of a pair of endvertices joined by k internally disjoint paths of lengths s 1 , ..., s k \ 1. We prove that the roots of the chromatic polynomial p(G s1, ..., sk , z) of a k-ary generalized theta graph all lie in the disc |z -1| [ [1+o(1)] k/log k,

The bandwidth problem and operations on
The bandwidth problem and operations on graphs
✍ J Chvatalova; J Opatrny πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 479 KB

For a given graph G and vertices u, v in G let ,,,~ ~(.,~) G(-,,o) G~, o) denote the graph Gm ~ Va , ~s :, obtained from G by merging vertices u, v, adding edge (u, v), subdividing edge (u, v), contracting edge (u, v) of G, respectively. We give upper and lower bounds for the bandwidth of ~'~ ~(~'~)

The edge reconstruction of hamiltonian g
The edge reconstruction of hamiltonian graphs
✍ L. Pyber πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 305 KB πŸ‘ 1 views

## Abstract If a graph __G__ on __n__ vertices contains a Hamiltonian path, then __G__ is reconstructible from its edge‐deleted subgraphs for __n__ sufficiently large.

On the size of graphs of a given bandwid
On the size of graphs of a given bandwidth
✍ Ronald D. Dutton; Robert C. Brigham πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 489 KB

The relationship between the graphical invariants bandwidth and number of edges is considered. Bounds, some sharp and others improvements of known results, are given for the nznber of edges of graphs having a given bandwidth. An important invariant of undirected graphs having no loops or multiple e