In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly co...In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.展开更多
Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of tw...Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.展开更多
For a simple digraph G, let β（G） be the size of the smallest subset X E（G） such that G - X has no directed cycles, and let γ（G） be the number of unordered pairs of nonadjacent vertices in G. A digraph G is ca...For a simple digraph G, let β（G） be the size of the smallest subset X E（G） such that G - X has no directed cycles, and let γ（G） be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This paper proves that β（G） ≤ 0.3819γ（G） if G is a 4-free digraph, and β（G） ≤ 0.2679γ（G） if G is a 5-free digraph. These improve the results of Sullivan in 2008.展开更多
In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is sho...In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.展开更多
基金Supported by NSFC(Grant No.10771225)Fundamental Research Funds for the Central University
文摘In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.
基金The NSF(11301450,61363020,11226294)of Chinathe Youth Science and Technology Education Project(2014731003)of Xinjiang Province
文摘Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.
基金supported by the Key Project of Chinese Ministry of Education(Grant No.109140)supported by NNSF of China(Grant No.11071233)
文摘For a simple digraph G, let β（G） be the size of the smallest subset X E（G） such that G - X has no directed cycles, and let γ（G） be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This paper proves that β（G） ≤ 0.3819γ（G） if G is a 4-free digraph, and β（G） ≤ 0.2679γ（G） if G is a 5-free digraph. These improve the results of Sullivan in 2008.
基金Research supported by the Science Foundation of Shandong Province.
文摘In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.
