Wings and perfect graphs

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G — C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. V. Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.     

Primes in the semigroup of non-negative matrices

A matrix A in the semigroup N_n of non-negative n×nmatrices is prime if A is not monomial and A=BC,BCεN_n implies that either B or C is monomial. One necessary and another sufficient condition are given for a matrix in N_n to be prime. It is proved that every prime in N_n is completely decomposable.     

Decompositions of positive self-dual boolean functions

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f_c such that f_c(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a non-dominated (ND) coterie if and only if f_c is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f₁,f₂,…, f_k. In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f₁, and f₂, and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

A hybrid graph-genetic method for domain decomposition

A new method is developed for finite element (FE) domain decomposition. This method employs a hybrid graph-genetic algorithm for graph partitioning and correspondingly bisects finite element (FE) meshes.

A weighted incidence graph is first constructed for the FE mesh, denoted by G₀. A coarsening process is then performed using heavy-edge matching. A sequence of such operations is employed in “n” steps, which leads to the formation of G_n with a size suitable for genetic algorithm applications.

Hereafter, G_n is bisected using conventional genetic algorithm. The shortest route tree algorithm is used for the formation of the initial population in genetic algorithm. Then an uncoarsening process is performed and the results are transferred to the graph G_n−1. The initial population for genetic algorithm on G_n−1is constructed from the results of G_n. This process is repeated until G₀ is obtained in the uncoarsening operation. Employing the properties of G₁, the graph G₀ is bisected by the genetic algorithm.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

On weakly s-permutably embedded subgroups of finite groups (II)

Suppose that G is a finite group and H is a subgroup of G. H is said to be s-permutably embedded in G if for each prime p dividing |H|, a Sylow p-subgroup of H is also a Sylow p-subgroup of some s-permutable subgroup of G; H is called weakly s-permutably embedded in G if there are a subnormal subgroup T of G and an s-permutably embedded subgroup H_se of G contained in H such that G = HT and H∩T≤H_se. In this paper, we continue the work of [Comm. Algebra, 2009, 37: 1086-1097] to study the influence of the weakly s-permutably embedded subgroups on the structure of finite groups, and we extend some recent results.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes

Let P be a simplicial d-polytope with n facets ((d − 1)-dimensional faces) in R^d. A shelling of P is an ordering of the facets of P such that the intersection of each facet F with the union of all facets that precede it the ordering is a nonempty union of (d − 2)-faces of F. The following open question was raised by Tverberg and is recorded in [4]. Suppose for some k < n, there is an ordering of k of the facets of P so that the intersection of each of these facets with the union of all of the facets that precede it in the ordering is a nonempty union of (d − 2)-faces. Can this initial “segment” be extended to a shelling of all the facets? This question is open even in the case that P is the dual of the d-dimensional hypercube. The question in this case has resurfaced several times since G. Danaraj and V. Klee (1978) in a variety of forms. It is related to the hierarchies of completely unimodal pseudo-Boolean functions studied in P.L. Hammer et al. (1988), the author (1988) and D. Wiedemann (1986). (A pseudo-Boolean function is a function mapping the vertices of the d-dimensional hypercube into the reals). In this paper, the hierarchies are compared and combined. This hierarchy is then extended to general simple polytopes, and the relationship to the above open question is explained.     

ℓ-homology of right-angled Coxeter groups based on barycentric subdivisions

Associated to any finite flag complex L there is a right-angled Coxeter group W_L and a contractible cubical complex Σ_L on which W_L acts properly and cocompactly, and such that the link of each vertex is L. It follows that if L is a triangulation of , then Σ_L is a contractible n-manifold. We establish vanishing (in a certain range) of the reduced ℓ²-homology of Σ_L in the case where L is the barycentric subdivision of a cellulation of a manifold. In particular, we prove the Singer Conjecture (on the vanishing of the reduced ℓ²-homology except in the middle dimension) in the case of Σ_L where L is the barycentric subdivision of a cellulation of , n=6,8.     

On-line construction of the upper envelope of triangles and surface patches in three dimensions

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions. This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log nΣ_r=1ⁿτ(r)/r²) and depends on the expected size τ(r) of an intermediate result for r triangles. Since τ(r) can be Θ(r²(r)) in the worst case, this cost is bounded in the worst case by O(n(n) log n). (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice. It extends to surfaces and surface patches of fixed maximum algebraic degree.     

Input control in nonnegative matrix equations

In this paper we consider the nonnegative matrix system c_iA+u_iB=c_i+1 where the nonnegative matrix A is allowed to vary, within bounds. The cone control problem is to find a nonnegative matrix B such that if C_i is a nonnegative vector in a specified cone, then there is a nonnegative vector u_i such that c_i+1 is in that cone. We extend this problem to input control by finding a B such that the cone, generated by the rows of B, is as small as possible. Thus, the percent distribution of ∣u_iB∣ through the states of the sustem by u_iB is either constant or varies little.     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

Unique satisfiability of Horn sets can be solved in nearly linear time

If a Horn set I has a single satisfying truth assignment or model then that model is said to be unique for I. The question of determining whether a unique model exists for a given Horn set I is shown to be solved in O((L)*L) time, where L is the sum of the lengths of the clauses in I and is the inverse Ackermann function. It is also shown that if LA*log (A) where A is the number of distinct proposition letters then unique satisfiability can be determined in O(L) time.     

Extending matchings in planar graphs V

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges e₁ and e₂ are such that the removal of their endvertices leaves at least one odd component C_o. The subgraph G[V(C_o) V(e₁) V(e₂)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false.

We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed.     

On index of total boundedness of (strictly) o-bounded groups

Let G be a metrizable topological group. Denote by itb(G) the smallest cardinality of a cover of G by totally bounded subsets of G. A group G is defined to be σ-bounded if itb(G)₀. The group G is called o-bounded if for every sequence (U_n)_nω of neighborhoods of the identity in G there exists a sequence (F_n)_nω of finite subsets in G such that G=_nωF_n·U_n; G is called strictly o-bounded (respectively OF-determined) if the second player (respectively one of the players) has a winning strategy in the following game OF: two players, I and II, choose at every step n an open neighborhood U_n of the identity in G and a finite subset F_n of G, respectively. The player II wins if G=_nωF_n·U_n.

For a second countable group G the following results are proven. . If G is strictly o-bounded, then itb(G)₁ and G is σ-bounded or meager. If the space G is analytic, then the group is OF-determined and satisfies . G is σ-bounded if it is strictly o-bounded and one of the following conditions holds: (i) G is analytic; (ii) ; (iii) (MA+¬CH) holds; (iv) analytic games are determined; (v) there exists a measurable cardinal. Also we show that under (MA) every non-locally compact Polish Abelian divisible group contains a Baire o-bounded OF-undetermined subgroup.     

Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

The generalized column incidence graph and a matroid base-listing algorithm

The generalized column incidence graph of a matroid base is defined, and it is shown that all elements on a minimal path in this graph lie in a common circuit. Also, an algorithm is provided which lists all bases of a matroid and calculates the Whitney and Tutte polynomials. The complexity of this algorithm is shown to be O(mN(n- m)(c(M) + m)), where Mis a matroid of rank mon a set of cardinality nNis the number of bases of M, and c(M) is the complexity of checking independence in M.