Strategies of loop recombination in ciliates

The concept of breakpoint graph, known from the theory of sorting by reversal, has been successfully applied in the theory of gene assembly in ciliates. We further investigate its usage for gene assembly, and show that the graph allows for an efficient characterization of the possible orders of loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) for a given gene during gene assembly. The characterization is based on spanning trees within a graph built upon the connected components in the breakpoint graph. We work in the abstract and more general setting of so-called legal strings.     

An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.This work was supported by U.S. Army Research Office grant DAAG29-82-K-0107.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

Graph family operations

In previous papers, Catlin introduced four functions, denoted , , , and , between sets of finite graphs. These functions proved to be very useful in establishing properties of several classes of graphs, including supereulerian graphs and graphs with nowhere zero k-flows for a fixed integer k3. Unfortunately, a subtle error caused several theorems previously published in Catlin (Discrete Math. 160 (1996) 67–80) to be incorrect. In this paper we correct those errors and further explore the relations between these functions, showing that there is a sort of duality between them and that they act as inverses of one another on certain sets of graphs.     

A new characterization of HH-free graphs

We show that a graph G has no houses and no holes if and only if for every connected induced subgraph H of G and every vertex in H, either the vertex is adjacent to all the other vertices in H, or it forms a 2-pair of H with some other vertex in H. As a consequence, there is a simple linear time algorithm to find a 2-pair in HH-free graphs. We also note that the class of Meyniel graphs admits an analogous characterization.     

Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

An ant-based algorithm for coloring graphs

This paper presents an ant-based algorithm for the graph coloring problem. An important difference that distinguishes this algorithm from previous ant algorithms is the manner in which ants are used in the algorithm. Unlike previous ant algorithms where each ant colors the entire graph, each ant in this algorithm colors just a portion of the graph using only local information. These individual coloring actions by the ants form a coloring of the graph. Even with the lack of pheromone laying capacity by the ants, the algorithm performed well on a set of 119 benchmark graphs. Furthermore, the algorithm produced very consistent results, having very small standard deviations over 50 runs of each graph tested.     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

图K(r,2)的邻强边色数

本文给出了每部有2个点的完全r-部图(r≥2)的邻强边色数.