206858542
Degree Sums and Path-Factors in Graphs
Abstract. Let G be a connected graph of order n and suppose that n=∑i=1kni, where ni≥2 are integers. In this paper we give some sufficient conditions in terms of degree sums to ensure that G contains a spanning subgraph consisting of vertex disjoint paths of orders n1,n2,…,nk.
15445426
An Ore-type Condition for Cyclability
A graph G is said to be cyclable if for each orientation D of G, there exists a set S(D) ?V(G) such that reversing all the arcs with one end in S results in a Hamiltonian digraph. Let G be a simple graph of even ordern? 8. In this paper, we show that if the degree sum of any two nonadjacent vertices is not less thann+ 1, then G is cyclable and the lower bound is sharp.
4357183
A New Proof of Wojcicka's Conjecture
A graph G is 3-domination-critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Wojcicka conjectured that every 3-domination-critical graph with δ ≥ 2 has a hamiltonian cycle (J. Graph Theory 14 (1990) 205-215). The conjecture had been proved and its proof consists of two parts: the case α ≤ δ + 1 (J. Graph Theory 25 (1997) 173-184) and the case α = δ + 2 (Discrete Appl. Math. 92 (1999) 57-70). In this paper, we give a new and simple proof of the conjecture by using Hanson's (J. Combin. Math. Combin. Comput. 13 (1993) 121-128) and Bondy-Chvatal's (Discrete Math. 15(1976) 111-135) closure operations.
6176366
The Ramsey numbers of stars versus wheels
For two given graphs G 1 and G 2 , the Ramsey number R(G 1 , G 2 ) is the smallest positive integer n such that for any graph G of order n, either G contains G 1 or the complement of G contains G 2 . Let S n denote a star of order n and W m a wheel of order m + 1. This paper shows that R(S n , W 6 )=2n + 1 for n ≥ 3 and R(S n , W m )=3n - 2 for m odd and n ≥ m - 1 ≥ 2.
37750685
A Genetic Algorithm with Chromosome-Repairing Technique for Polygonal Approximation of Digital Curves
A genetic algorithm with chromosome-repairing scheme (CRS) is proposed in this paper to solve the polygonal approximation problem. Different from the existing approaches based on genetic algorithms, the proposed algorithm adopts variable-length chromosome encoding for reducing the memory storage and computational time, and develops a special crossover named gene-removing crossover for removing the redundant genes. It is known that Genetic operators may yield infeasible solutions, and it is generally difficult to cope with them. Instead of using the penalty function approach, we propose a chromosome-repairing scheme to iteratively add the valuable candidate gene to the chromosome to deal with the infeasible solution and an evaluating scheme for the candidate genes. The experimental results show that the proposed CRS outperforms the existing approaches based on genetic-algorithms, ant-colony-optimization and tabu-search.
16940810
Vertex and Tree Arboricities of Graphs
This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.
43634604
Hamiltonian Kneser Graphs
The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n.
14272034
Optimal Anytime Constrained Simulated Annealing for Constrained Global Optimization
In this paper we propose an optimal anytime version of constrained simulated annealing (CSA) for solving constrained nonlinear programming problems (NLPs). One of the goals of the algorithm is to generate feasible solutions of certain prescribed quality using an average time of the same order of magnitude as that spent by the original CSA with an optimal cooling schedule in generating a solution of similar quality. Here, an optimal cooling schedule is one that leads to the shortest average total number of probes when the original CSA with the optimal schedule is run multiple times until it finds a solution. Our second goal is to design an anytime version of CSA that generates gradually improving feasible solutions as more time is spent, eventually finding a constrained global minimum (CGM). In our study, we have observed a monotonically non-decreasing function relating the success probability of obtaining a solution and the average completion time of CSA, and an exponential function relating the objective target that CSA is looking for and the average completion time. Based on these observations, we have designed CSAAT-ID the anytime CSA with iterative deepening that schedules multiple runs of CSA using a set of increasing cooling schedules and a set of improving objective targets. We then prove the optimality of our schedules and demonstrate experimentally the results on four continuous constrained NLPs. CSAAT-ID can be generalized to solving discrete, continuous, and mixed-integer NLPs, since CSA is applicable to solve problems in these three classes. Our approach can also be generalized to other stochastic search algorithms, such as genetic algorithms, and be used to determine the optimal time for each run of such algorithms.
13210979
Specification-based verification and validation of Web services and service-oriented operating systems
Service-oriented architecture (SOA) and Web services (WS) have received significant attention recently. Even though WS are based on open standards and support software interoperability, but the trustworthy issues of WS has actually limited the growth of WS applications as organizations do not trust those WS developed by other vendors and at the same time they do not have access to the source code. This paper addressed this issue by proposing several solutions including specification-based verification and validation, collaborative testing, and group testing. The key concept is that it is possible to provide a comprehensive evaluation of WS even if their source code is not available.