The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

Extension of Multiply Transitive Permutation Sets

Let G be a k-transitive permutation set on E and let E* = E∪{∞},∞ ? E; if G* is a (k: + 1)-transitive permutation set on E*, G* is said to be an extension of G whenever G _∝ ^* =G. In this work we deal with the problem of extending (sharply) k- transitive permutation sets into (sharply) (k + 1)-transitive permutation sets. In particular we give sufficient conditions for the extension of such sets; these conditions can be reduced to a unique one (which is a necessary condition too) whenever the considered set is a group. Furthermore we establish necessary and sufficient conditions for a sharply k- transitive permutation set (k ≥ 3) to be a group. Math. Subj. Class.: 20B20 Multiply finite transitive permutation groups 20B22 Multiply infinite transitive permutation groups     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

The Möbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [σ,π] in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2,…,k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142.We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [σ,π] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of (1,π) is either 0, 1 or −1.     

A survey on labeling graphs with a condition at distance two

For positive integers k,d₁,d₂, a k-L(d₁,d₂)-labeling of a graph G is a function f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|?d_i whenever the distance between u and v is i in G, for i=1,2. The L(d₁,d₂)-number of G, λ_d1,d2(G), is the smallest k such that there exists a k-L(d₁,d₂)-labeling of G. This class of labelings is motivated by the code (or frequency) assignment problem in computer network. This article surveys the results on this labeling problem.     

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.     

A characterization for a graphic sequence to be potentially C r -graphic

Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.     

Generalization of matching extensions in graphs (III)

Proposing them as a general framework, Liu and Yu (2001) [6] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d+2?|V(G)| and |V(G)|−n−d is even. If on deleting any n vertices from G the remaining subgraph H of G contains a k-matching and each k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. In this paper, we obtain more properties of (n,k,d)-graphs, in particular the recursive relations of (n,k,d)-graphs for distinct parameters n,k and d. Moreover, we provide a characterization for maximal non-(n,k,d)-graphs.     

Primitive <Emphasis Type="Italic">k</Emphasis>-free permutation groups

For a finite permutation group G acting on a set Ω, we say that G is k-free if the set-wise stabilizer of every k-subset of Ω is trivial. The purpose of this article is to describe, for all k, the primitive k-free permutation groups. Received: 20 February 2006     

Algorithms for graphs with small octopus

A d-octopus of a graph G=(V,E) is a subgraph T=(W,F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common. First, we study the complexity of finding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are efficient approximation algorithms with worst case performance ratio c·d for some small constant c>0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore, the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k=2) and 2d (for k⩾3). Finally, we show that there are O(n^7d+2) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus.     

Generalization of matching extensions in graphs (II)

Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311-320.] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d?|V(G)|-2 and |V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. Liu and Yu's Papee's paper, the recursive relations for distinct parameters n,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)-graphs in the general case d?0.     

Near automorphisms of cycles

Let f be a permutation of V(G). Define δ_f(x,y)=|d_G(x,y)-d_G(f(x),f(y))| and δ_f(G)=∑δ_f(x,y) over all the unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among all the permutations f of V(G). The permutation f with δ_f(G)=π(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles C_n and we prove that π(C_n)=4⌊n/2⌋-4, moreover, we obtain the set of near automorphisms of C_n.     

Claw-free graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the generalized prism πG is obtained by joining two copies of G by the matching {uπ(u):u∈V(G)}. Denote the domination number of G by γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. The edgeless graphs are the only known universal fixers, and are conjectured to be the only universal fixers. We prove that claw-free graphs are not universal fixers.     

The relaxed game chromatic index of k-degenerate graphs

The (r,d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r,d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with Δ(G)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ+k-1 and d?2k²+4k.     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

Stratonovich-Weyl correspondence for compact semisimple Lie groups

Let G be a compact Lie group, M a G-homogeneous space and π a unitary representation of G realized on a Hilbert space of functions on M. We give a general presentation of the Stratonovich-Weyl correspondence associated with π. In the case when G is a compact semisimple Lie group and π _λ an irreducible representation of G with highest weight λ, we study the Stratonovich-Weyl symbol of the derived operator d π _λ (X) for X in the Lie algebra of G and its behavior as λ goes to infinity.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

Edge-switching homomorphisms of edge-coloured graphs

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.