12
$\begingroup$

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. (Let us call this the sweepout number until we find a reference elsewhere.)

For example, for $K_n$ this is $n!$, for a path on $n$ vertices this is $2^{n-1}$. These are clearly the largest and smallest possible values. Other values:

  • For a star with $n-1$ leaves, the answer is $2(n-1)!$
  • For a cycle graph, the answer is $n2^{n-2}$

The answers are sometimes divisible; for instance, for the 4-vertex graphs we get 8, 12, 14, 16, 20, 24. (The answer is automatically even.)

This must have been studied, but we can't find the key word. It seems possibly related to the Tutte polynomial.

Can this be computed in any reasonable way?

Update: Divisibility does not continue for large graphs. For an example that also hints at the motivation, consider the dual graph to the division of Pennsylvania into congressional districts. (This is a graph with 18 vertices). The sweepout number for this graph is 10,672,157,119,848, which is not round.

Improve this question
$\endgroup$
21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex Lazar
    Commented Apr 4, 2022 at 8:16
  • 3
    $\begingroup$ @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. $\endgroup$
    – Jukka Kohonen
    Commented Apr 4, 2022 at 12:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Hopkins
    Commented Apr 4, 2022 at 12:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jukka Kohonen
    Commented Apr 4, 2022 at 15:40
  • 2
    $\begingroup$ For one of them he says that the invariant is 14 $\endgroup$
    – Nick L
    Commented Apr 5, 2022 at 15:44

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .