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

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
نویسندگان
, , , ,