In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-...In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be an MCB. Furthermore, we show that the structure of MCB in a (weighted)graph is unique. The property is also true for those having a longest length (although much work has been down in evaluating MCB, little is known for those having a longest length). We use those methods to find out some unknown properties for short cycles sharing particular properties in (unweighted) graphs. As applications, we determine the structures of short cycles in an embedded graph and show that there exist polynomially bounded algorithms in finding a shortest contractible cycle and a shortest two-sided cycle provided such cycles exist. Those answer an open problem of B. Mohar and C. Thomassen.展开更多
The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the gue...The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the guest graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where ｜Fv｜ is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.展开更多
Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in prat-ical uses such as electric circuit theory and structur...Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in prat-ical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of 'small face-embeddings'. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.展开更多
In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-tra...In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.展开更多
This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and...This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP- 1(k) network. After that, we discuss the embedding of a 2-D mesh, M1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence- column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to a/10+2 and the congestion is equal to max{ a/10+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.展开更多
In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube with dilation at most 2 and prove its correctness.
For most of circular graph the length of the minimum cycle basis is given. For the others a bound of the length of the minimum cycle basis is given and the given bound is reached.
基金supported by the National Natural Science Foundation of China(Grant No.10271048)the first author also acknowledges the financial support of Shanghai Priority Academic Disciplinethe fund of the Science and Technology Commission of Shanghai Municipality(Grant No.04JC14031).
文摘In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be an MCB. Furthermore, we show that the structure of MCB in a (weighted)graph is unique. The property is also true for those having a longest length (although much work has been down in evaluating MCB, little is known for those having a longest length). We use those methods to find out some unknown properties for short cycles sharing particular properties in (unweighted) graphs. As applications, we determine the structures of short cycles in an embedded graph and show that there exist polynomially bounded algorithms in finding a shortest contractible cycle and a shortest two-sided cycle provided such cycles exist. Those answer an open problem of B. Mohar and C. Thomassen.
基金Supported by the National Natural Science Foundation of China(11071022)the Key Project of Hubei Department of Education(D20092207)
文摘The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the guest graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where ｜Fv｜ is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.
文摘Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in prat-ical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of 'small face-embeddings'. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.
基金Supported by the National Natural Science Foundation of China(No.10271048,10671073)Supported by Shanghai Leading Academic Discipline Project(No.B407)Science and Technology Commission of Shanghai Municipality(No.07XD14011)
文摘In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.
文摘This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP- 1(k) network. After that, we discuss the embedding of a 2-D mesh, M1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence- column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to a/10+2 and the congestion is equal to max{ a/10+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.
文摘In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube with dilation at most 2 and prove its correctness.
基金Supported by the NSF of Renmin University of China
文摘For most of circular graph the length of the minimum cycle basis is given. For the others a bound of the length of the minimum cycle basis is given and the given bound is reached.
