✦ LIBER ✦

Embedding of graphs in two-irregular graphs

✍ Scribed by M. Axenovich; Z. Füredi

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 90 KB
Volume: 36
Category: Article
ISSN: 0364-9024
DOI: 10.1002/1097-0118(200102)36:2<75::aid-jgt3>3.0.co;2-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Induced embeddings in Steinhaus graphs

✍ Delahan, Franz A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 1 views

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n -1)/2 + 1. The vertices for each graph in S are the first n(n -1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i -1)/2 + 1 for the first n positive integers i.

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 1 views

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.

3-Coloring graphs embedded in surfaces

✍ Zhao, Yue 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 2 views

In this article, we show that there exists an integer k(Σ)

Small congestion embedding of graphs int

Small congestion embedding of graphs into hypercubes

✍ Matsubayashi, Akira; Ueno, Shuichi 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hype

Minimum bandwidth problem for embedding

Minimum bandwidth problem for embedding graphs in cycles

✍ Lin, Yixun 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 2 views

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.

On convex embeddings of planar 3-connect

On convex embeddings of planar 3-connected graphs

✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi