On bandwidth and edgesum for the composition of two graphs

DOI10.1016/0012-365X(94)00013-9MaRDI QIDQ1897434zbMATH OpenWikidataFDO

Authors Jiuqiang Liu, Kenneth L. Williams

Publication date 20 February 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00013-9

zbMATH Keywords

bandwidth Cartesian product composition cycle edgesum path tree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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])\).

Recommendations

Cites work

Cited in

(12)

This page was built for publication: On bandwidth and edgesum for the composition of two graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897434)