Bandwidth reduction in rectangular grids

Bandwidth reduction in rectangular grids

We show that the bandwidth of a square twodimensional grid of arbitrary size can be reduced if two (but not less than two) edges are deleted. The two deleted edges may not be chosen arbitrarily, but they may be chosen to share a common endpoint or to be non-adjacent. We also show that the bandwi...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2007
Hauptverfasser: Andreescu, T., Stromquist, W., Sunic, Z.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2007
Schriftenreihe:Algebra and Discrete Mathematics
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/157342
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Bandwidth reduction in rectangular grids / T. Andreescu, W. Stromquist, Z. Sunic // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 1–15. — Бібліогр.: 3 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-157342
record_format dspace
spelling irk-123456789-1573422019-06-21T01:30:15Z Bandwidth reduction in rectangular grids Andreescu, T. Stromquist, W. Sunic, Z. We show that the bandwidth of a square twodimensional grid of arbitrary size can be reduced if two (but not less than two) edges are deleted. The two deleted edges may not be chosen arbitrarily, but they may be chosen to share a common endpoint or to be non-adjacent. We also show that the bandwidth of the rectangular n × m (n ≤ m) grid can be reduced by k, for all k that are sufficiently small, if m − n + 2k edges are deleted. 2007 Article Bandwidth reduction in rectangular grids / T. Andreescu, W. Stromquist, Z. Sunic // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 1–15. — Бібліогр.: 3 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 05C78. http://dspace.nbuv.gov.ua/handle/123456789/157342 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description We show that the bandwidth of a square twodimensional grid of arbitrary size can be reduced if two (but not less than two) edges are deleted. The two deleted edges may not be chosen arbitrarily, but they may be chosen to share a common endpoint or to be non-adjacent. We also show that the bandwidth of the rectangular n × m (n ≤ m) grid can be reduced by k, for all k that are sufficiently small, if m − n + 2k edges are deleted.
format Article
author Andreescu, T.
Stromquist, W.
Sunic, Z.
spellingShingle Andreescu, T.
Stromquist, W.
Sunic, Z.
Bandwidth reduction in rectangular grids
Algebra and Discrete Mathematics
author_facet Andreescu, T.
Stromquist, W.
Sunic, Z.
author_sort Andreescu, T.
title Bandwidth reduction in rectangular grids
title_short Bandwidth reduction in rectangular grids
title_full Bandwidth reduction in rectangular grids
title_fullStr Bandwidth reduction in rectangular grids
title_full_unstemmed Bandwidth reduction in rectangular grids
title_sort bandwidth reduction in rectangular grids
publisher Інститут прикладної математики і механіки НАН України
publishDate 2007
url http://dspace.nbuv.gov.ua/handle/123456789/157342
citation_txt Bandwidth reduction in rectangular grids / T. Andreescu, W. Stromquist, Z. Sunic // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 1–15. — Бібліогр.: 3 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT andreescut bandwidthreductioninrectangulargrids
AT stromquistw bandwidthreductioninrectangulargrids
AT sunicz bandwidthreductioninrectangulargrids
first_indexed 2025-07-14T09:47:14Z
last_indexed 2025-07-14T09:47:14Z
_version_ 1837615216307732480
fulltext Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2007). pp. 1 – 15 c© Journal “Algebra and Discrete Mathematics” Bandwidth reduction in rectangular grids Titu Andreescu, Water Stromquist, Zoran Šunić Dedicated to V.I. Sushchansky on the occasion of his 60th birthday Abstract. We show that the bandwidth of a square two- dimensional grid of arbitrary size can be reduced if two (but not less than two) edges are deleted. The two deleted edges may not be chosen arbitrarily, but they may be chosen to share a common endpoint or to be non-adjacent. We also show that the bandwidth of the rectangular n × m (n ≤ m) grid can be reduced by k, for all k that are sufficiently small, if m − n + 2k edges are deleted. Introduction We consider only simple undirected graphs (no loops, no multiple edges). A vertex numbering of a graph G = (V, E) is a bijective map ν : V → [k] from the vertex set V of G to the set of the first k positive integers [k] = {1, 2, . . . , k}, where k = |V |. The absolute value of the difference between the numbers at the two endpoints of an edge e in E is denoted by fν(e) and called the length of e induced by ν. Thus any vertex numbering of G induces an edge labeling fν : E → Z+ of G by positive integers. The largest length of an edge in E (i.e. the largest label used by fν) is called the bandwidth of the numbering ν. If the edge set is empty the bandwidth is 0 by definition. The smallest possible bandwidth, taken over all possible vertex numberings of G, is called the bandwidth of the graph G. Sometimes the adjective “linear” is used due to the following phys- ical interpretation. Every vertex numbering ν corresponds to a linear arrangement of the graph G in which the vertex v in V is placed at the The third author was partially supported by NSF grant DMS-0600975 2000 Mathematics Subject Classification: 05C78. Key words and phrases: linear bandwidth, rectangular grid. Jo u rn al A lg eb ra D is cr et e M at h .2 Bandwidth reduction in rectangular grids number ν(v) on the real line. The (linear) bandwidth of a linear arrange- ment is then just the length of the longest wire needed to assemble the graph G and the minimal such bandwidth, taken over all possible linear arrangements of G, is the (linear) bandwidth of G. Another interpretation is related to the adjacency matrix of G. Namely, every numbering ν of the graph G induces a corresponding adja- cency matrix Mν(G) of G (the row i column j entry in Mν(G) is 1 if the vertices labeled by i and j are adjacent and it is 0 otherwise). The band- width of the numbering ν is then just the largest distance from a nonzero entry in Mν(G) to the diagonal of the matrix and the bandwidth of the graph is the minimal such distance over all possible numberings. There- fore, a graph G has bandwidth b if and only if there exists an ordering of the vertices of G such that all nonzero entries of the corresponding ad- jacency matrix are inside the bandwidth consisting of the main diagonal and the b adjacent diagonals along the main diagonal on both sides. Two-dimensional rectangular grid Gn,m, where 1 ≤ n ≤ m, is the graph whose vertices are the points in the set V = [n]× [m] = {(i, j)|1 ≤ i ≤ n, 1 ≤ j ≤ m} with an edge between two vertices if and only if the Euclidean distance between them is 1 (think of the natural embedding of the vertex set in the Cartesian plane). We write Gn for the square grid Gn,n. It is well known that the bandwidth of the rectangular grid Gn,m is n, unless m = n = 1. Theorem A (J. Chvátalová [1]). Let 1 ≤ n ≤ m. If m ≥ 2, then the bandwidth of the two-dimensional rectangular grid Gn,m is n. The above result is also obtained in [3] by using a technique involving estimates on the size of the boundary of subsets of vertices in the grid and we utilize the same approach in our considerations. The bandwidth of a graph is measuring how difficult it is to embed the graph on a line. The following result provides some refinement of this measure for the rectangular grids. Theorem B (P. Fishburn and P. Wright [2]). Let 1 ≤ n ≤ m. Every vertex numbering of Gn,m of bandwidth n induces at least 2(n − 1) + n(m − n) edges of length n. Moreover, the down diagonal numbering induces ex- actly 2(n − 1) + n(m − n) edges of length n. As an example, the down diagonal numbering on the square grid Gn Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 3 is given by t + 1 . . . n2 . . . t + 2 . . . 4 . . . . . . . . . 2 5 . . . . . . 1 3 6 . . . t + n , where t = n(n − 1)/2. This numbering has bandwidth n and induces exactly 2(n−1) edges of length n (all horizontal edges incident to vertices on the main diagonal). Note that the down diagonal numbering of Gn that we just displayed indicates that we sometimes think of Gn,m as a rectangular board of dimension n×m (meaning n rows and m columns) in which the squares represent the vertices and any pair of squares that have common side are considered to be neighbors. By the result of Chvátalová, we know that in order to make a linear arrangement of the square grid Gn we must be ready to use pieces of wire of length at least n. Moreover, by the result of Fishburn and Wright, in order to make an arrangement that does not use any pieces longer than n, we must be ready to use at least 2(n − 1) pieces of length n. Thus it seems that the bandwidth n is barely achieved in Gn (there are always many edges of induced length n) and that one would have to delete many edges in order to reduce the bandwidth. Nevertheless, we will prove that, for n ≥ 3, it is sufficient to delete only 2 edges (regardless of n) in Gn and obtain a graph of bandwidth n − 1 and that one cannot reduce the bandwidth by deleting only one edge. 1. Bandwidth reduction The bandwidth of the path Pn of length n − 1 ≥ 1 is 1, of the cycle Cn of length n ≥ 3 is 2, and of the complete graph Kn on n ≥ 1 vertices is n − 1. Deletion of any edge in the cycle Cn produces the path Pn and thus reduces the bandwidth by 1. Similarly, deletion of any edge in Kn reduces the bandwidth by 1. Definition 1. The bandwidth reduction number of a graph G of band- width b, b ≥ 1, is the smallest size of a set of edges whose deletion from G induces a subgraph of bandwidth no greater than b − 1. For example, cycles and complete graphs have bandwidth reduction number 1, while paths have bandwidth reduction number equal to their length. Some more interesting examples follow. Jo u rn al A lg eb ra D is cr et e M at h .4 Bandwidth reduction in rectangular grids Example 1. Consider the wheel Wn, n ≥ 3, a graph on n+1 vertices that consists of a cycle of length n together with a “center” vertex connected to every vertex in the cycle by an edge. The following table provides the bandwidth and the bandwidth reduction number of the wheel graphs. We do not provide the easy proofs, but we note the exceptional case of W6, which is the only wheel whose bandwidth reduction number is 3. graph W3 W4 W5 W6 W2m−1 (m ≥ 4) W2m (m ≥ 4) bandwidth 3 3 3 3 m m bandwidth reduction n. 1 1 2 3 1 2 Example 2. Another set of relatively easy examples is provided by the complete bipartite graphs Bn,m, for 1 ≤ n ≤ m. graph B2,2 Bn,2k+1 Bn,2k (k 6= 1 or n 6= 2) bandwidth 2 k + n k + n − 1 bandwidth reduction number 1 1 2 The notion of bandwidth reduction can be further extended as follows. Definition 2. Let G be a graph a graph of bandwidth b, where b ≥ k ≥ 1. The k-th bandwidth reduction number of G, denoted by brk(G), is the smallest size of a set of edges whose deletion from G induces a subgraph of bandwidth no greater than b − k. We note that the k-th bandwidth reduction number of a graph G of bandwidth b is the smallest number of edges e of induced length fν(e) greater than b − k, taken over all possible numberings ν of G, i.e., brk(G) = min ν |{e ∈ E|fν(e) > b − k}| . For example, in the case of the complete graph Kn we have brk(Kn) = 1 + 2 + · · · + k = k(k + 1) 2 , for k = 1, . . . , n − 1, since the bandwidth of Kn is n − 1 and every numbering of Kn induces i edges of length n − i, for i = 1, . . . , n − 1. This implies that if a graph on n vertices has more than n(n − 1) 2 − k(k + 1) 2 edges, then its bandwidth is at least n − k, for k = 1, . . . , n − 1. Before we move on to bandwidth reduction in rectangular grids, we observe that the bandwidth of a graph can be reduced by more than 1 by deletion of a single edge. This is why we require the newly obtained graph to have bandwidth no greater than b− k rather than exactly b− k in the definition of the k-th bandwidth reduction number. Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 5 Example 3. Consider the graph W6n,6n−1, n ≥ 2, obtained by joining two wheels W6n and W6n−1 by connecting their centers by an edge (two wheels and an axle). Note that an arbitrary graph on v vertices with diameter d and band- width b satisfies the inequality 1 + db ≥ v (1) (this is clear since the maximal possible label on a vertex at distance x from the vertex labeled by 1 is 1 + xb). Since the diameter of W6n,6n−1 is 3 and the number of vertices is 12n + 1, inequality (1) shows that the bandwidth of W6n,6n−1 is at least 4n. However, deletion of the edge between the centers of the two wheels leads to a graph of bandwidth 3n. Thus br1(W6n,6n−1) = br2(W6n,6n−1) = · · · = brn(W6n,6n−1) = 1, for this graph. In the previous example, a steep reduction in the bandwidth was obtained by removing a bridge from the graph (thus disconnecting the graph). In the following example the bandwidth of a graph is reduced by more than 1 by removing an edge that is not a bridge. Example 4. Consider the graph C ′′ 24 which is obtained from the cycle of length 24 by adding two edges as in Figure 1. Let b be the bandwidth of C ′′ 24. The diameter of this graph is 7 and therefore, by inequality (1), 1 + 7b ≥ 24, which implies that b ≥ 4. On the other hand, removing the edge whose endpoints are labeled by 1 and 24, leads to a graph C ′ 24 of bandwidth 2 (the labeling provided in the figure has bandwidth 2 on the induced subgraph C ′ 24). 2. Bandwidth reduction in rectangular grids We give now an upper bound on the k-th bandwidth reduction number in rectangular grids, for sufficiently small k. Theorem 1. Let m ≥ n > 2k. The k-th bandwidth reduction number of the rectangular grid Gn,m satisfies the inequality brk(Gn,m) ≤ m − n + 2k. We construct an example of a numbering ν of Gn,m in which at most m − n + 2k edges are longer than n − k. The example is a modification of the down diagonal numbering. Jo u rn al A lg eb ra D is cr et e M at h .6 Bandwidth reduction in rectangular grids 8 6 4 18161412 22 2420 2 1 10 3 5 7 9 11 13 15 17 19 23 21 Figure 1: Graph C ′′ 24 Think of Gn,m as of a rectangular board of dimension n × m. First modify the board by cutting out the lower right part of the board of dimension k×(m−n+k+1) and flipping it over as indicated in Figure 2. �������������� �������������� �������������� �������������� �������������� �������������� �������������� �������������� �������������� �������������� �������������� �������������� k k k m m−n+k+ m−n+k+ n−k 1 1 B C A n−k−1 D E Figure 2: A numbering of Gm,n with at most m − n + 2k edges longer than n − k Enumerate all the squares in the modified board in the down diagonal fashion. We claim that the bandwidth of this numbering of the modified bard is n − k (the statements that follow will be made more precise in Lemma 1 and the proof of Theorem 1 below). Consider a vertex A on a diagonal of length n−k−1. The vertical edges incident to A have length Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 7 n − k − 1 and the horizontal ones have length (n − k − 1) + 1 = n − k. A vertex B on a diagonal of length n − k is incident to horizontal edges of length n− k and vertical edges of length (n− k)− 1. A vertex C that lives on a diagonal of length k is incident to vertical edges of length k and horizontal edges of length k+1 = 2k+1−k ≤ n−k, where the inequality comes from the assumption that 2k < n. In all other “atypical” cases, near the bottom left or the upper right corner(s) of the modified board, the diagonals are even shorter, which implies that the incident edges are also shorter. Thus the bandwidth of the given numbering of the modified board is n − k. After we flip back the modified part of the board to its original position the newly created k horizontal edges (between the non-shaded and the shaded part of the board) may have length longer than n − k and all but one of the newly created m − n + k + 1 vertical edges may have length longer than n−k. Indeed the induced length of the rightmost vertical edge between the shaded and the non-shaded part is exactly n−k, since its endpoints (denoted by D and E in Figure 2) were (horizontal) neighbors in the modified board. In order prove Theorem 1 more formally, we introduce an auxiliary graph that we call a corridor (see Figure 3). The squares in the figure represent vertices and two vertices are neighbors if their corresponding squares share a common edge. The graph consists of 3 pieces, namely two vertical pieces of width w − 1 and one horizontal piece of width w. We call such a graph a corridor of size w. Note that the lengths of any of the three pieces of the corridor are irrelevant for our purposes. Lemma 1. Any subgraph of the corridor of size w has bandwidth no larger than w. Proof. The claim follows from the fact that the bandwidth of a subgraph does not exceed the bandwidth of the graph, once we prove that the bandwidth of the corridor of size w is no larger than w. The down diagonal numbering of the corridor has bandwidth w. Namely, start at vertex A, then go down the diagonal toward B, move to the next diagonal in the same fashion (always starting from the left end), and so on. We claim that all horizontal edges have length w and all vertical edges have length w − 1. Indeed, since the length of every diagonal in the vertical pieces is w−1, the length of the vertical edges involving such diagonals is w− 1 and the length of the horizontal edges is w − 1 + 1 = w (this is true even for the two diagonals that are neighboring the horizontal piece of the corridor). On the other hand, the length of the diagonals in the horizontal piece is Jo u rn al A lg eb ra D is cr et e M at h .8 Bandwidth reduction in rectangular grids B w−1 w−1 w A Figure 3: A corridor of size w w, implying that the length of the horizontal edges is w and the length of the vertical ones is w − 1. We note in passing that the bandwidth of any subgraph of a corridor in which the vertical pieces have width w and the horizontal one has width w − 1 is also not larger than w (the appropriate numbering starts at B, fills the diagonal toward A, and then moves on to the next diagonal in the same fashion). Proof of Theorem 1. The condition 2k < n implies that k < n − k and therefore the modified board fits inside a corridor of size n − k. Example 5. We provide an example illustrating the preceding result. Assume that we want to reduce the bandwidth of G8 to 6. Thus n = Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 9 m = 8, k = 2 and the numbering of the modified board is given by 26 32 38 44 50 56 61 64 21 27 33 39 45 51 57 62 16 22 28 34 40 46 52 58 11 17 23 29 35 41 47 53 59 63 7 12 18 24 30 36 42 48 54 60 4 8 13 19 25 31 37 43 49 55 2 5 9 14 20 1 3 6 10 15 Recall that another way to state Theorem 1 is to say that the incidence matrix of Gn,m can be written in such a way that all non-zero entries, except for m − n + 2k symmetric pairs, are within distance n − k from the main diagonal. In particular, this means that the incidence matrix of the square grid Gn can be written in such a way that all non-zero entries, except for 2 exceptional symmetric pairs, are within distance n − 1 from the main diagonal. This contrasts nicely with Theorem B. Note that the numbering indicated in the proof of Theorem 1 in the case of a square grid has the property that the two exceptional edges (the ones that need to be deleted) share a common vertex. This is certainly not necessary as the next example shows. Example 6. Consider the numbering of G6 given by 33 29 25 30 34 36 11 16 21 26 31 35 7 12 17 22 27 32 4 8 13 18 23 28 2 5 9 14 19 24 1 3 6 10 15 20 . Following the same pattern, we may always construct a numbering of Gn, n ≥ 3, in which only the two leftmost vertical edges between the top two rows, have lengths longer than n − 1 (and these length are 5n − 8 and 3n − 5). We show now that the bandwidth of square grids cannot be reduced if only 1 edge is deleted. The exceptional cases are n = 1 and n = 2. Indeed, G1 has bandwidth 0 which cannot be reduced, while G2 is the cycle C4 and its bandwidth reduction number is 1. Theorem 2. Let n ≥ 3. The bandwidth reduction number of Gn is 2. The edges that need to be deleted may, but do not have to, share a common endpoint. Jo u rn al A lg eb ra D is cr et e M at h .10 Bandwidth reduction in rectangular grids Proof. For an arbitrary numbering ν of Gn, call an edge long if its induced length is at least n and call it short otherwise. An example of a numbering of Gn, for n ≥ 3, with only two long edges is already provided in the proof of Theorem 1. We note that the two long edges in that example share a common vertex, namely the vertex in row n column n − 1. The lengths of the long edges are 5n− 7 and 3n− 4. Example 6 provides numberings in which the two long edges do not share a common vertex. It remains to be shown that every numbering of Gn, n ≥ 3, has at least two long edges. Let ν be an arbitrary labeling of Gn. Choose the smallest k such that all rows or all columns of Gn have a label in [k]. Without loss of generality we may assume that all rows have a label in [k]. Define the partial numbering κ of Gn to be the numbering of the vertices obtained from the numbering ν by deletion of the labels greater than k (thus only k vertices have a label). Claim 1. The label k is alone in its row in the partial numbering κ. Otherwise each row would have a label from [k−1] which contradicts the minimality in the choice of k. Claim 2. No row is completely numbered by κ. Otherwise each column would have a label from [k − 1] (note that k is not in the fully numbered row by Claim 1). This again contradicts the minimality in the choice of k. Call an edge between a vertex numbered by an element in [k] and an element not in [k] a boundary edge. Call an endpoint of a boundary edge a boundary vertex. More precisely, call a boundary vertex numbered by κ an interior boundary vertex and a boundary vertex not numbered by κ an exterior boundary vertex. If there are at least n + 1 interior boundary vertices or at least n + 1 exterior boundary vertices, then there would be at least two long edges in ν (in the former case the two lowest labels on the boundary vertices are too small and in the latter the two largest labels on the boundary vertices are too large). Assume that there are no more than n interior and no more than n exterior boundary vertices. A direct corollary of Claim 2 is that each row has at least one hori- zontal boundary edge. Thus there is exactly one interior boundary vertex in each row, exactly one exterior boundary vertex in each row and they are paired up by n horizontal boundary edges. At least one of these n horizontal boundary edges must be long (apropos, this proves Theorem A in the case of square grids). We assume that this is the only long edge in ν and we seek a contradiction. Claim 3. The endpoints of the n−1 short horizontal boundary edges Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 11 are numbered by the pairs (k, k + n− 1), (k − 1, k + n− 2), (k − 2, k + n− 3), . . . , (k − n + 2, k + 1), while the endpoints of the long edge come from a pair (s, ℓ), where s is a “small” number less than or equal to k − n + 1 and ℓ is a “large” number greater or equal to k + n. Indeed, any other numbering of the boundary vertices would result in at least two long horizontal edges. Claim 4. For every row i in Gn, the vertices labeled by the partial numbering κ form a horizontal path pi that ends at the leftmost or the rightmost column. This follows from the fact that every row has exactly one interior boundary vertex and exactly one exterior boundary vertex. Thus each row contains a unique maximal path that consists of vertices numbered by κ. These n paths will be called κ-paths. Claim 5. The κ-path in any row next to the vertex labeled by k consists of a single vertex in the column of k. Indeed, if the neighboring row has a vertex labeled by κ that is not in the same column as k, this vertex would be involved in a vertical edge that would have to be long (all vertices in the row of k, with the exception of k itself, are labeled by numbers greater or equal to k + n − 1). Since every row contains vertices labeled by κ and k is the only labeled vertex in its row, any neighboring row has a single vertex numbered by κ, which is in the same column as k. Without loss of generality, by Claim 4 and Claim 5, we may assume that the vertex k (together with its vertical neighbors from [k]) is in the leftmost column in Gn. Denote the κ-path that contains the label s by ps (this is the row containing the long edge). Claim 6. The κ-path in any row next to ps extends over the same columns as ps does. Recall that s ≤ n− k + 1. All other vertices in ps are also labeled by numbers that are smaller or equal to n− k + 1. All vertices in the row of s that are not in ps are labeled by numbers that are greater or equal to n + k. Therefore if a vertex in a row next to ps is next to a vertex in ps it must be labeled by κ and if it is next to a vertex that is not in ps then it must not be labeled by κ (otherwise a vertical long edge would exist). Claim 7. If the κ-path p is no longer than n−2, then the κ-path q in any neighboring row occupies the same columns as p or differs in exactly one column. Again, in any other case there would be a long vertical edge involving a number from [k] and a number greater than n + k − 1. Note that we Jo u rn al A lg eb ra D is cr et e M at h .12 Bandwidth reduction in rectangular grids required that the length of p should be no longer than n − 2, since if the length is n − 1 the neighboring κ-path q may also have length n − 1 and start at the opposite end without creating additional long vertical edge(s). However, we will see that this does not happen. Claim 8. No horizontal κ-path is longer than n−2 and they all start at the left end. The length of the κ-path k is 1 and so is the length of the neighboring κ-path(s) and they all start at the left end. Going further away, by Claim 7, the length of the κ-paths can only go up by 1 from one row to another, except that the length does not change in the rows next to ps. Thus the longest κ-path cannot be longer than n− 2 (and n− 2 is only possible if k is in the bottom row and ps is in the top row or the other way around). We now consider the partial numbering τ that corresponds to the set of numbers [k + n − 1]. As observed before, the numbers k + 1, k + 2, . . . , k+n−1 are placed in different rows, one in each row except for the row of the long horizontal edge sℓ. Thus new n − 1 horizontal boundary edges are now formed between the vertices numbered by [k + n − 1] and those not numbered by [k+n−1]. These n−1 horizontal boundary edges correspond to n − 1 external (with respect to τ) boundary vertices. In addition, the vertex labeled by ℓ is also an external boundary vertex with respect to τ (by Claim 6), which is incident to a new vertical boundary edge. Thus, there are at least n external boundary vertices each of which is an endpoint of a boundary edge (with respect to τ) that is different from sℓ. This implies that at least one of these boundary edges is long and we have a second long edge. 3. Final remarks 3.1. Relation to the vertex-isoperimetric number For a numbering ν of a graph G = (V, E) one can define the vertex- isoperimetric number of ν to be the maximum size of a set of vertices in G numbered by [k] that have neighbors that are not numbered by [k], where the maximum is taken over all k = 0, . . . , |V |. The smallest pos- sible vertex-isoperimetric number, taken over all numberings of G, is the vertex-isoperimetric number of the graph G. If bw(G) is the bandwidth of G and vi(G) is its vertex-isoperimetric number then bw(G) ≥ vi(G). It is well known that the vertex-isoperimetric number of the square grid Gn is n (see [3]). The down diagonal numbering provides an example of Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 13 a numbering with vertex-isoperimetric number n and the proof of Theo- rem 2 essentially contains a proof that this number cannot be less than n. Thus in order to reduce the bandwidth of Gn we need to delete enough edges so that at least the vertex-isoperimetric number is reduced. How- ever, one can reduce the vertex-isoperimetric number of Gn by deleting only one edge. For example, consider the case of n = 4 and the numbering given by 7 13 15 16 4 8 12 14 2 5 9 11 1 3 6 10 . If the edge with endpoints labeled by 7 and 13 is deleted, the newly obtained graph has vertex-isoperimetric number 3. This indicates that, in general, the problem of bandwidth reduction is more difficult than the problem of vertex-isoperimetric number reduction. It also explains why, in the course of the proof of Theorem 2, it was relatively easy to show that at least one edge needed to be deleted, but one had to work harder for the second edge. 3.2. How good is the bound 2k? Theorem 1 states that the k-th bandwidth reduction number of the square grid Gn is bounded linearly by 2k, for k < n/2, i.e, one has to delete relatively small number of edges to reduce the bandwidth substantially. The proof of Theorem 2 indicates an easy way to see that at least k edges need to be deleted in order to reduce the bandwidth of Gn by k. Namely, the first time some partial numbering has a representative in each row (or each column) there would be at least n horizontal (or vertical) boundary edges at least k of which must have length at least n − k + 1. Thus, for n ≥ 3, k < n/2, we have k ≤ brk(Gn) ≤ 2k. The upper bound gives the correct bandwidth reduction number for k = 1 (Theorem 2) and it is quite possible that the upper bound gives the cor- rect bandwidth numbers for small values of k. We will indicate that there is a better upper bound on brk(Gn), for values of k that are sufficiently close to n/2. Before we do that note that it is clear that for k ≥ n/2 the bandwidth reduction has to eventually get more difficult. A linear bound on the bandwidth reduction number simply cannot be found for all k. After all, for k = n, one needs to remove all 2n(n− 1) edges to get to bandwidth 0. Jo u rn al A lg eb ra D is cr et e M at h .14 Bandwidth reduction in rectangular grids Assume 2k+1 ≤ n and consider the numbering of the square grid Gn given by . . . t − 5 t − 2 t t + 1 t + 3 t + 6 . . . . . . . . . t − 4 t − 1 t + 2 t + 5 . . . 4 . . . . . . t − 3 t + 4 . . . 2 5 . . . . . . . . . . . . 1 3 6 . . . . . . n2 , where t = n(n − k − 1) and the vertical bar separates the board in two boards of dimension n × (n − k − 1) on the left and n × (k + 1) on the right. The numbering follows the down diagonal direction in the left part of the board then switches to the right part and follows the up diagonal direction in this part. Since 2k+2 ≤ n (i.e. k+1 ≤ n−k−1) all induced edges have length at most n−k with the exception of the n critical edges crossing between the two parts of the table. The lengths of the critical edge in row i is i(i − 1) + 1. Thus if r is the largest positive integer such that r(r − 1) + 1 ≤ n − k, the top r critical edges may be kept and the remaining n − r critical edges need to be deleted in order to reach a subgraph of bandwidth n − k. Therefore brk(Gn) ≤ n − r, where r is the largest positive integer such that r(r−1)+1 ≤ n−k. This bound is not as good as the linear bound 2k for small values of k, but it is better than 2k for sufficiently large values of n and k sufficiently close to n/2. For instance for n = 100 and k ∈ {47, 48, 49} the corresponding value of r is r = 7 and we obtain brk(G100) ≤ 93. The 2k bound gives 94, 96, and 98, respectively, for these three values of k, but is sharper than the n − r bound for all k ≤ 46. References [1] Jarmila Chvátalová. Optimal labelling of a product of two paths. Discrete Math., 11:249–253, 1975. [2] Peter Fishburn and Paul Wright. Bandwidth edge counts for linear arrangements of rectangular grids. J. Graph Theory, 26(4):195–202, 1997. [3] William R. Hare, Eleanor O’M Hare and S. T. Hedetniemi. Bandwidth of grid graphs. Congr. Numer., 50:67–76, 1985. Jo u rn al A lg eb ra D is cr et e M at h .T. Andreescu, W. Stromquist, Z. Šunić 15 Contact information T. Andreescu Mathematical Sciences, The University of Texas at Dallas, Richardson, TX 75083- 0688, USA W. Stromquist Swarthmore College, Department of Math- ematics and Statistics, 500 College Avenue, Swarthmore, PA. 19081, USA Z. Šunić Department of Mathematics, Texas A&M University, MS-3368, College Station, TX 77843-3368, USA

Ähnliche Einträge