✦ LIBER ✦

Bandwidth of theta graphs with short paths

✍ Scribed by G.W. Peck; Aditya Shastri

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 628 KB
Volume: 103
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90268-k

No coin nor oath required. For personal study only.

✦ Synopsis

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 theta graphs. These are graphs which consist of two terminal vertices and a number of paths of possibly varying length between these. Chvatalova and Opatrny (1988) resolved this question when each path has (edge) length at least 4 or all paths have length 3.

📜 SIMILAR VOLUMES

The edge-bandwidth of theta graphs

✍ Dennis Eichhorn; Dhruv Mubayi; Kevin O'Bryant; Douglas B. West 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

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

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh

On the Inapproximability of Disjoint Pat

On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints

✍ Bin Ma; Lusheng Wang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 230 KB

In this paper, we study the inapproximability of several well-known optimization problems in network optimization. We show-that the max directed vertex-disjoint paths problem cannot be approximated within ratio 2 log 1&= n unless NP DTIME[2 polylog n ], the max directed edge-disjoint paths problem c

Characterization of edge-colored complet

Characterization of edge-colored complete graphs with properly colored Hamilton paths

✍ Jinfeng Feng; Hans-Erik Giesen; Yubao Guo; Gregory Gutin; Tommy Jensen; Arash Ra 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract An edge‐colored graph __H__ is properly colored if no two adjacent edges of __H__ have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph __G__ has a properly colored Hamilton path if and only if __G__ has a spanning subgraph consisting

Partitions of a graph into paths with pr

Partitions of a graph into paths with prescribed endvertices and lengths

✍ Hikoe Enomoto; Katsuhiro Ota 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k À 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v

Relative length of long paths and cycles

Relative length of long paths and cycles in graphs with large degree sums

✍ Hikoe Enomoto; Jan van den Heuvel; Atsushi Kaneko; Akira Saito 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 601 KB

## Abstract For a graph __G, p__(__G__) denotes the order of a longest path in __G__ and __c__(__G__) the order of a longest cycle. We show that if __G__ is a connected graph __n__ ≥ 3 vertices such that __d__(__u__) + __d__(__v__) + __d__(__w__) ≧ n for all triples __u, v, w__ of independent verti