The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved tha...The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved that Bn is edge-bipancyclic for n ≤ 5 and Bn - F is bipancyclic when n ≥ 4 and IFI≤ n - 3. In this paper, we improve this result by showing that for any edge set F of Bn with IFI ≤ n - 3, every edge of Bn - F lies on a cycle of every even length from 6 to n! for n≤ 5 and every edge of Bn - F lies on a cycle of every even length from 8 to n! for n = 4.展开更多
In this paper we prove the following: Let G be connected balanced bipartite graph of order 2n> 4. If G satisfies the localization condition |NZ(u)\N(v)| + 2 < d(u), for any u,v∈ V(G) and d(u, v) = 3 where N(u) ...In this paper we prove the following: Let G be connected balanced bipartite graph of order 2n> 4. If G satisfies the localization condition |NZ(u)\N(v)| + 2 < d(u), for any u,v∈ V(G) and d(u, v) = 3 where N(u) = {w|w∈V(G) and d(u, w)= 2}, then G is either bipancyclic or isomorphic to C6. Furthermore, a conjecture is proposed.展开更多
Let G be a hamiltonian, bipartite graph on 2n vertices, where n > 3. It isshown that if e(G) > n(n ― 1)/2 + 2 then G contains cycles of every possible even length. Thisimproves a result of Entringer and Schmeic...Let G be a hamiltonian, bipartite graph on 2n vertices, where n > 3. It isshown that if e(G) > n(n ― 1)/2 + 2 then G contains cycles of every possible even length. Thisimproves a result of Entringer and Schmeichel.展开更多
Let G =(V1,V2,E) be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B(G),is defined to be n if G =Kn and min i∈{1,2}|N(S)|〈n min |N(S)|/|S|otherwise.We call G b...Let G =(V1,V2,E) be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B(G),is defined to be n if G =Kn and min i∈{1,2}|N(S)|〈n min |N(S)|/|S|otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B(G) 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows:Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n(n is large enough) vertices such that B(G) c and δ(G)(2-c)n/(3-c)+2/3.Then G is bipancyclic.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.10626053,10701074 and 11171160)Sciences Foundation for Young Scholars of Beijing Normal UniversityPriority Discipline of Beijing Normal University,Fundamental Research Funds for the Central Universities
文摘The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved that Bn is edge-bipancyclic for n ≤ 5 and Bn - F is bipancyclic when n ≥ 4 and IFI≤ n - 3. In this paper, we improve this result by showing that for any edge set F of Bn with IFI ≤ n - 3, every edge of Bn - F lies on a cycle of every even length from 6 to n! for n≤ 5 and every edge of Bn - F lies on a cycle of every even length from 8 to n! for n = 4.
文摘In this paper we prove the following: Let G be connected balanced bipartite graph of order 2n> 4. If G satisfies the localization condition |NZ(u)\N(v)| + 2 < d(u), for any u,v∈ V(G) and d(u, v) = 3 where N(u) = {w|w∈V(G) and d(u, w)= 2}, then G is either bipancyclic or isomorphic to C6. Furthermore, a conjecture is proposed.
基金Supported partially by Project 02139 of Ministry of Education, China
文摘Let G be a hamiltonian, bipartite graph on 2n vertices, where n > 3. It isshown that if e(G) > n(n ― 1)/2 + 2 then G contains cycles of every possible even length. Thisimproves a result of Entringer and Schmeichel.
基金Supported by the Scientific Research Fund of Hubei Provincial Education Department(B2015021)
文摘Let G =(V1,V2,E) be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B(G),is defined to be n if G =Kn and min i∈{1,2}|N(S)|〈n min |N(S)|/|S|otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B(G) 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows:Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n(n is large enough) vertices such that B(G) c and δ(G)(2-c)n/(3-c)+2/3.Then G is bipancyclic.