Bandwidth, edgesum and profile of graphs
Yung‐Ling Lai · ScholarWorks - WMU (Western Michigan University) · 1997
For graph $G=(V, E)$, each 1-1 mapping $f:V\to\{(1, 2,\... , \vert V\vert\}$ is called proper numbering G. The bandwidth graph G is min max $\vert f(u)-f(v)\vert$ where the maximum is taken over each edge $uv\in E(G)$, and the minimum is over all proper numberings f. For graphs in general it is well known that the decision problem associated with finding bandwidth is NP-complete. The edgesum G is the number min $\sigma\sb{uv\in E}\vert f(u)-f(v)\vert$, where the minimum is taken over all proper numberings f. Determination the edgesum for arbitrary graphs is known to be NP-complete. For proper numbering f, the $profile width w\sb{f}(v) of a vertex v$ in graph G is the number $w\sb{f}(v)={\rm max}\sb{x\in N\lbrack v\rbrack}(f(v)-f(x))$ where $N\lbrack v\rbrack =\{x\in V:x=v {\rm or} xv\in E\}$ is the closed neighborhood v. The profile graph G is min $\Sigma\sb{u\in V(G)} w\sb{f}$ where the minimum is taken over all proper numberings f. It is known that determination the profile for arbitrary graphs is NP-complete. The graph parameters bandwidth, edgesum and profile are examined in detail. The results an extensive survey as to the solved bandwidth, edgesum and profile problems for classes graphs are presented. Graphs are appropriate models for many computer applications. Several application areas are discussed. The exact values the profile the composition path with other graphs, cycle with other graphs, complete graph with other graphs and complete bipartite graph with other graphs are given. The exact value the bandwidth butterfly is established. A polynomial time approximation algorithm to find the edgesum and profile butterfly is presented. An approximation algorithm to find the profile hypercube is presented. Several tight bounds on the profile the corona two graphs are developed and the exact value the profile the tensor product path with complete bipartite graph is provided.