Abstract | ||
---|---|---|
A graph G is terminal-pairable with respect to a demand (loopless) multigraph D on the same vertex set as G, if there exist edge-disjoint paths joining the end vertices of every demand edge of D. In this short note, we improve the upper bound on the largest Δ(n) with the property that the complete graph on n vertices is terminal-pairable with respect to any demand multigraph of maximum degree at most Δ(n). This disproves a conjecture originally stated by Csaba, Faudree, Gyárfás, Lehel and Schelp. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.disc.2018.06.005 | Discrete Mathematics |
Keywords | Field | DocType |
Terminal-pairability,Demand graph | Complete graph,Graph,Discrete mathematics,Combinatorics,Multigraph,Vertex (geometry),Upper and lower bounds,Degree (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
341 | 9 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
António Girão | 1 | 1 | 3.07 |
Gábor Mészáros | 2 | 4 | 3.62 |