✦ LIBER ✦

On bandwidth for the tensor product of paths and cycles

✍ Scribed by Lai Yung-Ling; Kenneth Williams

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 530 KB
Volume: 73
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(95)00005-c

No coin nor oath required. For personal study only.

✦ Synopsis

The tensor product of graphs G1 and G2 is defined to be G= (V,E) where V = V(Gl ) x V(G2) and edge ((x~,.YI),(x~,Yz)) EE whenever (xI,xz)EE(GI) and (yl,yz)~E(G2).

We use GI(Tp)G2 to denote G. This paper establishes the bandwidth of the tensor product of a path with a path, a cycle with a path, and a cycle with a cycle. Optimal numberings to achieve each of these bandwidths are provided.

📜 SIMILAR VOLUMES

On optimal orientations of Cartesian pro

On optimal orientations of Cartesian products of even cycles and paths

✍ Koh, K. M.; Tay, E. G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

For a graph G , let D ( G ) be the family of strong orientations of G , and define d ៝ ( G ) Å min{d(D)ÉD √ D(G)}, where d(D) is the diameter of the digraph D. In this paper, we evaluate the values of d ៝ (C 2n 1

The number of Hamiltonian paths and cycl

The number of Hamiltonian paths and cycles on k-colored graphs

✍ David A Klarner 📂 Article 📅 1969 🏛 Elsevier Science ⚖ 239 KB

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

On estimates for the tensor product of t

On estimates for the tensor product of two homogeneous elliptic operators

✍ Dmitrii V. Limanskii 📂 Article 📅 2011 🏛 Springer US 🌐 English ⚖ 204 KB

On the direct sum and tensor product of

On the direct sum and tensor product of matrix games

✍ Bertram Mond 📂 Article 📅 1964 🏛 John Wiley and Sons 🌐 English ⚖ 552 KB

On genus imbeddings of the tensor produc

On genus imbeddings of the tensor product of graphs

✍ Abay-Asmerom, Ghidewon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 566 KB

In this article new genus results for the tensor product H @ G are presented. The second factor G in H @ G is a Cayley graph. The imbedding technique used to establish these results combines surgery and voltage graph theory. This technique was first used by A. T. White [171. This imbedding technique