pith. machine review for the scientific record. sign in

arxiv: 1811.07482 · v2 · submitted 2018-11-19 · 🧮 math.CO

Recognition: unknown

Minimum degree condition for a graph to be knitted

Authors on Pith no claims yet
classification 🧮 math.CO
keywords degreegraphknittedminimumconnecteddisjointldotsarticle
0
0 comments X
read the original abstract

For a positive integer $k$, a graph is $k$-knitted if for each $k$-subset $S$ of vertices, and every partition of $S$ into disjoint parts $S_1, \ldots, S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1, \ldots, C_t$ such that $C_i$ contains $S_i$ for each $i$. 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\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $\left\lceil\frac{k}{8}\right\rceil$-connected.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.