The traveling salesman problem in graphs with some excluded minors

Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper we characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs.     

基于自由度分析的装配求解实现

装配求解是装配设计的重要内容，目的是利用装配约束信息求解有关实体的位置和方向．本文针对传统装配求解方法的不足，提出了一种基于自由度分析的装配求解方法，它充分利用了装配约束的几何信息，增量式添加约束，同时不断修正所记录的相应装配实体的运动自由度，并通过自由度求出装配实体的转换矩阵．本文具体描述了方法实现的有关结构和装配的推理方法     

On the Total Domination Number of Cartesian Products of Graphs

The most famous open problem involving domination in graphs is Vizings conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. In this paper, we investigate a similar problem for total domination. In particular, we prove that the product of the total domination numbers of any nontrivial tree and any graph without isolated vertices is at most twice the total domination number of their Cartesian product, and we characterize the extremal graphs.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal     

Testing set proportionality and the Ádám isomorphism of circulant graphs

Given two k element subsets , we give a quasi-linear algorithm to either find such that S=λT or prove that no such λ exists.This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.     

The strength of weak proximity

This paper studies weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment (p,q) is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing.Most previously studied proximity regions are associated with a parameter β, 0β∞. For fixed β, weak β-drawability is at least as expressive as strong β-drawability, as a strong β-drawing is also a weak one. We give examples of graph families and β values where the two notions coincide, and a situation in which it is NP-hard to determine weak β-drawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of β-drawability: we show that every graph has, for all sufficiently small β, a weak β-proximity drawing that is computable in linear time, and we show that every tree has, for every β less than 2, a weak β-drawing that is computable in linear time.     

A forest building process on simple graphs

Consider the following process on a simple graph without isolated vertices: order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in some preceding edge. The resulting set of edges forms a spanning forest of the graph.The probability of obtaining $k$ components in this process for complete bipartite graphs is determined as well as a formula for the expected number of components in any graph. A generic recurrence and some additional basic properties are discussed.     

A note on the DP-chromatic number of complete bipartite graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvo?ák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{?}\left(G\right)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}\left(G\right)$. On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{?}\left(K_{k,t}\right)=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}\left(K_{k,t}\right)=k+1$ if $t\ge 1+(k^k∕k!)(log(k!)+1)$, and we show that ${\chi }_{DP}\left(K_{k,t}\right)<k+1$ if $t<k^k∕k!$.     

Graph algorithms for DNA sequencing – origins,current models and the future

With the ubiquitous presence of next-generation sequencing in modern biological, genetic, pharmaceutical and medical research, not everyone pays attention to the underlying computational methods. Even fewer researchers know what were the origins of the current models for DNA assembly. We present original graph models used in DNA sequencing by hybridization, discuss their properties and connections between them. We also explain how these graph models evolved to adapt to the characteristics of next-generation sequencing. Moreover, we present a practical comparison of state-of-the-art DNA de novo assembly tools representing these transformed models, i.e. overlap and decomposition-based graphs. Even though the competition is tough, some assemblers perform better and certainly large differences may be observed in hardware resources utilization. Finally, we outline the most important trends in the sequencing field, and try to predict their impact on the computational models in the future.     

On single-matrix graph-directed iterated function systems

We study graph-directed function systems where each contraction in the system has the form fe(x)=A−1(x+de), where A is an expanding matrix. We show that a certain discreteness implies the open set condition, and the latter implies the strong open set condition. Hausdorff measures and dimensions (w.r.t. a weak norm) of the invariant sets are investigated. The stationary Markov measures of the system are proved to be translation invariant.     

Trees with minimal index and diameter at most four

In this paper we consider the trees with fixed order n and diameter d≤4. Among these trees we identify those trees whose index is minimal.