A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

A sufficient condition for a planar graph to be 3-choosable

It is shown that a planar graph without cycles of length 4, 6, 8, or 9 is 3-choosable.     

A comprehensive analysis of degree based condition for Hamiltonian cycles

Since finding whether a graph has a Hamiltonian path or Hamiltonian cycle are both NP-complete problems, researchers have been formulating sufficient conditions that ensure the path or cycle. Rahman and Kaykobad (2005) [2] presented a sufficient condition for determining the existence of Hamiltonian path. Three recent works-Lenin Mehedy, Md. Kamrul Hasan, Mohammad Kaykobad (2007) [3], Rao Li (2006) [4], Shengjia Li, Ruijuan Li, Jinfeng Feng (2007) [5]-further used the same or similar condition to ensure Hamiltonian cycle with some exceptions. The three works, along with their unique findings, have some common results. This paper unifies the results and brings them under Rahman and Kaykobad’s condition.     

On Hamiltonian cycles and Hamiltonian paths

A Hamiltonian cycle is a spanning cycle in a graph, i.e., a cycle through every vertex, and a Hamiltonian path is a spanning path. In this paper we present two theorems stating sufficient conditions for a graph to possess Hamiltonian cycles and Hamiltonian paths. The significance of the theorems is discussed, and it is shown that the famous Ore's theorem directly follows from our result.     

The complexity for partitioning graphs by monochromatic trees,cycles and paths

Let G be an edge-coloured graph. We show in this paper that it is NP-hard to find the minimum number of vertex disjoint monochromatic trees which cover the vertices of the graph G. We also show that there is no constant factor approximation algorithm for the problem unless P?=?NP. The same results hold for the problem of finding the minimum number of vertex disjoint monochromatic cycles (paths, respectively) which cover the vertices of the graph.     

A lower bound for the hitting set size for combinatorial rectangles and an application

We prove a lower bound of where for the hitting set size for combinatorial rectangles of volume at least ε in [m]^d space, for and d>2.     

A note on the Markoff condition and central words

We define Markoff words as certain factors appearing in bi-infinite words satisfying the Markoff condition. We prove that these words coincide with central words, yielding a new characterization of Christoffel words.     

A new modeling and solution approach for the set-partitioning problem

The set-partitioning problem (SPP) is widely known for both its application potential and its computational challenge. This NP-hard problem is known to pose considerable difficulty for classical solution methods such as those based on LP technologies. In recent years, the unconstrained binary quadratic program has proven to perform well as a unified modeling and solution framework for a variety of IP problems. In this paper we illustrate how this unified framework can be applied to SPP. Computational experience is presented, illustrating the attractiveness of the approach.     

A spectral lower bound for the treewidth of a graph and its consequences

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least ⌊3·2^d/(2(d+4))⌋−1. The currently known upper bound is . We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree Δ

(1)

contains an induced cycle (chordless cycle) of length at least 1+log_Δ(μn/8) (provided G is not acyclic),

(2)

has a clique minor K_h for some ,

where μ is the second smallest eigenvalue of the Laplacian matrix of G.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

A necessary and sufficient condition for the perspective observability problem

In this paper we derive a necessary and sufficient condition for observing the initial condition of a new class of system known as the perspective system. Such a system has already been applied in the field of computer vision especially in the area of motion estimation problems. Our result generalizes an earlier result by Popov-Belevitch-Hautus on the problem of observing a linear dynamical system.     

A necessary and sufficient condition for input-to-state stability of quantised feedback systems

For zooming-out/in method used in the design of quantised feedback systems, the property of the duration of zoom-out mode (this duration is defined as capture time) is essential to input-to-state stability (ISS) of systems. This paper shows that a necessary and sufficient condition of achieving ISS with respect to external disturbances for quantised feedback systems is that capture time under the proposed coding scheme is uniformly bounded. It further shows that the coding scheme under which capture time is only bounded and not uniformly bounded cannot guarantee ISS of systems. A coding scheme is designed for uniformly bounded capture time and therefore achieves ISS of systems.     

Observers and observability for uncertain nonlinear systems: A necessary and sufficient condition

In this paper, observers and observability for uncertain nonlinear systems are systematically discussed. It is shown that for the convergence of a large class of observers, featured with the augment state to estimate the uncertainty, it requires not only the observability condition for the augment matrix pair but, more importantly, requires a structural condition first proposed in this paper. Furthermore, it is demonstrated that the combination of this structural condition and the observability of the augment matrix pair is a necessary and sufficient condition for the convergence of the observers and the observability of the original uncertain nonlinear systems. This implies that both the structural condition and the observability condition of the augment matrix pair reveal essential feature of the observing problems for uncertain nonlinear systems. In addition, for unobservable uncertain nonlinear systems, which do not satisfy this necessary and sufficient condition, the biased estimation error is explicitly presented, which can be used to evaluate the estimation performance of this class of observers. The numerical simulations for three typical examples are carried out to validate our theoretical analysis.     

A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

Unknown input observer for state affine systems: A necessary and sufficient condition

The problem of designing an unknown input observer for linear systems and its application to fault detection is widely studied in the literature. For nonlinear systems, only subclasses of nonlinear systems and sufficient conditions have been stated. In this paper an unknown input observer design for state affine systems is considered. Based on the geometric approach, a necessary and sufficient condition is given for the existence of an unknown input observer.     

基于干扰度的长大货物联运路径规划方法

针对长大货物联运路径规划问题,构造干扰度函数以量化长大货物联运对正常运输的影响程度,并以长大货物联运总成本最少为第一优化目标,以对正常运输的干扰程度最低为第二优化目标,构建基于干扰度的长大货物联运路径多目标规划模型;基于研究问题的特征,结合所提类三棱柱网络构造算法,设计基于K-最短路的联运路径规划算法。算例结果表明,所提方法能制定多组长大货物联运路径规划方案,降低长大货物联运的干扰影响,能确定影响方案优劣的关键路段与节点。提出的方法可为长大货物联运组织提供决策支持。     

A hybrid mechanism for heterogeneous e-procurement involving a combinatorial auction and bargaining

We discuss the design of a hybrid mechanism for e-procurement, which implements a multi-attribute combinatorial auction, followed by a bargaining process to achieve desirable procurement transaction outcomes. For the auction phase of the mechanism, we discuss incentive-compatible bidding strategies for suppliers, and how the buyer should determine the winning suppliers. In the follow-on bargaining phase, the buyer can implement a pricing strategy that views the winning suppliers as though they are in different groups. We develop a model and derive decision conditions for the buyer to formulate procurement strategy in this context. Our most important finding is that, compared with the classical Vickrey–Clarke–Groves mechanism, the proposed mechanism improves the transactional social surplus, by including the possibility of post-auction bargaining. We also consider the likelihood that such a hybrid mechanism will be able to provide sustainable business value so long as there is reasonable symmetry in bargaining power between the buyer and the supplier. We offer some thoughts on how to extend this research with approaches from behavioral economics and experimental methods.     

A necessary and sufficient stabilization condition for discrete time-varying stochastic systems with multiplicative noise

This paper investigates a fundamental problem of stabilization for time-varying multiplicative noise stochastic systems. A necessary and sufficient stabilization condition is presented based on the receding horizon approach. The explicit time-varying controller is designed if the condition is satisfied. The presented results are new to the best of our knowledge.