Originator: Peter Slater (presented by Noah Prince - REGS 2007; updated results added)
Definitions: Given a graph and a vertex weighting by nonnegative integers, an acquisition move is the movement of all weight from some vertex of positive weight k to some neighboring vertex having weight at least k before the move. When no further moves can be made, the vertices with positive weight form an independent set. The acquisition number of a graph G, introduced by Lampert and Slater [LS] and written a(G), is the minimum size of that independent set when the initial configuration puts weight 1 on each vertex.
In the acquisition game on a graph G, acquisition moves are made alternately by two players, Max and Min. The aim of Max is to make the final independent set large; Min seeks to make it small. The game acquisition number, written ag(G), is the outcome under optimal play. That is, Max can guarantee that the final configuration has at least ag(G) vertices, and Min can guarantee that it has no more than ag(G) vertices. The answer can be quite different depending on who moves first; we assume that Min moves first.
Background: Let G be an n-vertex graph. Lampert and Slater [LS] showed that a(G)≤(n+1)/3 when G is connected, and this is sharp. If H is a subgraph of G, then a(G)≤a(H). Thus the acquisition numbers of trees provide upper bounds for the acquisition numbers of connected graphs. Since a(Pn)=⌈n/4⌉, the path is not the worst tree.
Denser graphs have smaller acquisition numbers. The questions tend to be of two flavors: what is the maximum acquistion number among n-vertex graphs in a particular family, and what properties force the acquisition number to be small (such as 1). The questions posed here were generated in discussion at REGS 2007.
Question 1: What is the largest acquisition number for an n-vertex k-connected graph?
Comments: Placing a constant lower bound on the minimum degree of a connected graph is not enough to reduce the acquisition number below linear; using the trees with large acquisition number, one can construct connected G with δ(G)=k and a(G)>n/(2k+3) (for large n). However, if &delta(G)≥(n-1)/2 (and G≠C5), then a(G)=1 [LPWWW]. Also, if a(G)>1, then the complement of G has acquisition number 1 [LPWWW].
Conjecture 2: There is a constant c such that every graph with diameter 2 has acquisition number at most c. (Perhaps c=2.)
Comments: If diam(G)=2, then a(G)&le250 lg n lg lg lg n. If diam(G)=2 and C4⊄G and Δ(G)≥8, then a(G)=1 [LPWWW].
When a vertex acquires weight from another, its weight at most doubles, and it can never acquire weight from that vertex again. Hence a vertex of degree d ends with weight at most 2d. Therefore a(G)≥n/2d when G has n vertices and maximum degree d. Equality holds for the d-dimensional cube.
Question 3: Is the d-dimensional hypercube the only graph G with maximum degree d such that a(G)=|V(G)|/2d?
Question 4: In the model of random graphs with independent edge probability p, what is the expected value of a(G)? What is the threshold probability for a(G)=1? What is the threshold probability for making a(G) almost always sublinear?
Comments: Results of [LPWWW] give an upper bound on the first threshold and a lower bound on the second. In particular, a(G) is almost always 1 when p≥(3lnn/n)1/2), and a(G) is almost always linear when p≤c/n.
For game acquisition number, the corresponding questions are more difficult. Again the maximum over n-vertex connected graphs is attained by a tree, and the path is not the worst. Slater and Wang [SW] determined that ag(Pn) equals 2n/5 plus a small constant depending on the congruence class of n modulo 5. However, an n-vertex caterpillar having a spine with three vertices and maximum degree about n/3 has game acquisition number about 2n/3.
Question 5: What is the maximum of ag(G) when G is a tree with n vertices?
Question 6: What is ag(Km,n)?
Comments: Regardless of either player's strategy, ag(Kn)=1. For a star, the value is 1 if Min moves first, n-1 if Max moves first. The problem for Km,n is surprisingly difficult. Nevertheless, ag(Kn,n)=2 when n ≥ 2 [MSWW]. As m grows (with n fixed), it seems that ag(Km,n) grows to a limit that is somewhere between n/2 and n.
References:
[LS] Lampert, D. E.; Slater, P. J.; The acquisition number of a graph.
Proc. Twenty-sixth Southeastern Intl Conf on Combinatorics, Graph Theory and
Computing (Boca Raton, FL, 1995). Congr. Numer. 109 (1995), 203--210.
[LPWWW] Timothy D. LeSaulnier, Noah Prince, Paul S. Wenger, Douglas B. West,
and Pratik Worah, Acquisition number of graphs, draft.
[MSWW] Kevin Milans, Chris Stocker, Lesley Wiglesworth, and Douglas B. West,
Game acquisition number of complete bipartite graphs, draft.
[SW] Slater, Peter J.; Wang, Yan; The competitive-acquisition numbers of paths.
Proc. Thirty-Fifth Southeastern Intl Conf on Combinatorics, Graph Theory and
Computing (Boca Raton, FL, 2004). Congr. Numer. 167 (2004), 33--43.