Timeline for Pairs of vertices with high degree difference
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2021 at 17:55 | answer | added | Louis D | timeline score: 1 | |
| Apr 10, 2021 at 16:29 | vote | accept | CommunityBot | ||
| Apr 10, 2021 at 10:14 | answer | added | user153000 | timeline score: 8 | |
| S Apr 9, 2021 at 19:37 | history | bounty ended | CommunityBot | ||
| S Apr 9, 2021 at 19:37 | history | notice removed | user153000 | ||
| Apr 9, 2021 at 18:46 | answer | added | RobPratt | timeline score: 2 | |
| Apr 8, 2021 at 19:27 | comment | added | RobPratt | Optimization for $n \le 15$ and $\lfloor n/2 \rfloor \le k \le n-1$ yields empirical formula $\max \mathcal{I}_k(G) = (k+1)(n-k-1)$. | |
| Apr 8, 2021 at 18:08 | comment | added | Louis D | Another observation is that you can assume $R=\emptyset$ since if there were a counterexample with $R\neq \emptyset$, then you could add all edges inside the set $R$ and all edges between the sets $A$ and $R$ which has at least as many pairs of vertices with degree difference at least $k$. | |
| Apr 8, 2021 at 14:05 | comment | added | Louis D | A couple of trivial comments: (i) You can let $B:=\{v_i:\deg(v_i)\leq n-k-1\}$ since there can be no vertices of degree $n$. (ii) Since $\mathcal{I}_k(G)\leq |A||B|$, you can assume you are in the case where $n-k<\min(|A|, |B|)\leq \max(|A|, |B|)<k$. | |
| S Apr 8, 2021 at 13:08 | history | bounty started | CommunityBot | ||
| S Apr 8, 2021 at 13:08 | history | notice added | user153000 | Draw attention | |
| Apr 7, 2021 at 16:56 | history | undeleted | user153000 | ||
| Apr 7, 2021 at 15:55 | history | deleted | user153000 | via Vote | |
| Apr 6, 2021 at 12:29 | history | asked | user153000 | CC BY-SA 4.0 |