Antibandwidth and cyclic antibandwidth of meshes and hypercubes

The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle C_n, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

The local spectra of regular line graphs

The local spectrum of a graph G=(V,E), constituted by the standard eigenvalues of G and their local multiplicities, plays a similar role as the global spectrum when the graph is “seen” from a given vertex. Thus, for each vertex i∈V, the i-local multiplicities of all the eigenvalues add up to 1; whereas the multiplicity of each eigenvalue λ of G is the sum, extended to all vertices, of its local multiplicities.In this work, using the interpretation of an eigenvector as a charge distribution on the vertices, we compute the local spectrum of the line graph LG in terms of the local spectrum of the regular graph G it derives from. Furthermore, some applications of this result are derived as, for instance, some results about the number of circuits of LG.     

Partitioning a graph into alliance free sets

A strong defensive alliance in a graph G=(V,E) is a set of vertices A⊆V, for which every vertex v∈A has at least as many neighbors in A as in V−A. We call a partition A,B of vertices to be an alliance-free partition, if neither A nor B contains a strong defensive alliance as a subset. We prove that a connected graph G has an alliance-free partition exactly when G has a block that is other than an odd clique or an odd cycle.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

An inequality on the edge lengths of triangular meshes

We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879-895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh.     

Occupation games on graphs in which the second player takes almost all vertices

Given a connected graph G=(V,E), two players take turns occupying vertices v∈V by placing black and white tokens so that the current vertex sets B,W⊆V are disjoint, B∩W=0?, and the corresponding induced subgraphs G[B] and G[W] are connected any time. A player must pass whenever (s)he has no legal move. (Obviously, after this, the opponent will take all remaining vertices, since G is assumed connected.) The game is over when all vertices are taken, V=B^∗∪W^∗. Then, Black and White get b=|B^∗|/|V| and w=|W^∗|/|V|, respectively. Thus, the occupation game is one-sum, b+w=1, and we could easily reduce it to a zero-sum game by simply shifting the payoffs, b^′=b−1/2,w^′=w−1/2. Let us also notice that b≥0 and w≥0; moreover, b>0 and w>0 whenever |V|>1.[Let us remark that the so-called Chinese rules define similar payoffs for the classic game of GO, yet, the legal moves are defined in GO differently.]Like in GO, we assume that Black begins. It is easy to construct graphs in which Black can take almost all vertices, more precisely, for each ε>0 there is a graph G for which b>1−ε. In this paper we show that, somewhat surprisingly, there are also graphs in which White can take almost all vertices.     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637-1650.] as the smallest integer k such that there is a linear layout ?:V→{1,…,|V|} such that for every 1?i<|V| the vertices u with ?(u)?i can be divided into at most k subsets each members having the same neighbours with respect to the vertices v with ?(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.     

On approximation of max-vertex-cover

We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G=(V,E), where |V|=n⩾k, such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k>(3/4)n, and a simple randomized algorithm for k>(1/2)n. Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k, our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.     

Global defensive alliances in star graphs

A defensive alliance in a graph G=(V,E) is a set of vertices S⊆V satisfying the condition that, for each v∈S, at least one half of its closed neighbors are in S. A defensive alliance S is called a critical defensive alliance if any vertex is removed from S, then the resulting vertex set is not a defensive alliance any more. An alliance S is called global if every vertex in V(G)?S is adjacent to at least one member of the alliance S. In this paper, we shall propose a way for finding a critical global defensive alliance of star graphs. After counting the number of vertices in the critical global defensive alliance, we can derive an upper bound to the size of the minimum global defensive alliances in star graphs.     

Upper minus total domination in small-degree regular graphs

A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)?f(v) for every v∈V(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.     

On explicit formulas for bandwidth and antibandwidth of hypercubes

The Hales numbered n-dimensional hypercube exhibits interesting recursive structures in n. These structures lead to a very simple proof of the well-known bandwidth formula for hypercubes proposed by Harper, whose proof was thought to be surprisingly difficult. Harper also proposed an optimal numbering for a related problem called the antibandwidth of hypercubes. In a recent publication, Raspaud et al. approximated the hypercube antibandwidth up to the third-order term. In this paper, we find the exact value in light of the above recursive structures.