The terminal-pairability problem in complete bipartite graphs

被引：0

作者：

Lv, Zequn ^{[1
]}

Lu, Mei ^{[1
]}

机构：

[1] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2021年 / 291卷

基金：

中国国家自然科学基金;

关键词：

Terminal-pairability; Demand graph; Bipartite graph;

D O I：

10.1016/j.dam.2020.12.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we study the terminal-pairability problem in the case that the base graph is a complete bipartite graph, and the demand graph is a bipartite graph on the same vertex set and using copies of edges of the base graph as demand edges. In 1998, Gyarfas and Schelp raised a question that if the maximum degree of the demand graph Delta(D) <= Inverted right perpendicularn/3Inverted left perpendicular holds, then whether D is terminal-pairable in K-n,K-n? We partially answer the question. (C) 2020 Elsevier B.V. All rights reserved.

引用

页码：64 / 67

页数：4

共 15 条

[1] Terminal-pairability in complete bipartite graphs [J].

Colucci, Lucas ;

Erdos, Peter L. ;

Gyori, Ervin ;

Mezei, Tarnas Robert .

DISCRETE APPLIED MATHEMATICS, 2018, 236 :459-463

[2] NETWORKS COMMUNICATING FOR EACH PAIRING OF TERMINALS [J].

CSABA, L ;

FAUDREE, RJ ;

GYARFAS, A ;

LEHEL, J ;

SCHELP, RH .

NETWORKS, 1992, 22 (07) :615-626

[3]

Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048

[4]

FAUDREE R., 1992, Congressus Numerantium, V88, P111

[5]

FAUDREE R.J., 1992, New Zealand Journal of Mathematics, V21, P91

[6]

FAUDREE R.J., 1999, Journal of Combinatorial Mathematics and Combinatorial Computing, V20, P145

[7] THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH [J].

GALVIN, F .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :153-158

[8] A communication problem and directed triple systems [J].

Gyarfas, A ;

Schelp, RH .

DISCRETE APPLIED MATHEMATICS, 1998, 85 (02) :139-147

[9]

Gyori E., 2018, J COMBIN MATH COMBIN, V107, P221

[10] Note on terminal-pairability in complete grid graphs [J].

Gyori, Ervin ;

Mezei, Tumas Robert ;

Meszaros, Gabor .

DISCRETE MATHEMATICS, 2017, 340 (05) :988-990

← 1 2 →