The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G=(V,A), the subdigraph of G induced by a subset X of V is denoted by G[X]. With each digraph G=(V,A) is associated its dual G^?=(V,A^?) defined as follows: for any x,y∈V, (x,y)∈A^? if (y,x)∈A. Two digraphs G and H are hemimorphic if G is isomorphic to H or to H^?. Given k>0, the digraphs G=(V,A) and H=(V,B) are k-hemimorphic if for every X⊆V, with |X|≤k, G[X] and H[X] are hemimorphic. A class C of digraphs is k-recognizable if every digraph k-hemimorphic to a digraph of C belongs to C. In another vein, given a digraph G=(V,A), a subset X of V is an interval of G provided that for a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For example, 0?, {x}, where x∈V, and V are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable.     

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.     

Quasi-kernels and quasi-sinks in infinite graphs

Given a directed graph G=(V,E) an independent set A⊂V is called quasi-kernel (quasi-sink) iff for each point v there is a path of length at most 2 from some point of A to v (from v to some point of A). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph G=(V,E) there is a a partition (V₀,V₁) of the vertex set such that the induced subgraph G[V₀] has a quasi-kernel and the induced subgraph G[V₁] has a quasi-sink.     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

An algorithm for the number of path homomorphisms

A homomorphism of a graph G₁=(V₁,E₁) to a graph G₂=(V₂,E₂) is a mapping from the vertex set V₁ of G₁ to the vertex set V₂ of G₂ which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path.     

Indecomposability graph and critical vertices of an indecomposable graph

Given a directed graph G=(V,A), the induced subgraph of G by a subset X of V is denoted by G[X]. A subset X of V is an interval of G provided that for a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For instance, 0?, V and {x}, x∈V, are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial, otherwise it is decomposable. Given an indecomposable directed graph G=(V,A), a vertex x of G is critical if G[V?{x}] is decomposable. An indecomposable directed graph is critical when all its vertices are critical. With each indecomposable directed graph G=(V,A) is associated its indecomposability directed graph defined on V by: given x≠y∈V, (x,y) is an arc of if G[V?{x,y}] is indecomposable. All the results follow from the study of the connected components of the indecomposability directed graph. First, we prove: if G is an indecomposable directed graph, which admits at least two non critical vertices, then there is x∈V such that G[V?{x}] is indecomposable and non critical. Second, we characterize the indecomposable directed graphs G which have a unique non critical vertex x and such that G[V?{x}] is critical. Third, we propose a new approach to characterize the critical directed graphs.     

On the sphericity testing of single source digraphs

A digraph D=(V,A) is called spherical, if it has an upward embedding on the round sphere which is an embedding of D on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, say to the north pole. It is easy to see that [S.M. Hashemi, Digraph embedding, Discrete Math. 233 (2001) 321-328] for upward embedding, plane and sphere are not equivalent, which is in contrast with the fact that they are equivalent for undirected graphs. On the other hand, it has been proved that sphericity testing for digraphs is an NP-complete problem [S.M. Hashemi, A. Kisielewicz, I. Rival, The complexity of upward drawings on spheres, Order 14 (1998) 327-363]. In this work we study sphericity testing of the single source digraphs. In particular, we shall present a polynomial time algorithm for sphericity testing of three connected single source digraphs.     

Surjections on Grassmannians preserving pairs of elements with bounded distance

Let m and k be two fixed positive integers such that m>k?2. Let V be a left vector space over a division ring with dimension at least m+k+1. Let G_m(V) be the Grassmannian consisting of all m-dimensional subspaces of V. We characterize surjective mappings T from G_m(V) onto itself such that for any A,B in G_m(V), the distance between A and B is not greater than k if and only if the distance between T(A) and T(B) is not greater than k.     

Good distance graphs and the geometry of matrices

Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V^′,∼^′) be two good distance graphs, and φ:V→V^′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩Z_D|?3 and D is not a field of characteristic 2 with D=F, where and Z_D is the center of D. Let H_n(n?2) be the set of n×n Hermitian matrices over D. It is proved that (H_n,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈H_n.     

A polynomial-time algorithm for the paired-domination problem on permutation graphs

A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.     

The maximum corank of graphs with a 2-separation

For a graph G=(V,E) with vertex-set V={1,2,…,n}, which is allowed to have parallel edges, and for a field F, let S(G;F) be the set of all F-valued symmetric n×n matrices A which represent G. The maximum corank of a graph G is the maximum possible corank over all A∈S(G;F). If (G₁,G₂) is a (?2)-separation, we give a formula which relates the maximum corank of G to the maximum corank of some small variations of G₁ and G₂.     

On the zeros of a minimal realization

In an earlier work, the authors have introduced a coordinate-free, module-theoretic definition of zeros for the transfer function G(s) of a linear multivariable system (A,B,C). The first contribution of this paper is the construction of an explicit k[z]-module isomorphism from that zero module, Z(G), to V¹/R¹, where V¹ is the supremal (A,B)-invariant subspace contained in kerC and R¹ is the supremal (A,B)-controllable subspace contained in kerC, and where (A,B,C) constitutes a minimal realization of G(s). The isomorphism is developed from an exact commutative diagram of k-vector spaces. The second contribution is the introduction of a zero-signal generator and the establishment of a relation between this generator and the classic notion of blocked signal transmissions.     

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G=(V,E) with matching number ν(G), a d-blocker is a subset of edges B such that ν((V,E?B))≤ν(G)−d and a d-transversal T is a subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.     

Simple Realizability of Complete Abstract Topological Graphs in P

An abstract topological graph (briefly an AT-graph) is a pair A=(G,R)A=(G,\mathcal{R}) where G=(V,E) is a graph and R í ((E) || 2)\mathcal {R}\subseteq {E \choose 2} is a set of pairs of its edges. An AT-graph A is simply realizable if G can be drawn in the plane in such a way that each pair of edges from R\mathcal{R} crosses exactly once and no other pair crosses. We present a polynomial algorithm which decides whether a given complete AT-graph is simply realizable. On the other hand, we show that other similar realizability problems for (complete) AT-graphs are NP-hard.     

Computing finest mincut partitions of a graph and application to routing problems

Let G=(V,E,w) be an n-vertex graph with edge weights w>0. We propose an algorithm computing all partitions of V into mincuts of G such that the mincuts in the partitions cannot be partitioned further into mincuts. There are O(n) such finest mincut partitions. A mincut is a non-empty proper subset of V such that the total weight of edges with exactly one end in the subset is minimal. The proposed algorithm exploits the cactus representation of mincuts and has the same time complexity as cactus construction. An application to the exact solution of the general routing problem is described.     

On Galois Algebras Satisfying the Fundamental Theorem

Let B be a Galois algebra over a commutative ring R with Galois group G such that B ^H is a separable subalgebra of B for each subgroup H of G. Then it is shown that B satisfies the fundamental theorem if and only if B is one of the following three types: (1) B is an indecomposable commutative Galois algebra, (2) B = Re ⊕ R(1 ? e) where e and 1 ? e are minimal central idempotents in B, and (3) B is an indecomposable Galois algebra such that for each separable subalgebra A, V _B (A) = ?∑ _g∈G(A) J _g , and the centers of A and B ^G(A) are the same where V _B (A) is the commutator subring of A in B, J _g  = {b ∈ B | bx = g(x)b for each x ∈ B} for a g ∈ G, and G(A) = {g ∈ G | g(a) = a for all a ∈ A}.     

Interactions

Given a C^∗-algebra B, a closed ^*-subalgebra A⊆B, and a partial isometry S in B which interacts with A in the sense that S^∗aS=H(a)S^∗S and SaS^∗=V(a)SS^∗, where V and H are positive linear operators on A, we derive a few properties which V and H are forced to satisfy. Removing B and S from the picture we define an interaction as being a pair of maps (V,H) satisfying the derived properties. Starting with an abstract interaction (V,H) over a C^∗-algebra A we construct a C^∗-algebra B containing A and a partial isometry S whose interaction with A follows the above rules. We then discuss the possibility of constructing a covariance algebra from an interaction. This turns out to require a generalization of the notion of correspondences (also known as Pimsner bimodules) which we call a generalized correspondence. Such an object should be seen as an usual correspondence, except that the inner-products need not lie in the coefficient algebra. The covariance algebra is then defined using a natural generalization of Pimsner's construction of the celebrated Cuntz-Pimsner algebras.     

Ideals with bounded approximate identities in Fourier algebras

We make use of the operator space structure of the Fourier algebra A(G) of an amenable locally compact group to prove that if H is any closed subgroup of G, then the ideal I(H) consisting of all functions in A(G) vanishing on H has a bounded approximate identity. This result allows us to completely characterize the ideals of A(G) with bounded approximate identities. We also show that for several classes of locally compact groups, including all nilpotent groups, I(H) has an approximate identity with norm bounded by 2, the best possible norm bound.     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

A better approximation algorithm for the budget prize collecting tree problem

Given an undirected graph G=(V,E), an edge cost c(e)?0 for each edge e∈E, a vertex prize p(v)?0 for each vertex v∈V, and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to find a subtree T′=(V′,E′) that maximizes , subject to . We present a (4+ε)-approximation algorithm.