An upper bound for the crossing number of bubble-sort graph Bn

被引：0

作者：

Zheng, Baigong ^{[1
]}

Yang, Yuansheng ^{[1
]}

Xu, Xirong ^{[1
]}

机构：

[1] Dalian Univ Technol, Sch Comp Sci & Technol, Dalian 116024, Peoples R China

来源：

UTILITAS MATHEMATICA | 2016年 / 101卷

关键词：

Crossing number; Drawing; Bubble-sort graph;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The crossing number of a graph G is the minimum number of pairwise intersections of edges in a drawing of G. Motivated by the recent work [Faria, L., Figueiredo, C.M.H. de, Sykora, O., Vrt'o, I.: An improved upper bound on the crossing number of the hypercube. J. Graph Theory 59, 145-161 (2008)], we give an upper bound of the crossing number of n-dimensional bubble-sort graph B-n.

引用

页码：309 / 328

页数：20

共 10 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[2] Hamiltonian laceability of bubble-sort graphs with edge faults [J].

Araki, Toru ;

Kikuchi, Yosuke .

INFORMATION SCIENCES, 2007, 177 (13) :2679-2691

[3] A FRAMEWORK FOR SOLVING VLSI GRAPH LAYOUT PROBLEMS [J].

BHATT, SN ;

LEIGHTON, FT .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (02) :300-343

[4] Matching preclusion for the (n, k)-bubble-sort graphs [J].

Cheng, Eddie ;

Liptak, Laszlo ;

Sherman, David .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (11) :2408-2418

[5]

Erdos P., 1973, AM MATH MONTHLY, V80, P52, DOI DOI 10.2307/2319261

[6] An improved upper bound on the crossing number of the hypercube [J].

Faria, Luerbio ;

Herrera de Figueiredo, Celina Miraglia ;

Sykora, Ondrej ;

Vrt'o, Imrich .

JOURNAL OF GRAPH THEORY, 2008, 59 (02) :145-161

[7] CROSSING NUMBER IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03) :312-316

[8]

Lin XH, 2006, UTILITAS MATHEMATICA, V71, P245

[9] The construction of mutually independent Hamiltonian cycles in bubble-sort graphs [J].

Shih, Yuan-Kang ;

Lin, Cheng-Kuan ;

Hsu, D. Frank ;

Tan, Jimmy J. M. ;

Hsu, Lih-Hsing .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (10) :2212-2225

[10]

Zheng WP, 2008, UTILITAS MATHEMATICA, V75, P211

← 1 →