Name
Abstract | ||
|---|---|---|
For a positive integer k, a graph is k-knitted if for each subset S of k vertices, and every partition of S into (disjoint) parts S1,…,St for some t≥1, one can find disjoint connected subgraphs C1,…,Ct such that Ci contains Si for each i∈[t]≔{1,2,…,t}. In this article, we show that if the minimum degree of an n-vertex graph G is at least n∕2+k∕2−1 when n≥2k+3, then G is k-knitted. The minimum degree is sharp. As a corollary, we obtain that k-contraction-critical graphs are k8-connected. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.disc.2019.06.038 | Discrete Mathematics |
Keywords | Field | DocType |
Graph linkage,Minimum degree,Contraction-critical graphs,Connectivity | Integer,Graph,Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Corollary,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
342 | 11 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Runrun Liu | 1 | 8 | 5.29 |
| Martin Rolek | 2 | 0 | 1.01 |
| Gexin Yu | 3 | 340 | 40.11 |