On bandwidth and edgesum for the composition of two graphs
type: Item
instance of: scholarly article
title: On bandwidth and edgesum for the composition of two graphs
zbMATH Open document ID: 0832.05092
DOI: 10.1016/0012-365X(94)00013-9
author: Jiuqiang Liu
author: Kenneth L. Williams
published in: Discrete Mathematics
publication date: 1996-02-20T00:00:00Z
review text: For a graph \(G= (V(G), E(G))\) on \(n\) vertices, let \(F(G)\) denote the set of all \(1- 1\) mappings \(f: V(G)\to \{1, 2,\dots, n\}\), called (proper) numberings of \(G\). Then \[ B(G):= \min_{f\in F(G)} \max_{uv\in E(G)} |f(u)- f(v)| \] is the bandwidth of \(G\), and \[ s(G):= \min_{f\in F(G)} \sum_{uv\in E(G)} |f(u)- f(v)| \] is the edgesum of \(G\). For graphs \(G\), \(H\), the composition \(G[H]\) is the graph with vertex set \(V(G)\times V(H)\) and edge set \(E(G[H]):= \{ab: a= (u_1, v_1)\wedge b= (u_2, v_2)\wedge u_1, u_2\in V(G)\wedge v_1, v_2\in V(H)\wedge(u_1 u_2\in E(G)\vee (u_1= u_2\wedge v_1 v_2\in E(H)))\}\); the Cartesian product \(G\times H\) is the graph with vertex set \(V(G)\times V(H)\) and edge set \(E(G\times H):= \{ab: a=(u_1, v_1)\wedge b= (u_2, v_2)\wedge u_1, u_2\in V(G)\wedge v_1, v_2\in V(H)\wedge ((u_1= u_2\wedge v_1 v_2\in E(H))\vee (u_1 u_2\in E(G)\wedge v_1= v_2))\}\). For graphs \(G_1,\dots, G_k\) with \(k\geq 3\), one defines inductively \(G_1\times\cdots\times G_k:= (G_1\times\cdots \times G_{k- 1})\times G_k\). Let \(G_m\), \(T_m\), \(P_m\), \(C_m\) denote respectively, an arbitrary graph, tree, path, cycle on \(m\) vertices. With these denotations the authors determine: (1) the bandwith \(B(K_n[G_m])\) under some additional suppositions on \(G_m\), especially for \(K_n[P_m]\), \(K_n[T_m]\), \(K_n[C_m]\), \(K_n[P_{m_1}\times\cdots\times P_{m_k}]\), \(K_n[C_{m_1}\times\cdots \times C_{m_k}]\); further \(B(K_{1, n}[G_m])\), and (2) the optimal numberings \(f\) for the edgesums \(s(K_n[P_m])\) and \(s(K_n[C_m])\).
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 790551
zbMATH Keywords: bandwidth
zbMATH Keywords: edgesum
zbMATH Keywords: composition
zbMATH Keywords: Cartesian product
zbMATH Keywords: tree
zbMATH Keywords: path
zbMATH Keywords: cycle
reviewed by: Günter Schaar
MaRDI profile type: Publication
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q4842753
cites work: On optimal linear arrangements of trees
cites work: Q3803160
cites work: Optimal labelling of a product of two paths
cites work: The bandwidth problem and operations on graphs
cites work: Complexity Results for Bandwidth Minimization
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Optimal Assignments of Numbers to Vertices
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q4192107
cites work: Assignment of Numbers to Vertices
cites work: Q4305531
cites work: Q4028466
cites work: Optimal Numberings of an $N \times N$ Array
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Q3139716
Wikidata QID: Q127704201
description: scientific article; zbMATH DE number 790551