A digraph D is k-ordered if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a cycle C such that C encounters the vertices of S in the specified order.In particular,we say that D is k-ordered h...A digraph D is k-ordered if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a cycle C such that C encounters the vertices of S in the specified order.In particular,we say that D is k-ordered hamiltonian if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a hamiltonian cycle C such that the vertices of S are encountered on C in the specified order.In this paper,sufficient conditions for digraphs to be ordered and ordered hamiltonian have been given.展开更多
The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It ...The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It has been noted that the 2-sum of two supereulerian (or even hamiltonian) digraphs may not be supereulerian. We obtain several sufficient conditions on and for to be supereulerian. In particular, we show that if and are symmetrically connected or partially symmetric, then is supereulerian.展开更多
Given a digraph D =（V, A）, the competition graph G of D, denoted by C（D）, has the same set of vertices as D and an edge between vertices x and y if and only if N;（x）∩N;（y）≠Ф. In this paper, we investigate t...Given a digraph D =（V, A）, the competition graph G of D, denoted by C（D）, has the same set of vertices as D and an edge between vertices x and y if and only if N;（x）∩N;（y）≠Ф. In this paper, we investigate the competition graphs of round digraphs and give a necessary and sufficient condition for these graphs to be hamiltonian.展开更多
在文献[2]中,B ang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是H am ilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与52n-92中的最大者,则D...在文献[2]中,B ang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是H am ilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与52n-92中的最大者,则D是H am ilton图.展开更多
G 是一个有限群,M 是 G 的一个极小生成集。用 Cay(M:G)表示生成集为 M 的 G 上的一个 Cayley 图。Z_n 表示模 n 的剩余类加群。本文借助 Rankin 的一个引理,研究有向 Cayley 图的 Hamilton 回的存在性。作为 Rankin 引理的推论,给出了 ...G 是一个有限群,M 是 G 的一个极小生成集。用 Cay(M:G)表示生成集为 M 的 G 上的一个 Cayley 图。Z_n 表示模 n 的剩余类加群。本文借助 Rankin 的一个引理,研究有向 Cayley 图的 Hamilton 回的存在性。作为 Rankin 引理的推论,给出了 Cay(M:Z_n)存在 Hamilton 回的若干充分条件。展开更多
In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite circulant digraphs are infinitely strongly connected and therefore have both one-and two-...In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite circulant digraphs are infinitely strongly connected and therefore have both one-and two-way infinite Hamiltonian paths.展开更多
In this paper, by the optimization method, we establish the integer programming mod-els of several famous problems of graph theory, such as the necessary and sufficient condi-tion of a graph (or digraph) being a Hamil...In this paper, by the optimization method, we establish the integer programming mod-els of several famous problems of graph theory, such as the necessary and sufficient condi-tion of a graph (or digraph) being a Hamiltonian graph, a Hamiltonian circuit which has aminimal total weight on a weighted graph (or digraph) and so on. Those difficult problemscan be solved by any of the integer programming algorithms.展开更多
基金Foundation item： Supported by the National Natural Science Foundation of China（61070229） Supported by the Natural Science Foundation of Shanxi Province（2008011010）
文摘A digraph D is k-ordered if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a cycle C such that C encounters the vertices of S in the specified order.In particular,we say that D is k-ordered hamiltonian if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a hamiltonian cycle C such that the vertices of S are encountered on C in the specified order.In this paper,sufficient conditions for digraphs to be ordered and ordered hamiltonian have been given.
文摘The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It has been noted that the 2-sum of two supereulerian (or even hamiltonian) digraphs may not be supereulerian. We obtain several sufficient conditions on and for to be supereulerian. In particular, we show that if and are symmetrically connected or partially symmetric, then is supereulerian.
基金Supported by NSFC(11401353)TYAL of ShanxiNatural Science Foundation of Shanxi Province(2016011005)
文摘Given a digraph D =（V, A）, the competition graph G of D, denoted by C（D）, has the same set of vertices as D and an edge between vertices x and y if and only if N;（x）∩N;（y）≠Ф. In this paper, we investigate the competition graphs of round digraphs and give a necessary and sufficient condition for these graphs to be hamiltonian.
文摘在文献[2]中,B ang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是H am ilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与52n-92中的最大者,则D是H am ilton图.
文摘G 是一个有限群,M 是 G 的一个极小生成集。用 Cay(M:G)表示生成集为 M 的 G 上的一个 Cayley 图。Z_n 表示模 n 的剩余类加群。本文借助 Rankin 的一个引理,研究有向 Cayley 图的 Hamilton 回的存在性。作为 Rankin 引理的推论,给出了 Cay(M:Z_n)存在 Hamilton 回的若干充分条件。
基金Supported by Natural Science Foundation of China (Project 10171085).
文摘In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite circulant digraphs are infinitely strongly connected and therefore have both one-and two-way infinite Hamiltonian paths.
文摘In this paper, by the optimization method, we establish the integer programming mod-els of several famous problems of graph theory, such as the necessary and sufficient condi-tion of a graph (or digraph) being a Hamiltonian graph, a Hamiltonian circuit which has aminimal total weight on a weighted graph (or digraph) and so on. Those difficult problemscan be solved by any of the integer programming algorithms.
