Hamilton Paths in n-Extendable Bipartite Graphs

被引：0
|
作者：
Gan, Zhiyong [1 ]
Lou, Dingjun [2 ]
机构：
[1] South China Normal Univ, Sch Comp, Guangzhou 510631, Peoples R China
[2] Sun Yat Sen Univ, Dept Comp Sci, Guangzhou 510275, Peoples R China
来源：
ARS COMBINATORIA | 2021年 / 154卷
关键词：
n-extendable graph; bipartite graph; Hamilton path; Hamiltoni an-laceable;
D O I：
暂无
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph G is said to he n-extendable if it has a matching of size n, and every matching of size n extends to a perfect matching of G. Let G = (X, Y) he an n-extendable bipartite graph with v <= 6n similar to 2. In this paper, we prove that G is Hamiltonian-laceable, i.e. for any pair of vertices x is an element of X, y is an element of Y, there is a Hamilton path from x to y in G. The bound for v(G) is sharp.
引用
收藏
页码：3 / 21
页数：19
相关论文
共 50 条
  • [1] Hamilton Cycles in n-Extendable Bipartite Graphs
    Li, Yueping
    Lou, Dingjun
    ARS COMBINATORIA, 2018, 139 : 3 - 18
  • [2] M-alternating paths in n-extendable bipartite graphs
    Aldred, REL
    Holton, DA
    Lou, DJ
    Saito, A
    DISCRETE MATHEMATICS, 2003, 269 (1-3) : 1 - 11
  • [3] On defect n-extendable bipartite graphs
    Wen, Xuelian
    IMECS 2007: International Multiconference of Engineers and Computer Scientists, Vols I and II, 2007, : 2347 - 2352
  • [4] A novel characterization of n-extendable bipartite graphs
    Lin, Hong
    Guo, Xiaofeng
    ARS COMBINATORIA, 2009, 91 : 353 - 362
  • [5] On the structure of minimally n-extendable bipartite graphs
    Lou, DJ
    DISCRETE MATHEMATICS, 1999, 202 (1-3) : 173 - 181
  • [6] Characterizing minimally n-extendable bipartite graphs
    Lou, Dingjun
    DISCRETE MATHEMATICS, 2008, 308 (11) : 2269 - 2272
  • [7] Long Cycles in n-Extendable Bipartite Graphs
    Gan, Zhiyong
    Lou, Dingjun
    ARS COMBINATORIA, 2019, 144 : 91 - 106
  • [8] CONSTRUCTION CHARACTERIZATIONS FOR DEFECT n-EXTENDABLE BIPARTITE GRAPHS
    Wen, Xuelian
    Yang, Zihui
    Zhang, Zan-Bo
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2009, 6 (03) : 353 - 360
  • [9] Characterizing defect n-extendable bipartite graphs with different connectivities
    Wen, Xuelian
    Lou, Dingjun
    DISCRETE MATHEMATICS, 2007, 307 (15) : 1898 - 1908
  • [10] ON N-EXTENDABLE GRAPHS
    PLUMMER, MD
    DISCRETE MATHEMATICS, 1980, 31 (02) : 201 - 210
12345