The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

图的能量与哈密尔顿性

设G是一个无向简单图,A（G）为G的邻接矩阵．用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件：其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件．这些结果改进了一些已知的结果．     

A note on the smallest connected non-traceable cubic bipartite planar graph

A graph is traceable if it contains a Hamiltonian path. We present a connected non-traceable cubic bipartite planar graph with 52 vertices and prove that there are no smaller such graphs.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

An overview of Stackelberg pricing in networks

The Stackelberg pricing problem has two levels of decision making: tariff setting by an operator, and then selection of the cheapest alternative by customers. In the network version, an operator determines tariffs on a subset of the arcs that he owns. Customers, who wish to connect two vertices with a path of a certain capacity, select the cheapest path. The revenue for the operator is determined by the tariff and the amount of usage of his arcs. The most natural model for the problem is a (bilinear) bilevel program, where the upper level problem is the pricing problem of the operator, and the lower level problem is a shortest path problem for each of the customers.     

The complexity of social groups and social systems described by graph structures

This paper presents methodology which permits the complete ranking of nondirected graphs (NDG's) on an attribute labelled ‘complexity.’ The technique applies to both small and large systems as might arise in studies of group or organization behavior. The methodology extends to cover the complexity of directed graphs (DG's) and permits the detailed specification of individual and group behavior.For the NDG an abstract automaton representing the participants' interaction or communications function is sited at each node. Each automaton is constructed so its internal complexity is sufficient to realize the minimal social action (e.g. transmission of a rumor and the path followed by the rumor) within the framework of the NDG. It is shown that the complexity of each node automaton depends upon the order of the graph, the degree of the node and the longest path parameter of the graph. The combined complexity of node automata constitutes the complexity of the NDG. The complexity of a DG is specified as a composition of complexities computed for the associated NDG and logical devices which produce the observed behavior. Illustrative examples pertaining to the committee-subcommittee problem and to organizational structures are presented.     

关于3-正则图的路分解

本文讨论了3-正则图的路分解问题,证明了任意的3-正则图都有{P3,P4}分 解,其中Rk指包含k个顶点的路.     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

Maslov P-Index Theory for a Symplectic Path with Applications

The Maslov P-index theory for a symplectic path is defined. Various properties of this index theory such as homotopy invariant, symplectic additivity and the relations with other Morse indices are studied. As an application, the non-periodic problem for some asymptotically linear Hamiltonian systems is considered.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

Independent sets and non-augmentable paths in generalizations of tournaments

We study different classes of digraphs, which are generalizations of tournaments, to have the property of possessing a maximal independent set intersecting every non-augmentable path (in particular, every longest path). The classes are the arc-local tournament, quasi-transitive, locally in-semicomplete (out-semicomplete), and semicomplete k-partite digraphs. We present results on strongly internally and finally non-augmentable paths as well as a result that relates the degree of vertices and the length of longest paths. A short survey is included in the introduction.     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

Maslov P-Index Theory for a Symplectic Path with Applications

Abstract The Maslov P-index theory for a symplectic path is defined. Various properties of this index theory such as homotopy invariant, symplectic additivity and the relations with other Morse indices are studied. As an application, the non-periodic problem for some asymptotically linear Hamiltonian systems is considered. *Project supported by the National Natural Science Foundation of China (No.10531050) and FANEDD.     

On relative length of longest paths and cycles

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. In this paper, we prove that if G is a 3 ‐connected graph of order n such that the minimum degree sum of four independent vertices is at least n+ 6, then p(G)?c(G)?2. By considering our result and the results in [J Graph Theory 20 (1995), 213–225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 279–291, 2009     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001