Timeline for Computing the number of ways to delete vertices sequentially without disconnecting a graph
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2022 at 19:56 | comment | added | Nick L | Suppose we add a "hair" to a graph $G$ i.e. add one edge and one vertex, to $v \in V_G$ giving $G'$. Then (calling the invariant $S$) we have $S(G') = S(G) + 2S(G \setminus v)$. This gives a pretty systematic way to compute the invariant for trees. | |
| Apr 6, 2022 at 1:33 | comment | added | Aaron Meyerowitz | For the ``lollypop" graph obtained by attaching one vertex $v$, to a vertex $w$ of an $n$-cycle, the sweeping number is $L_n=2^{n-2}\frac{n^2+n+2}2.$ Sketch: It works for $n=3.$ Deleting $v$ first leaves a cycle so $n\,2^{n-2}$ ways to finish. The sequences which delete $v$ on the second move all leave a path of length $n-1$ so there are $(n-1)2^{n-2}$ of these. The remaining ways amount to $2(L_{n-1}-(n-1)2^{n-3})$ because the two vertices deleted are (in one order or the other) the endpoints of an edge of the cycle not incident with $w.$ | |
| Apr 6, 2022 at 0:24 | comment | added | Timothy Chow | @DylanThurston For the Tutte polynomial, I can pick any edge, and recursively compute what happens when I delete or contract that edge. I don't need an outer loop over all possible choices of that edge. For your invariant, naively it seems that I need to loop over all possible choices of the first vertex to delete. Is that correct? Or is there a smarter recursive computation? | |
| Apr 6, 2022 at 0:04 | comment | added | Dylan Thurston | @TimothyChow it was just that the way of recursively computing it felt vaguely similar to the recursive computation of the Tutte polynomial. But it's really a stretch. | |
| Apr 5, 2022 at 23:08 | comment | added | Timothy Chow | I don't understand the proposed relationship with the Tutte polynomial. All trees have the same Tutte polynomial, but the number you are interested in is different for different trees. | |
| Apr 5, 2022 at 17:36 | comment | added | Aaron Meyerowitz | @SamHopkins Triangle free would then be enough. | |
| Apr 5, 2022 at 17:02 | comment | added | Sam Hopkins | @NickL: Ah, sorry, good catch. At any rate, the argument applies to trees, then. | |
| Apr 5, 2022 at 16:00 | comment | added | Nick L | It is a triangle with one extra vertex joined to one of the vertices. | |
| Apr 5, 2022 at 15:44 | comment | added | Nick L | For one of them he says that the invariant is 14 | |
| Apr 5, 2022 at 13:56 | comment | added | Sam Hopkins | Unless I'm mistaken, there is a simple reason why the number is a multiple of 4 for every graph (with 4 or more vertices): Dylan said that this is true for every graph with 4 vertices, and if the number is a multiple of $m$ for every graph with $n$ vertices it is a multiple of $m$ for every graph with $n+1$. | |
| Apr 5, 2022 at 12:28 | comment | added | Nick L | Sorry it should read $2 \sum_{i=0}^{n} i! c(n,i) 2 (n-i+2)!$ | |
| Apr 5, 2022 at 11:04 | comment | added | Nick L | You probably already know this, but there are a few more infinite families where it is possible to get a formula: For example formula for the Bipartite graph $K_{2,n}$ (and $n \geq 3$) the sweepout number is $2 \sum_{i=0}^{n} i! c(n,i) 2 (n-i-1)!$ Just by considering paths in the part with degree two vertices and then at some point the graph becomes a star graph then one can your formula in that case. | |
| Apr 5, 2022 at 5:50 | comment | added | Aaron Meyerowitz | It is kind of a dumb computation, but faster than I thought. Going out to $100$ I also see the $4p$ phenomenon at $c_{3,37,82}$ and $c_{6,59,65}$ but no place else. Since $c_{i,j,k}=c_{i-1,j,k}+c_{i,j-1,k}+c_{i,j,k-1}$, If all four are multiples of $4$, then an even number are $4$ times an odd. Nonetheless, I don't see that past $c_{32,33,65}.$ | |
| Apr 5, 2022 at 5:04 | comment | added | Aaron Meyerowitz | @DylanThurstan Let $c_{ijk}$ be the number of deletion sequences for a tree with three leaves at distances $i \leq j \leq k$ from the unique degree $3$ point. Based (now) on all the counts with $1 \leq i \leq k\leq 50$ (so $\binom{51}3$ cases) I see that these are always a multiple of $4.$ The phenomenon I meant was that of $c=4p$ with $p$ prime. It happens $40$ times over that range , the last being for $c_{3,5,50},c_{3,6,9}$ and $c_{3,26,37}$. Also, there are $634$ cases with $c$ being $4$ times an odd number, The last being someplace with $i=16.$ | |
| Apr 5, 2022 at 4:28 | comment | added | Dylan Thurston | @AaronMeyerowitz , we looked more and noticed the numbers are not round in general, see some more data in the post. I didn't understand which phenomenon you were seeing or not. | |
| Apr 5, 2022 at 4:26 | history | edited | Dylan Thurston | CC BY-SA 4.0 |
added 390 characters in body; edited title
|
| Apr 5, 2022 at 1:23 | comment | added | Aaron Meyerowitz | For trees obtained by identifying the endpoints of three intervals, the count appears to always be a multiple of $4.$ But it can be $4p$ with $p$ prime. For paths of length $4,7,10$ joined this way (so $19$ vertices) I get $4\cdot 4172117.$ I didn't see that phenomen past that as far as I looked (up to $10,20,30$.) If the graph has high symmetry, that will be reflected in the number. | |
| Apr 4, 2022 at 15:40 | comment | added | Jukka Kohonen | Alex, I agree that the shellability (ordering edges) seems relevant to the question here (ordering vertices), but it is not clear what exactly the connection is. | |
| Apr 4, 2022 at 14:24 | comment | added | Alex Lazar | @Jukka good catch, thanks! It still feels to me like there's something involving shellability (or vertex-decomposability) going on here --- $n2^{n-2}$ is the number of shelling orders of the cycle graph. | |
| Apr 4, 2022 at 12:50 | comment | added | Sam Hopkins | Not directly related to your question, but worth mentioning that there are various well-studied classes of graphs (e.g. threshold graphs, chordal graphs) that are defined recursively in terms of adding a single vertex at a time. | |
| Apr 4, 2022 at 12:25 | comment | added | Jukka Kohonen | @Alex, it does not seem equivalent. Consider a path on $3$ vertices 1—2—3. The vertices can be numbered in 4 ways. But the line graph is 12—23, it has only one edge so only one shelling. | |
| Apr 4, 2022 at 8:16 | comment | added | Alex Lazar | I think this is equivalent to counting shelling orders of the line graph of $G$, isn't it? See, e.g., mathoverflow.net/questions/297411/… and arxiv.org/abs/1809.10263 for discussions of some (infinite families of) special cases. | |
| Apr 4, 2022 at 4:31 | history | asked | Dylan Thurston | CC BY-SA 4.0 |