کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648036 | 1342390 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Long cycles in unbalanced bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let G[X,Y]G[X,Y] be a 2-connected bipartite graph with |X|≥|Y||X|≥|Y|. For S⊆V(G)S⊆V(G), we define δ(S;G):=min{dG(v):v∈S}δ(S;G):=min{dG(v):v∈S}. We define σ1,1(G):=min{dG(x)+dG(y):x∈X,y∈Y,xy∉E(G)}σ1,1(G):=min{dG(x)+dG(y):x∈X,y∈Y,xy∉E(G)} and σ2(X):=min{dG(x)+dG(y):x,y∈X,x≠y}σ2(X):=min{dG(x)+dG(y):x,y∈X,x≠y}. We denote by c(G)c(G) the length of a longest cycle in GG. Jackson [B. Jackson, Long cycles in bipartite graphs, J. Combin. Theory Ser. B 38 (1985) 118–131] proved that c(G)≥min{2δ(X;G)+2δ(Y;G)−2,4δ(X;G)−4,2|Y|}c(G)≥min{2δ(X;G)+2δ(Y;G)−2,4δ(X;G)−4,2|Y|}. In this paper, we extend this result, and prove that c(G)≥min{2σ1,1(G)−2,2σ2(X)−4,2|Y|}c(G)≥min{2σ1,1(G)−2,2σ2(X)−4,2|Y|}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 11, 6 June 2012, Pages 1857–1862
Journal: Discrete Mathematics - Volume 312, Issue 11, 6 June 2012, Pages 1857–1862
نویسندگان
Shuya Chiba, Jun Fujisawa, Masao Tsugaki, Tomoki Yamashita,