Longest cycles in certain bipartite graphs
Let G be a connected bipartite graph with bipartition (X,Y) such that |X|≥|Y|(≥2), n=|X| and m=|Y|. Suppose, for all vertices x∈X and y∈Y, dist(x,y)=3 implies d(x)+d(y)≥n+1. Then G contains a cycle of length 2m. In particular, if m=n, then G is hamiltomian.
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1998-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171298000131 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545443930701824 |
|---|---|
| author | Pak-Ken Wong |
| author_facet | Pak-Ken Wong |
| author_sort | Pak-Ken Wong |
| collection | DOAJ |
| description | Let G be a connected bipartite graph with bipartition (X,Y) such that |X|≥|Y|(≥2),
n=|X| and m=|Y|. Suppose, for all vertices x∈X and y∈Y, dist(x,y)=3 implies
d(x)+d(y)≥n+1. Then G contains a cycle of length 2m. In particular, if m=n, then G is
hamiltomian. |
| format | Article |
| id | doaj-art-71b14abf88f748b2bb463a40fdd0192f |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1998-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-71b14abf88f748b2bb463a40fdd0192f2025-02-03T07:25:45ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251998-01-0121110310610.1155/S0161171298000131Longest cycles in certain bipartite graphsPak-Ken Wong0Department of Mathematics and Computer Science, Seton Hall University, South Orange 07079, NJ, USALet G be a connected bipartite graph with bipartition (X,Y) such that |X|≥|Y|(≥2), n=|X| and m=|Y|. Suppose, for all vertices x∈X and y∈Y, dist(x,y)=3 implies d(x)+d(y)≥n+1. Then G contains a cycle of length 2m. In particular, if m=n, then G is hamiltomian.http://dx.doi.org/10.1155/S0161171298000131Bipartite graphs2-connected graphshamiltomian graphs. |
| spellingShingle | Pak-Ken Wong Longest cycles in certain bipartite graphs International Journal of Mathematics and Mathematical Sciences Bipartite graphs 2-connected graphs hamiltomian graphs. |
| title | Longest cycles in certain bipartite graphs |
| title_full | Longest cycles in certain bipartite graphs |
| title_fullStr | Longest cycles in certain bipartite graphs |
| title_full_unstemmed | Longest cycles in certain bipartite graphs |
| title_short | Longest cycles in certain bipartite graphs |
| title_sort | longest cycles in certain bipartite graphs |
| topic | Bipartite graphs 2-connected graphs hamiltomian graphs. |
| url | http://dx.doi.org/10.1155/S0161171298000131 |
| work_keys_str_mv | AT pakkenwong longestcyclesincertainbipartitegraphs |