Deshi Ye
email: yedeshi@zju.edu.cn.

Guochuan Zhang

On-line extensible bin packing with unequal bin sizes

Keywords: On-line algorithms, extensible bin packing, competitive ratio

In the extensible bin packing problem we are asked to pack a set of items into a given number of bins, each with an original size. However, the original bin sizes can be extended if necessary. The goal is to minimize the total size of the bins. We consider the problem with unequal (original) bin sizes and give the complete analysis on a list scheduling algorithm (LS). Namely we present tight bounds of LS for every collection of original bin sizes and every number of bins. We further show better on-line algorithms for the two-bin case and the three-bin case. Interestingly, it is proved that the on-line algorithms have better competitive ratios for unequal bins than for equal bins. Some variants of the problem are also discussed.

Introduction

We consider the following on-line extensible bin packing problem: there are m bins B 1 , B 2 , . . . , B m with original bin sizes b 1 , b 2 , . . . , b m . The original bin sizes can be extended if needed. The (final) size of a bin is defined to be the maximum of the original bin size and the total size of the items assigned to it. Items {a 1 , a 2 , . . . , a n } arrive over list, which are not known in advance. When an item a i arrives it must immediately and irrevocably be assigned to one of the bins and the next item a i+1 becomes known only after a i has been assigned. The size of item a i is p i . The goal is to assign all items to the bins such that the total size of the bins is minimized.

This problem arises in a wide variety of contexts. It has many applications in bin packing, storage allocation and scheduling problems. Consider, for instance, a set of workers is given with regular working times. In case of needed, the worker can do some overtime works. The problem is to assign duties to the workers in such a way that the total work (regular working times plus overtime works) is minimized.

Deshi Ye and Guochuan Zhang

Competitive ratios. An instance of the problem consists of a list of items and m bins with original sizes b 1 , b 2 , . . . , b m . Let B be the collection of bin sizes, i.e., B = {b 1 , b 2 , • • • , b m }. For any instance L, let A L (m, B) and OP T L (m, B) be the total size of the bins used by an on-line algorithm A and the total size of the bins used by an optimal off-line algorithm, respectively. Then the competitive ratio of algorithm A is

R A (m, B) = sup L A L (m, B)/OP T L (m, B).
If the bin sizes are identical, i.e., b

1 = b 2 = • • • = b m ,
the competitive ratio is denoted as R A (m). Further we define the overall competitive ratios as follows.

R A (m, •) = sup B R A (m, B), R A = sup m,B R A (m, B).
Known results. The extensible bin packing problem with unequal bin sizes was first studied by Dell'Olmo and Speranza [START_REF] Dell'olmo | Approximation algorithms for partitioning small items in unequal bins to minimize the total size[END_REF]. They considered both the off-line case and the on-line case under the assumption that the maximum item size is not larger than the minimum bin size. They showed an upper bound of 4 -2 √ 2 for an LP T (Longest Processing Time) algorithm in the off-line case and an upper bound of 5/4 for a list scheduling algorithm LS in the on-line case. The bound 5/4 is tight in terms of the overall competitive ratio, i.e., R LS = 5/4.

The special case that all bin sizes are equal to one has been extensively studied. It was proved that the off-line version of the problem is N P-hard in the strong sense [START_REF] Dell'olmo | A 13/12 approximation algorithm for bin packing with extendable bins[END_REF]. Actually, it can be easily reduced from the 3-partition problem [START_REF] Garey | Computers and Intractability: A guide to the Theory of N Pcompleteness[END_REF]. Dell'Olmo et al. [START_REF] Dell'olmo | A 13/12 approximation algorithm for bin packing with extendable bins[END_REF] proved that the worst-case ratio of the LP T algorithm is 13/12. If the number of the bins is fixed, it follows from the results of [START_REF] Woeginger | When does a dynamic programming formulation guarantee the existence of an FP-TAS[END_REF] that there exists a fully polynomial time approximation scheme. If m is not fixed, a polynomial time approximation scheme was provided in [START_REF] Alon | Approximation schemes for scheduling on parallel machines[END_REF]. Recently, Coffman and Lueker [START_REF] Coffman | Approximation algorithms for extensible bin packing[END_REF] presented a fully polynomial time asymptotic approximation scheme. They also proved that the problem does not admit a fully polynomial time approximation scheme unless P = N P, when m is not fixed. The on-line version was studied by Speranza and Tuza [START_REF] Speranza | On-line approximation algorithms for scheduling tasks on identical machines with extendable working time[END_REF]. They showed that the overall competitive ratio of a list scheduling heuristic is 5/4. Then a class of heuristics H x were presented which depend on a parameter x, 0 < x < 1, and tend to load partially loaded bins until a limit total load of 1 + x is reached on the bin. For any number of bins, the algorithm has an overall competitive ratio bounded above by 1.228. For the lower bound of the on-line problem, they showed that no heuristic can have a competitive ratio smaller than 7/6 by presenting an instance for the case that m = 2. Ye and Zhang [START_REF] Ye | On-line scheduling with extendable working time on a small number of machines[END_REF] considered on-line scheduling on a small number m of bins. They proved lower bounds for m = 3, 4 and gave the competitive ratios R Hx (m) for m = 2, 3 and 4. For m = 2 the algorithm is best possible. An improved algorithm for m = 3 was also presented.

A similar problem, called on-line bin stretching, was introduced by Azar and Regev [START_REF] Azar | On-line bin-stretching[END_REF]. A set of bins of fixed sizes is given. Items arrive on-line while it is known that there exists a valid packing of all items into the given bins. One is asked to pack all items into the bins, which can be overloaded. The goal function is the stretch factor, which is the maximum ratio for any bin between the size to which any bin was stretched (the sum of all items assigned to it) and its original size. Azar and Regev [START_REF] Azar | On-line bin-stretching[END_REF] studied the problem of identical bins, i.e. all original bins are of size 1. Epstein [START_REF] Epstein | Bin stretching revisited[END_REF] considered the two-bin case with unequal bin sizes.

Our results. In this paper, firstly we assume, as in [START_REF] Dell'olmo | Approximation algorithms for partitioning small items in unequal bins to minimize the total size[END_REF], that the largest item size is at most the smallest bin size, i.e.,

n max i=1 p i ≤ m min j=1 b j . (1)
We analyze the LS algorithm more carefully and prove the competitive ratios for each m and each collection B of bin sizes. The ratios differ for an even number of bins and an odd number of bins. It also shows that the competitive ratio of LS for the equal bins is exactly 5/4 when m is even and 5/4 -1/(4m 2 ) when m is odd. We then present an improved on-line algorithm for m = 2 and m = 3. Finally we discuss the problem without the assumption [START_REF] Alon | Approximation schemes for scheduling on parallel machines[END_REF]. A lower bound 6/5 for the overall competitive ratio is presented.

We prove the competitive ratio of LS for the two-bin case and present an improved on-line algorithm.

Notations and organization of the paper. Consider any algorithm A. During the execution of algorithm A, if a bin B j has a load (the total size of items assigned to it) at least its original size b j , B j is called heavy; otherwise, it is called light. The difference between the load and the size b j is free space if B j is light or excess if B j is heavy. Consider any instance L where

n i=1 p i < m j=1 b j .
In an optimal packing there must be some bins with free space. Construct a new instance L ′ by adding new items such that no bins have free space in the optimal packing without changing the optimal value. Note that

A L ′ (m, B) ≥ A L (m, B) and OP T L ′ (m, B) = OP T L (m, B). Therefore, A L (m, B)/OP T L (m, B) ≤ A L ′ (m, B)/OP T L ′ (m, B).
In instance L ′ , the total size of items is at least the total original size of bins. It implies that we only need to consider the instances in which the total size of items is at least the total original size of bins to prove an upper bound. Throughout the paper in proving the competitive ratios we always assume

n i=1 p i ≥ m j=1 b j .
(

) 2
The remainder of the paper is organized as follows. Section 2 gives the tight bound for a list scheduling algorithm. In Section 3, we present an on-line algorithm for m = 2 and m = 3. We discuss the problem without the item size assumption (1) in Section 4.

Tight bound for a list scheduling algorithm

List Scheduling was introduced by Graham [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF] for parallel machine scheduling. The algorithm always schedules the current job to the machine with minimum load at this time. Applying list scheduling to extensible bin packing with unequal bin sizes may result in different versions. We first consider a list scheduling algorithm, denoted by LS, which always assigns the incoming item to the bin of largest free space. Dell'Olmo and Speranza [START_REF] Dell'olmo | Approximation algorithms for partitioning small items in unequal bins to minimize the total size[END_REF] proved that R LS = 5/4. In this section we figure out R LS (m, B). Then we will show that a different version of list scheduling, which always assigns the incoming item to the bin with the least load (the total size of items in a bin), is not as good as LS in terms of the overall competitive ratio. The two versions of list scheduling are indeed equivalent if all the bin sizes are the same.

Let b min be the smallest bin sizes in the collection B and let p max be the largest item size. Under the assumption (1), we have p max ≤ b min . Consider the packing given by algorithm LS. For each bin B j , let M j be the total size of the items it accommodates after the schedule is over. If B j is light, let s j be its free space, i.e., s j = b j -M j . If B j is heavy, let r j be its free space immediately before it becomes heavy, and e j be its excess, i.e., e j = M jb j . We re-index the bins so that the first k bins are heavy, where k denotes the number of heavy bins.

Lemma 1

The competitive ratio of the list scheduling algorithm

R LS (m, B) ≥    1 + mbmin 4 P m j=1 bj , if m is even, 1 + (m 2 -1)bmin 4m P m j=1 bj , if m is odd.
Proof: Consider the following instances. If m is even, a large number of small enough items are coming first. The total size of these items is For an on-line algorithm in the resulting packing, if all bins are heavy or all bins are light, the packing is optimal. We only need to consider the packing with both heavy bin and light bin. It is crucial to estimate the total excess or the total free space of all bins. In proving an upper bound for algorithm LS we can further assume, without loss of generality, that a bin accepts no more items once it becomes heavy. Otherwise, all bins are heavy and the packing is optimal.

Theorem 2 The competitive ratio of the list scheduling algorithm

R LS (m, B) =    1 + mbmin 4 P m j=1 bj , if m is even, 1 + (m 2 -1)bmin 4m P m j=1 bj , if m is odd.
Proof: We only need to prove that

R LS (m, B) ≤    1 + mbmin 4 P m j=1 bj , if m is even, 1 + (m 2 -1)bmin 4m P m j=1 bj , if m is odd.
By the algorithm LS, we know that

k j=1 r j k ≥ min j=1,•••,k r j ≥ max j=k+1,•••,m s j ≥ m j=k+1 s j m -k . Then (m -k) k j=1 r j ≥ k m j=k+1 s j (3)
From ( 2), we have

k i=j e j ≥ m j=k+1 s j . (4)
We add (mk) k j=1 e j to both sides of the inequality (3) and from (4), we get

(m -k) k j=1 (r j + e j ) ≥ k m j=k+1 s j + (m -k) k j=1 e j ≥ k m j=k+1 s j + (m -k) m j=k+1 s j = m m j=k+1 s j . It means that m j=k+1 s j ≤ (m-k) m k j=1 (r j + e j ).
Note that the competitive ratio

R LS (m, B) ≤ ( n i=1 p i + m j=k+1 s j )/ n i=1 p i . Then R LS (m, B) ≤ 1 + (m -k) k j=1 (r j + e j ) m n i=1 p i ≤ 1 + (m -k) k j=1 (r j + e j ) m m j=1 b j . Since r j + e j ≤ p max ≤ b min , we obtain R LS (m, B) ≤ 1 + (m -k)kb min m m j=1 b j . If m is even, then (m -k)k/m 2 ≤ 1/4. It follows R LS (m, B) ≤ 1 + mb min 4 m j=1 b j . If m is odd, then (m -k)k ≤ 1 4 (m 2 -1). We have R LS (m, B) ≤ 1 + (m 2 -1)b min 4m m j=1 b j . ✷ Corollary 3 R LS (m, B) ≤ R LS (m) = 5 4 , if m is even, 5 4 -1 4m 2 , if m is odd.
Moreover, R LS = 5/4. ✷

Note that R LS (m, B) < R LS (m) if m ≥ 2 and b i = b j for some i, j. It means that the competitive ratio of LS becomes smaller if the bin sizes are unequal. Before closing this section, we consider a different version of list scheduling: assign items to the bin of least load. Denote the algorithm as LS ′ . Consider the following simple instance L for two bins. Let b 1 = 2b 2 and let ε > 0 be a sufficiently small number. The first two items have size of b 2ε, which are followed by an item with size of ε/2. By algorithm LS ′ , after assigning the first two items, each bin has a load of b 2ε. If the 3rd item goes to the first bin B 1 , an item (the last one) with size of b 2 comes, which is assigned to B 2 . If the 3rd item goes to the second bin B 2 , then the 4th item has a size of ε and the 5th item (the last one) has size of b 2 . The 4th is assigned to B 1 while the 5th is assigned to B 2 . In both cases,

LS ′ L (2, B) ≥ b 1 + b 2 + b 2 -ε.
In an optimal packing, we can assign the last item to B 2 and the others to

B 1 . Then OP T L (2, B) = b 1 + b 2 , which shows that R LS ′ (2, B) → 4/3 as ε tends to zero. It implies that R LS ′ ≥ 4/3.
3 The two-and three-bin cases

Assume that b 1 ≥ b 2 ≥ • • • ≥ b m ≥ p max .
In this section we consider the cases that m = 2 and m = 3. Algorithm A m (α): If all bins are heavy, then assign the incoming item a i arbitrarily. If there is a light bin whose excess will be at most α in case of accepting, assign the item a i to such a bin with lowest index; if such a bin does not exist, assign a i to the bin with largest free space.

In this algorithm α is a user-specified parameter. Choosing different parameters results in different algorithms.

Lemma 4 For any parameter α > 0, the competitive ratio of algorithm A 2 (α) is at least

1 + b 2 /(3(b 1 + b 2 )).
Proof: Let N be a sufficiently large integer. If α < b 2 /3, consider an instance L as follows. The first ⌊(b 1 -2b 2 /3)N ⌋ items are small items, each with size 1/N , which are followed by items a 1 , a 2 , a 3 with size of b 2 /3, 2b 2 /3 and 2b 2 /3, respectively. Clearly, A 2 (α) assigns all the small items together with a 1 to bin B 1 , and a 2 to bin B 2 . Thus no matter where a 3 is assigned, A 2 (α) L (2, B) ≥ b 1 +b 2 +b 2 /3-1/N . For an optimal solution, we can assign a 1 and a 2 to B 2 , and the remaining items to

B 1 . Thus OP T L (2, B) = b 1 + b 2 , which follows that A 2 (α) L (2, B)/OP T L (2, B) → 1 + b 2 /(3(b 1 + b 2 )) as N goes to infinity. If α ≥ b 2 /3, consider the following instance L: the first ⌊(b 1 -2b 2 /3)N ⌋ items with size 1/N , are followed by item a 1 with size b 2 . So A 2 (α) L (2, B) ≥ b 1 + b 2 /3 + b 2 -1/N .
In an optimal packing, we assign a 1 to B 2 , and the remaining items to

B 1 . OP T L (2, B) = b 1 + b 2 , which follows A 2 (α) L (2, B)/OP T L (2, B) → 1 + b 2 /(3(b 1 + b 2 )) as N tends to infinity. ✷ By setting α = b 2 /3, we prove that the competitive ratio of A 2 (α) is 1 + b 2 /(3(b 1 + b 2 )). Theorem 5 The competitive ratio of A 2 (α) is 1 + b 2 /(3(b 1 + b 2 )) if α = b 2 /3.
Moreover the overall competitive ratio is 7/6.

Proof: If both bins are light or both are heavy, the packing is optimal. We only need to consider the case that exactly one bin is heavy. From the assumption (2), we have

M 1 + M 2 ≥ b 1 + b 2 , where M i is the load of bin B i , i = 1, 2.
Let α = b 2 /3. Let T be the excess of the heavy bin and let X be the free space of the light bin. If

T ≤ α, then R A2(α) (2, B) ≤ (T + b 1 + b 2 )/(b 1 + b 2 ) ≤ 1 + b 2 /(3(b 1 + b 2 )
). Now assume that T > α. We want to prove X ≤ α.

Case 1. B 2 is light. X = b 2 -M 2 .
Let a n be the last item assigned to B 1 , which makes the excess over α.

B 2 is not empty and before a n is assigned B 1 is light and has an free space at least X. Otherwise, a n should have been assigned to B 2 . It implies that the size of the items in B 2 is larger than X + α, otherwise all the items in B 2 can be assigned to

B 1 . Thus X = b 2 -M 2 < b 2 -(X + α). It follows that X < α. Case 2. B 1 is light. X = b 1 -M 1 .
Before the last item is assigned to B 2 , B 2 is light and has an free space at least X. The total size of items in B 2 before the last item is assigned is at most b 2 -X.

According to the algorithm, b 2 -X + M 1 > b 1 + α. Then b 2 -X > b 1 -M 1 + α which implies that X ≤ α.
In both cases we have

R A2(α) (2, B) ≤ (X + M 1 + M 2 )/(M 1 + M 2 ) ≤ 1 + b 2 /(3(b 1 + b 2 )). It is easy to verify that R A2(α) (2, •) = 7/6. ✷
Since no on-line algorithm can have an overall competitive ratio less than 7/6 for two bins [START_REF] Dell'olmo | Approximation algorithms for partitioning small items in unequal bins to minimize the total size[END_REF], A 2 (α) is an optimal on-line algorithm for m = 2 in terms of the overall competitive ratio, setting α = b 2 /3.

We will show a lower bound for two bins under the assumption [START_REF] Alon | Approximation schemes for scheduling on parallel machines[END_REF]. Let b 1 = kb 2 /3 + x, where 0 ≤ x < b 2 /3 and k ≥ 3 (k is an integer).

Lemma 6 No on-line algorithm can achieve a competitive ratio smaller than

R = 1 + (b 2 /3 -x)/(b 1 + b 2 ), if 0 ≤ x ≤ b 2 /6; 1 + x/(b 1 + b 2 ), if b 2 /6 < x < b 2 /3.
Proof: Let A be any on-line algorithm. Consider the following instance L. The items with size of b 2 /3 come one by one until n 2 = 2 or n 1 = k -1, where n i is the number of items with size of b 2 /3 placed into bin B i by algorithm A for i = 1, 2.

Case 1. n 2 = 0, n 1 = k -1. If 0 ≤ x ≤ b 2 /6, the next two items have size of 2b 2 /3. Thus A L (2, B) ≥ b 1 + b 2 + b 2 /3 -x. If b 2 /6 < x < b 2 /3, the next item has size of x. If x goes to B 1 , two items with size of 2b 2 /3 come. It follows that A L (2, B) ≥ b 1 + b 2 + b 2 /3. If x goes to B 2 , an item with size of b 2 comes. Then A L (2, B) ≥ b 1 + b 2 + x. Case 2. n 2 = 1, n 1 = k -1. The next item has size of b 2 and then A L (2, B) ≥ b 1 + b 2 + b 2 /3. Case 3. n 2 = 2, n 1 = p, where 0 ≤ p < k -1.
Case 1. Only one bin is heavy. If the excess of the heavy bin is at most α, we can get the competitive ratio 1 + b 3 /(2(b 1 + b 2 + b 3 )) immediately. Before the last item of the heavy bin is assigned, all the three bins are light and the heavy bin has the largest free space at the moment.

Subcase 1a B 1 is heavy. Then M 1 > b 1 + α. Note that M 2 + M 3 > b 2 + α. We have R A3(α) (3, B) ≤ (M 1 + b 2 + b 3 )/(M 1 + M 2 + M 3 ) = 1 + (b 2 + b 3 -M 2 -M 3 )/(M 1 + M 2 + M 3 ) ≤ 1 + (b 2 + b 3 -b 2 -α)/(b 1 + b 2 + b 3 ) ≤ 1 + b 3 /(2(b 1 + b 2 + b 3 )) Subcase 1b B 2 is heavy. M 2 > b 2 + b 3 /2 and M 1 + M 3 > b 1 + b 3 /2. R A3(α) (3, B) ≤ (M 2 + b 1 + b 3 )/(M 1 + M 2 + M 3 ) = 1 + (b 1 + b 3 -M 1 -M 3 )/(M 1 + M 2 + M 3 ) ≤ 1 + b 3 /(2(M 1 + M 2 + M 3 )) ≤ 1 + b 3 /(2(b 1 + b 2 + b 3 )) Subcase 1c B 3 is heavy. M 3 > b 3 + b 3 /2. Let X be the total free space of M 1 and M 2 . Then X = b 1 + b 2 -(M 1 + M 2 ). Let Y 3 be the load in B 3 before the last item is assigned. Thus b 3 -Y 3 ≥ b 2 -M 2 , b 3 -Y 3 ≥ b 1 -M 1 .
We have Case 2. Only one bin is light. If the free space X of the light bin is at most α or the total excess of the two heavy bins is at most α, we have the competitive ratio immediately. We only need to consider the case that X > α and the total excess exceeds α. However, we will show that it is impossible. Before considering the following two cases, we assume that M i > 0 for i = 1, 2, 3. Otherwise, the total excess is at most α.

X = b 1 + b 2 -(M 1 + M 2 ) ≤ 2
Subcase 2a B 3 is light. M 3 = b 3 -X < α = b 3 /2. Let Y i be the load of B i immediately before it becomes heavy, for i = 1, 2. Then b i -Y i ≥ X; otherwise the last item, which makes the total excess of B 1 and B 2 over α, would have been assigned to bin B 3 , then any item less than b 3 can be assigned to B 1 or B 2 . Thus all the items in B 3 should have been assigned to B i by the algorithm. It is a contradiction.

Final Remarks. There are many open questions. Although we have proved that the algorithm A 2 (α) is optimal in terms of the overall competitive ratio, it is still open to find a best possible on-line algorithm for two bins in terms of the competitive ratio. It is interesting to design an algorithm with a better competitive ratio than LS algorithm for any number of bins. The problem without the assumption (1) becomes more difficult. We only proved the competitive ratio of LS for the two-bin case. Any improvement on the lower bounds is also of interest.

  m j=1 b j -mb min /2 such that after assigning these items by LS, each bin has free space exactly b min /2. Then m/2 items with size of b min are coming. Clearly, the optimal value is m j=1 b j , while LS generates a total size m j=1 b j +mb min /4. Thus R LS (m, B) ≥ 1+ mbmin 4 P m j=1 bj . If m is odd, the instance is slightly different. A large number of small enough items are coming first. The total size of them is m j=1 b j -(m -1)b min /2, so that after assigning these items each bin has free space exactly m-1 2m b min . Then (m -1)/2 items with size b min are coming. Clearly, the optimal total bin size is m j=1 b j , while LS generates a total bin size of m j=1 b j + (m 2 -1)b min /(4m). Thus R LS (m, B) ≥ 1 + (m 2 -1)bmin 4m P m j=1 bj . The lemma is proved. ✷

(b 3 -Y 3 + M 1 ≥ b 1 + b 3 / 2 , Y 3 + M 2 ≥ b 2 + b 3 / 2 .

 3311323222 Y 3 ). On the other hand,We haveX = b 1 + b 2 -(M 1 + M 2 ) ≤ 2Y 3b 3 . So, X ≤ min{2(b 3 -Y 3 ), 2Y 3b 3 } ≤ b 3 /2. Therefore, R A3(α) (3, B) ≤ (X + M 1 + M 2 + M 3 )/(M 1 + M 2 + M 3 ) ≤ 1 + b 3 /(2(b 1 + b 2 + b 3 )).

Acknowledgements

The authors would like to thank the referees and the Associate Editor for their helpful suggestions.

‡ Research was supported by NSFC(10601048) and National 973 Fundamental Research Project of China(No. 2007CB310900). § Research was supported by NSFC (60573020).

Deshi Ye and Guochuan Zhang

Subcase 3a For the sake of proof, we also consider the case p = k -1. In this case the next item has size of 2b 2 /3 + x, and thus A L (2, B) ≥ b 1 + b 2 + b 2 /3.

Subcase 3b

Subcase 3d

Otherwise, all the s items go to B 1 . The free space of

Then it is reduced to the above three subcases 3a -3c.

Note that in any of the above cases, OP T L (2, B) = b 1 + b 2 . Thus, the lemma is proved. ✷ Lemma 6 shows that R A (2, B) ≥ 1+ b2 6(b1+b2) for any on-line algorithm A. It also shows that algorithm A 2 (α) is optimal for the case that x = 0 (or b 1 = kb 2 /3 for some integer k ≥ 4), by setting α = b 2 /3. Now we consider the three-bin case.

Lemma 7 For any parameter α > 0, the competitive ratio of algorithm A 3 (α) is at least

and a 2 and a 3 to

In an optimal packing, we can assign a 1 and a 3 to B 3 , the first ⌊b 1 N -1⌋ items with size 1/N to B 1 and the remaining items to

as N tends to infinity. ✷

In the following, we prove that the competitive ratio of algorithm A 3 (α) can reach the lower bound

Theorem 8 The competitive ratio of the algorithm

In the packing given by A 3 (α), let M i be the total size of the items assigned to bin B i . If all the bins are heavy or all the bins are light, the algorithm gives an optimal packing. Hence, we only need to consider the following cases.

Deshi Ye and Guochuan Zhang

Subcase 2b B 3 is heavy. Recall that any item size is at most b 3 . There are at least two items in B 3 .

Assume that a k is the last item assigned to B 3 . Those items assigned to B 3 have size at least X > b 3 /2. Thus the idle space of B 3 before a k is assigned is less than X, which means that a k would have not been assigned to B 3 . It is a contradiction.

✷

From Theorems 5 and 8 we realize that the competitive ratio of algorithm A m (α) for unequal bins is better than that for equal bins.

Without the assumption on item sizes

In this section, we will discuss the problem without the assumption (1) for the two-bin case. However, it is reasonable to assume that all items with size at most b 1 .

Lemma 9 Without the assumption (1), no deterministic on-line algorithms can achieve an overall competitive ratio lower than 6/5 for two bins.

Proof: Let b 1 = 3/2 and b 2 = 1. The first item a 1 has size of 1/2. If a 1 is assigned to bin B 2 , two items a 2 , a 3 with size of 1 are coming. If a 1 is assigned to bin B 1 , item a 2 with size of 3/2 is coming. For both cases, the overall competitive ratio is at least 6/5. ✷ Lemma 10 For any on-line algorithm A the competitive ratio Proof: We first show the upper bound. Without loss of generality, we consider the case only one bin is heavy.

The LS algorithm assigns items to the bin with largest free space. Recall that the total size of items is not less than the total size of bins, we get that the free space is at most b 2 . Then, LS L (2, B) ≤

Let X be the free space and T be the excess. We only consider the case that both X and T are greater than b 1 /2. Otherwise, it follows that R LS (2, B) ≤ 1 + b 1 /(2(b 1 + b 2 )). Let p n be the size of the last item assigned to the bin which has an excess over b 1 /2. Recall that all items have size of at most b 1 . Let Y i be the load of bin B i before the last item is assigned. Then

The following simple instance shows that the bound is tight. Consider three items with sizes of min{b In the following, we present an on-line algorithm to improve the upper bound in some cases.

Algorithm A2:

Proof:

Consider the following cases:

Case 1. b 1 ≤ 4b 2 /3. We use A 2 (α), by setting α = b 2 /3. The proof is similar as the one of Theorem 5.

Case 2. 4b 2 /3 < b 1 ≤ 2b 2 . We only need to consider the case that exactly one bin is heavy, the excess of the heavy bin is over b 1b 2 , and the free space of the light bin is larger than b 1b 2 . However, we will show this case is impossible. Before the last item a n , which makes the excess over b 1b 2 , is assigned, if B 2 is empty, then the excess is at most b 1b 2 after assigning a n . Assume that B 2 is not empty before a n is assigned. Note that B 1 has an free space larger than b 1b 2 before a n is assigned. It means that the total size of items in B 2 is more than ✷


Artur Szymański

A Paweł Wojda

Self-complementing permutations of k-uniform hypergraphs

Keywords:

. For any positive integer n we denote by λ(n) the unique integer such that n = 2 λ(n) c, where c is odd. In the paper we prove that a permutation σ of [1, n] with orbits O1, . . . , Om is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l ≥ 0 such that k = a2 l + s, a is odd, 0 ≤ s < 2 l and the following two conditions hold:

(i) n = b2 l+1 + r, r ∈ {0, . . . , 2 l -1 + s}, and (ii)

For k = 2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs.

Introduction

Let V be a set of n elements.

The set of all k-subsets of V is denoted by V k . A k-uniform hypergraph H consists of a vertex-set V (H) and an edge-set E(H) ⊆ V (H) k . Two k-uniform hypergraphs G and H are isomorphic, if there is a bijection σ : V (G) → V (H) such that e ∈ E(G) if and only if {σ(x)|x ∈ e} ∈ E(H). The complement of a kuniform hypergraph H is the hypergraph H such that V (H) = V (H) and the edge set of which consists of all k-subsets of V (H) not in E(H) (in other words E(H) = V (H) k -E). A k-uniform hypergraph H is called self-complementary (s-c for short) if it is isomorphic with its complement H. Isomorphism of a k-uniform self-complementary hypergraph onto its complement is called self-complementing permutation (or s-c permutation).

The 2-uniform self-complementary hypergraphs are exactly self-complementary graphs. This class of graphs has been independently discovered by Ringel and Sachs who proved the following.

Theorem 1 (Ringel (Rin63) and Sachs (Sac62)) Let n be a positive integer. A permutation σ of [1, n] is a self-complementing permutation of a self-complementary graph of order n if and only if all the orbits of σ have their cardinalities congruent to 0 (mod 4) except, possibly, one orbit of cardinality 1.

Observe that by Theorem 1 an s-c graph of order n exists if and only if n ≡ 0 or n ≡ 1 (mod 4) or, equivalently, whenever n 2 is even. In (SW) we prove that a similar result is true for k-uniform hypergraphs.

Theorem 2 ((SW)) Let k and n be positive integers, k ≤ n. A k-uniform self-complementary hypergraph of order n exists if and only if n k is even. A simple criterion for evenness of n k has been given in (Gla99) (and then rediscovered in (KHRM58)). Theorem 3 ((Gla99; KHRM58)) Let k and n be positive integers, k = +∞ i=0 c i 2 i and n = +∞ i=0 d i 2 i , where c i , d i ∈ {0, 1} for every i. n k is even if and only if there is i 0 such that c i0 = 1 and d i0 = 0. Theorem 3 asserts that n k is even if and only if k has 1 in a certain binary place while n has 0 in the corresponding binary place. For example, 27 13 is even since 13 = 1

• 2 3 + 1 • 2 2 + 0 • 2 1 + 1 • 2 0 and 27 = 1 • 2 4 + 1 • 2 3 + 0 • 2 2 + 1 • 2 1 + 1 • 2 0 (so we have c 2 = 1 and d 2 = 0).
Except for Theorem 1 which is a characterization of the self-complementing permutations for graphs, there are already two published results characterizing the permutations of k-uniform s-c hypergraphs for k > 2. Namely, Kocay in (Koc92) (see also [START_REF] Palmer | On the number of n-plexes[END_REF]) and Szymański in (Szy05) have characterized the s-c permutations of s-c k-uniform hypergraphs for, respectively, k = 3 and k = 4. This work is a continuation of the work of (SW) and [START_REF] Wojda | Self-complementary hypergraphs[END_REF]. We generalize all the results mentioned above by giving a characterization of the s-c permutations of k-uniform hypergraphs for any integers k and n.

Result

Any positive integer n may be writen in the form n = 2 l c, where c is an odd integer. Moreover, l and c are uniquely determined. We write then λ(n) = l. Note that in the binary expansion of n, λ(n) is the index of the first 1-bit. For any set A we shall write λ(A) in place of λ(|A|), for short.

In the proof of our main result we shall need the following lemma proved in (Woj06).

Lemma 1 Let k, m and n be positive integers, and let σ :

V → V be a permutation of a set V , |V | = n, with orbits O 1 , . . . , O m . σ is a self-complementing permutation of a self-complementary k-uniform
hypergraph, if and only if, for every p ∈ {1, . . . , k} and for every decomposition

k = k 1 + . . . + k p of k (k j > 0 for j = 1, . . . ,

p), and for every subsequence of orbits

O i1 , . . . , O ip such that k j ≤ |O ij | for j = 1, . . . , p, there is a subscript j 0 ∈ {1, . . . , p} such that λ(k j0 ) < λ(O ij 0 )
Given any integer l ≥ 0. If the binary expansion of k is 1-bit in position l, then k can be written in the form k = a l 2 l + s l , where a l is odd and 0 ≤ s l < 2 l . Theorem 4 Let k and n be integers, k ≤ n. A permutation σ of [1, n] with orbits O 1 , . . . , O m is a selfcomplementing permutation of a k-uniform hypergraph of order n if and only if there is a nonnegative integer l such that k = a l 2 l + s l , where a l is odd and 0 ≤ s l < 2 l , and the following two conditions hold:

(i) n = b l 2 l+1 + r l , r l ∈ {0, . . . , 2 l -1 + s l }, and (ii) i:λ(Oi)≤l |O i | ≤ r l .
Proof:

Sufficiency. By contradiction. Let n, k, l, a l , b l , s l and r l be integers verifying the conditions of the theorem, let σ be a permutation of [1, n] with orbits O 1 , . . . , O m verifying (ii), and let us suppose that σ is not a s-c permutation of any k-uniform s-c hypergraph of order n. Then, by Lemma 1, there is a

decomposition of k = k 1 + • • • + k t and a subsequence of orbits O i1 , . . . , O it such that 0 < k j ≤ |O ij | (1) and λ(k j ) ≥ λ(O ij ) (2)
for j = 1, . . . , t. Since a l is odd, we have k ≡ 2 l + s l (mod 2 l+1 ). By (2), j: λ(Oi j )>l k j ≡ 0 (mod 2 l+1 ). Therefore

k = t j=1 k j = j: λ(Oi j )>l k j + j: λ(Oi j )≤l k j ≡ j: λ(Oi j )≤l k j (mod 2 l+1 )
Hence, and by (1), (i) and (ii) we have j:λ(Oi j )≤l k j ≤ j:λ(Oi j )≤l |O ij | < 2 l+1 , and therefore

2 l + s l = j: λ(Oi j )≤l k j ≤ j: λ(Oi j )≤l |O ij | ≤ r l < 2 l + s l a contradiction.
Necessity. Let 1 ≤ k ≤ n and let σ be a permutation of the set [1, n] with orbits O 1 , . . . , O m . Let us suppose that for every integer l such that k = a l 2 l + s l , where a l is odd positive integer, 0 ≤ s l < 2 l , and n = b l 2 l+1 + r l , 0 ≤ r l < 2 l+1 we have either

r l ∈ {2 l + s l , . . . , 2 l+1 -1} or r l ∈ {0, . . . , 2 l -1 + s l } and i: λ(Oi)≤l |O i | > r l
We shall prove that σ is not a s-c permutation of any s-c k-uniform hypergraph of order n. For this purpose we shall give two claims.

Claim 1 For every nonnegative integer l such that k = a l 2 l + s l , where a l is odd and 0 ≤ s l < 2 l , we have i: λ(Oi)≤l

|O i | ≥ 2 l + s l
Proof of Claim 1. Let us write i:λ(Oi)≤l |O i | and i:λ(Oi)>l |O i | in their binary forms:

i:λ(Oi)≤l |O i | = ∞ j=0 e j 2 j i:λ(Oi)>l |O i | = ∞ j=0 f j 2 j
where e j , f j ∈ {0, 1} for every j. Observe that f j = 0 for j = 0, . . . , l and therefore

l j=0 e j 2 j = r l (3)
We shall consider two cases.

Case 1. r l ∈ {0, . . . , 2 l + s l -1} and i:λ(Oi)≤l |O i | > r l . We have n ≥ 2 l+1 (otherwise

r l = n = i:λ(Oi)≤l |O i |). Since
∞ j=0 e j 2 j > r l , and by (3), we obtain

∞ j=0 e j 2 j ≥ 2 l+1 > 2 l + s l .
Case 2. r l ∈ {2 l + s l , . . , 2 l+1 -1}.

We have i:λ(Oi)≤l |O i | = ∞ j=0 e j 2 j ≥ l j=0 e j 2 j = r l ≥ 2 l + s l , and the claim is proved. ✷ Claim 2 Let α 1 , . . . , α q and λ 1 , . . . , λ q be integers such that 0 < α i , 0 ≤ λ i ≤ λ(α i ) and λ i ≤ l for i = 1, . . . , q and q i=1 α i ≥ 2 l . Then there are β 1 , . . . , β q such that for every i = 1, . . . , q 0 ≤ β i ≤ α i (4) and either

β i = 0 or λ(β i ) ≥ λ i (5) and q i=1 β i = 2 l (6)
Proof of Claim 2. The existence of β 1 , . . . , β q verifying (4)-(5) and q i=1 β i ≤ 2 l is very easy. Indeed, it is immediate that β 1 = 2 λ1 , β 2 = . . . β q = 0 is a sequence with the desired properties. So let us suppose that β 1 , . . . , β q is a sequence verifying (4)-(5) and

q i=1 β i ≤ 2 l such that q i=1 β i is maximal. If q i=1 β i = 2 l
then the proof is complete. So let us suppose that q i=1 β i < 2 l . Then there is i 0 ∈ {1, . . . , q} such that β i0 < α i0 . Observe that β i0 + 2 λi 0 ≤ α i0 . The sequence β 1 , . . . , β q defined by β i0 = β i0 + 2 λi 0 and β i = β i for i = i 0 also verifies (4)-(5) and q i=1 β i ≤ 2 l , which contradicts the maximality of the sum q i=1 β i , and the claim is proved. ✷

We shall use our claims to construct a decomposition of k in the form k = k 1 + . . . + k m such that

(1) k 1 , . . . , k m are nonnegative integers,

(2) k i ≤ |O i | for i = 1, . . . , m, and

(3) λ(k i ) ≥ λ(O i ) whenever k i > 0
By Lemma 1, this will imply that σ is not a s-c permutation of any k-uniform s-c hypergraph. Let us write k in its binary form:

k = 2 lt + 2 lt-1 + . . . + 2 l1 + 2 l0
where l 0 < l 1 < . . . < l t .

By Claim 1, i:λ(Oi)≤l0 |O i | ≥ 2 l0 . Hence, and by Claim 2, there are nonnegative integers k

(0) 1 , k (0)
2 , . . . , k

(0) m such that k (0) i = 0 for i such that λ(O i ) > l 0 and k (0) i ≤ |O i | for i = 1, . . . , m λ(k (0) i ) ≥ λ(O i ) whenever k (0) i > 0 and m i=1 k (0) i = 2 l0
Note that, for i = 1, . . . , m, we have λ

(|O i | -k (0) i ) ≥ λ(O i ).
Let us suppose that we have already constructed k

(j) 1 , . . . , k (j) m , (j ≤ t), such that k (j) i = 0 for i such that λ(0 i ) > l i and k (j) i ≤ |O i | for i = 1, . . . , m λ(k (j) i ) ≥ λ(O i ) whenever k (j) i > 0 m i=0 k (j) i = 2 lj + 2 lj-1 + • • • + 2 l0 and λ(|O i | -k (j) i ) ≥ λ(O i ) If j = t,
then we have already found a desired decomposition of k. If j < t, then, by Claim 1, we have

i:λ(Oi)≤lj+1 (|O i | -k (j) i ) ≥ 2 lj+1 . λ(|O i | -k (j) i ) ≥ λ(O i ) for every i ∈ {1, . . . , m} such that |O i | -k (j) i > 0.
Hence, and by Claim 2, there are β 1 , . . . , β m such that β i = 0 for i such that λ(O i ) > l j+1 and

0 ≤ β i ≤ |O i | -k (j) i for i = 1, . . . , m λ(O i ) ≤ λ(β i ) for i = 1, . . . , m whenever β i = 0 m i=1 β i = 2 lj+1
Thus we may define for every i = 1, . . . , m k

(j+1) i = k (j) i + β i to obtain the sequence (k (j+1) 1 , . . . , k (j+1) m ) verifying for every i ∈ {1, . . . , m} k (j+1) i = 0 for i such that λ(O i ) > l j+1 k (j+1) i ≤ |O i | λ(k (j+1) i ) ≥ λ(O i ) whenever k (j+1) i > 0 and m i=1 k (j+1) i = 2 lj+1 + 2 lj + • • • + 2 l0 It is clear that k = m i=1 k (t)
i and the proof of Theorem 4 is complete. ✷ Theorem 4 implies very easily the following theorem first proved by Kocay.

Corollary 1 (Kocay (Koc92)) σ is a self-complementing permutation of a self-complementary 3-uniform hypergraph if and only if either all the orbits of σ have even cardinalities, or else, it has 1 or 2 fixed points and the all remaining orbits of σ have their cardinalities being multiples of 4.

For k = 2 l Theorem 4 may be written as follows.

Corollary 2 Let l and n be nonnegative integers, 2 l < n, and let 0 ≤ r < 2 l+1 be such that n ≡ r (mod 2 l+1 Theorem 2 for l = 1 (i.e. for graphs) is exactly Theorem 1, and for l = 2 the following theorem proved by Szymański in (Szy05).

Corollary 3 A permutation σ is self-complementing permutation of a 4-uniform hypergraph of order n if and only if n ≡ r( mod 8) with r = 0, 1, 2 or 3, and the sum of the cardinalities of orbits which are not multiples of 8 is at most 3.

1365-8050 c 2009 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Acknowledgements

The research was partially supported by AGH local grant No 11 420 04.


Elmar Teufl

Stephan Wagner

Asymptotic enumeration on self-similar graphs with two boundary vertices

Keywords: spanning forests, connected subgraphs, self-similar graphs, asymptotic enumeration

We study two graph parameters, namely the number of spanning forests and the number of connected subgraphs, for self-similar graphs with exactly two boundary vertices. In both cases, we determine the general behavior for these and related auxiliary quantities by means of polynomial recurrences and a careful asymptotic analysis. It turns out that the so-called resistance scaling factor of a graph plays an essential role in both instances, a phenomenon that was previously observed for the number of spanning trees. Several explicit examples show that our findings are likely to hold in an even more general setting.

Introduction

In several recent papers [START_REF] Chang | Spanning forests on the Sierpinski gasket[END_REF][START_REF] Chang | Dimer coverings on the sierpinski gasket with possible vacancies on the outmost vertices[END_REF][START_REF] Chang | Dimer-monomer model on the Sierpinski gasket[END_REF][START_REF] Chang | Spanning trees on the Sierpinski gasket[END_REF][START_REF] Teufl | The number of spanning trees of finite sierpinski graphs[END_REF][START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF][START_REF] Teufl | The number of spanning trees in self-similar graphs[END_REF] the enumeration of various graph-theoretical objects on selfsimilar graphs was studied, including, among others, the number of spanning trees and forests, matchings, and connected subgraphs. Some of these counting problems have a background in theoretical physics, as also explained in [START_REF] Chang | Spanning forests on the Sierpinski gasket[END_REF]: the number of spanning forests of a graph can be seen as a special value of the Tutte polynomial T (G, x, y) of a graph (namely, the value for x = 2, y = 1). On the other hand, it also occurs as a special q → 0 limit of the partition function of the q-state Potts model, see for example [START_REF] Sokal | The multivariate Tutte polynomial (alias Potts model) for graphs and matroids[END_REF]. While this and related problems are well-studied for lattices, [START_REF] Chang | Spanning forests on the Sierpinski gasket[END_REF] is the first work where fractal-type structures are investigated. There, the authors were concerned with the asymptotic behavior of the number of spanning forests |SF(G n )| for an increasing family of graphs G n , and in particular with the associated asymptotic growth constant

lim n→∞ log|SF(G n )| |G n | ,
which is a quantity of physical interest. The authors of [START_REF] Chang | Spanning forests on the Sierpinski gasket[END_REF] were able to calculate numerical values for the growth constants of Sierpiński graphs with small dimension. In the present paper, we study the problem in more generality, but we have to restrict ourselves to a special type of construction that will be explained in the following section. The other counting problem that we address is the enumeration of connected subgraphs. We will see that similar techniques can be used for both problems and that the so-called resistance scaling factor of a graph with respect to two of its vertices plays a crucial role in both instances. This phenomenon also occurs in the enumeration of spanning trees, which was exhibited in [START_REF] Teufl | The number of spanning trees in self-similar graphs[END_REF].

Let us demonstrate this in the case of the aforementioned sequence of finite Sierpiński graphs which are depicted on Figure 1. The number of spanning trees in the level-n graph X n is described by a system

X 0 X 1 X 2 X 3
Fig. 1: Finite Sierpiński graphs X0, X1, X2, X3.

of polynomial recurrence equations:

a 1,n+1 = 6a 2 1
,n a 2,n , a 2,n+1 = 7a 1,n a 2 2,n + a 2 1,n a 3,n , a 3,n+1 = 14a 3 2,n + 12a 1,n a 2,n a 3,n , where a k,n is the number of spanning forests in X n with k components each of which contains exactly one "boundary vertex" of X n , see [START_REF] Chang | Spanning trees on the Sierpinski gasket[END_REF][START_REF] Teufl | The number of spanning trees of finite sierpinski graphs[END_REF]. From this it is not too difficult to derive an explicit formula for the number τ (X n ) of spanning trees in X n : .

τ (X n ) =
In [START_REF] Teufl | The number of spanning trees in self-similar graphs[END_REF] it was proved that the number of spanning trees can be computed explicitly for a large class of self-similar graphs with a high degree of symmetry. Similarly, the number of connected subgraphs or connected subsets can be described by a system of seven polynomial recurrence equations: We refer to [START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF] for details, including a precise definition of the quantities involved. It turns out that the asymptotically significant terms are those which are written in bold. We point out that this part of the system agrees with the system for spanning trees. Hence the number of connected subgraphs (or subsets) is asymptotically given by c • 5 3

-n 2 • β 3 n
for constants c = 6.163424 . . . and β = 2.3032106556 . . . In [START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF] it was conjectured that a similar formula holds for other self-similar graphs as well, which we will verify for a very specific class in this paper, namely self-similar graphs with two "boundary" vertices. We obtain precise asymptotic information for the number of spanning forests and the same for the number of connected subgraphs under mild conditions on the geometry of X n .

2 Setting and statement of results Using G as model, construct a sequence X 0 , X 1 , X 2 , . . . of self-similar (multi-)graphs as follows:

Let G = (V G,
• The initial graph X 0 is given together with two distinguished vertices v 0 , w 0 and is assumed to be finite.

• The graph X n+1 is obtained by replacing every edge of G by an isomorphic copy of X n , where v n , w n are used for linkage. There are two possibilities for each replacement. Fix one of these once and forever. The distinguished vertices v n+1 , w n+1 of X n+1 emerge from v, w in G.

For an edge e ∈ EG we write h v (e) ∈ V G for the endpoint of e which is merged with v n during the construction and call the vertex h v (e) the v-end of the edge e. We define the w-end h w (e) of e analogously. Thus, in every stage of the construction an edge e in G is replaced by X n , so that the vertex h v (e) is merged with v n and h w (e) is merged with w n .

We always assume that X 0 and G are connected, so that the graphs X n are connected, too. By considering edges of G as resistors with unit resistance we may regard G as a electrical network. With respect to the boundary v, w (source, sink) the network G is electrically equivalent to a single resistor with some resistance ρ, which is called the resistance scaling factor of G with respect to v and w, see for example [START_REF] Barlow | Diffusions on fractals[END_REF][START_REF] Kigami | Analysis on fractals[END_REF][START_REF] Metz | The short-cut test[END_REF][START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF]

. Notice that ρ ≤ 1 if d = d G (v, w) = 1. v 0 w 0 X 0 v 1 w 1 X 1 v 2 w 2 X 2 v 3 w 3 X 3
Fig. 2: The Austria graphs X0,X1,X2, and X3.

Example. The "Austria" graphs X 0 , X 1 , . . . were first studied in [START_REF] Krön | Growth of self-similar graphs[END_REF] with respect to volume growth and later also in [START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF] in the context of combinatorial enumeration (their shape resembles a map of Austria, see Figure 2). Since the initial graph is given by X 0 = K 2 , the model graph G equals X 1 . The orientation of the replacement can be seen in X 2 and X 3 in Example. In [START_REF] Malozemov | The difference Laplacian ∆ on the modified Koch curve[END_REF] spectral properties of the modified Koch curve were studied. It is a minor but interesting variation of the fractal Koch curve. The first few graphs in the associated graph sequence are depicted in Figure 3. Since X 0 = K 2 the model graph G is again X 1 . Due to symmetry there are no choices during the replacement.

X 0 X 1 X 2 X 3
Fig. 3: The finite modified Koch graphs X0,X1,X2, and X3.

Theorem 1. Assume that s > 1, then two different cases concerning the asymptotics of spanning forests in X n may occur:

(I) The number of spanning forests in X n which do not connect v n and w n is given by

C 1 β s n 1 (1 + o(1)),
whereas the number of spanning forests in X n connecting v n and w n satisfies

C 2 β s n 1 β -d n 2 (1 + o(1)
)

for certain constants β 1 > 1, β 2 ≥ 1, C 1 > 0, C 2 > 0.
(II) The number of spanning forests in X n which do not connect v n and w n is given by

C 3 ρ δ-1 s-1 n β s n 3 (1 + o(1)),
whereas the number of spanning forests in X n connecting v n and w n satisfies

C 4 ρ -s-δ s-1 n β s n 3 (1 + o(1))
for certain constants

β 3 > 1, C 3 > 0, C 4 > 0.
Expressions for these constants are provided in the proof. Depending on the values of ρ and d, we get the following description:

• If ρ ≥ 1 then Case I occurs.

• If ρ < 1 and d = 1 then Case II occurs.

• If ρ < 1 and d > 1 then both cases are possible depending on the initial graph X 0 . Here it may happen that the term β s n 1 (1 + o(1)) of Case I must be replaced by the weaker term β

s n +O(1) 1
(this situation is described in the proof). The proof and an example for the case ρ < 1 and d > 1 are provided in Section 3.

Theorem 2. Assume that s > 1, that v, w are leaves (i.e. vertices with degree 1) in G, that v 0 , w 0 are leaves in X 0 , and that G is not a path, then there are constants β 4 > 1 and C 5,0 > 0, C 5,1 > 0, so that the number of non-empty connected subgraphs of X n is given by

C 5,k ρ -s-δ s-1 n β s n 4 1 + O 2 -n ,
where k ∈ {0, 1} is the remainder of the division of n by 2.

The assumption that v, w and v 0 , w 0 are leaves assures that the maximal degree X n is uniformly bounded. Together with s > 1 it implies further that ρ ≥ 2. In the case that G is a path it is easy to derive an exact formula for the number of non-empty connected subgraphs of X n . Theorem 2 is proved in Section 4.

Spanning forests

This section is devoted to the proof of Theorem 1. Thus we always assume that s > 1. Let SF(G) be the set of all spanning forests in G. Introduce auxiliary sets: SF • (G), SF • (G). The first set contains all spanning forests of G connecting v and w, whereas the latter denotes the set of all spanning forests of G, where v and w are not connected by the forest. Denote by SF m (G) the set of all spanning forests of G with m edges and combine these notations in the obvious way, e.g. SF • m (G). Finally, we use

SF(X n ), SF • (X n ), SF m (X n ) analogously.
We are interested in the number |SF(X n )| of spanning forests in X n . Obviously, the disjoint union

SF • (X n ) ⊎ SF • (X n ) = SF(X n ) is the set of all spanning forests of X n . For simplicity, set a n = |SF • (X n )|, b n = |SF • (X n )|.
Notice that the sequence b n tends to infinity since s > 1. Since every spanning forest of X n+1 can be decomposed into spanning forests on each copy of X n , we obtain the recursions

a n+1 = F ∈SF • (G) a |EF | n b |EG|-|EF | n = m |SF • m (G)| a m n b s-m n , b n+1 = F ∈SF • (G) a |EF | n b |EG|-|EF | n = m |SF • m (G)| a m n b s-m n .
Using the polynomials p, q, r given by

p(x) = x d q(x) = δ m=d |SF • m (G)| x m = |SF • d (G)|x d + • • • + |SF • δ (G)|x δ , r(x) = δ-1 m=0 |SF • m (G)| x m = 1 + • • • + |SF • δ-1 (G)|x δ-1 ,
the previous recursion can be reformulated as

a n+1 = b s n p(x n ) = b s n x d n q(x n ) and b n+1 = b s n r(x n ), (1)
yielding a recursion for the quotient x n = an bn :

x n+1 = f (x n ) = x d n g(x n ).
Here the rational functions f and g are given by

f (x) = p(x) r(x) and g(x) = q(x) r(x) ,
respectively. The degrees of p and r are given by deg(p) = δ and deg(r

) = δ-1 (recall that δ = |V G|-1). It is easy to see that SF • δ (G) is the set of spanning trees in G and SF • δ-1 (G)
is the set of spanning forests in G with two components each of which contains exactly one distinguished vertex. In Bollobas's book [START_REF] Bollobás | Modern graph theory[END_REF] such spanning forests are called thickets. Note that asymptotic information about the number of spanning forests in X n is closely related to the dynamical behavior of f . This idea was already used in the work [START_REF] Chang | Spanning forests on the Sierpinski gasket[END_REF].

Lemma 3. Let us note two basic inequalities for |SF

• m-1 (G)| and |SF • m (G)|: • We have |SF • m-1 (G)| ≥ ρ |SF • m (G)|. • Assume that d = d G (v, w) = 1, then |SF • m-1 (G)| ≤ |SF • m (G)|. Proof.
In order to prove the first part of the lemma, we introduce SF ⊗ (G) to be the set of all spanning forests in SF • (G), where v and w can be connected by one additional edge, and let

B ⊆ V G be a vertex subset with v, w ∈ B, so that the induced subgraph G[B] is connected. Then there is a relation between the number τ (G[B]) of spanning trees in G[B] and the number θ(G[B]) of thickets in G[B] with respect to v, w: θ(G[B]) = ρ(G[B]) τ (G[B]),
where ρ(G[B]) is the resistance scaling factor of G[B] with respect to v, w, see [START_REF] Teufl | Enumeration problems for classes of self-similar graphs[END_REF]; in fact this formula is a consequence of Kirchhoff's famous theorem on electrical currents and spanning trees, see [START_REF] Kirchhoff | Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird[END_REF] or [START_REF] Bollobás | Modern graph theory[END_REF].

Because of Rayleigh's Monotonicity Law for electrical networks (see for example

|SF ⊗ m-1 (G, B)| |SF • m (G, B)| = θ(G[B]) τ (G[B]) = ρ(G[B]) ≥ ρ(G) = ρ holds. A simple decomposition yields |SF • m-1 (G)| ≥ |SF ⊗ m-1 (G)| = B |SF ⊗ m-1 (G, B)| ≥ B ρ |SF • m (G, B)| = ρ |SF • m (G)|,
where the sums are taken over all vertex subsets B ⊆ V G with v, w ∈ B, so that the induced graph G[B] is connected.

For the second statement of the lemma, note that a spanning forest in SF • m-1 (G) must not contain an edge connecting v and w. Adding such an edge to a spanning forest in SF • m-1 (G) yields a forest in SF • m (G), proving the inequality.

Proposition 4. The asymptotic behavior of f at 0 is given by f (x) = O(x d ), whereas the expansion at ∞ is given by f

(x) = ρ -1 x -c + O(x -1
). Here c ≥ 0 is some constant, which is positive, unless all simple paths (i.e. paths which do not visit vertices several times) connecting v and w have length 1. In this case the function f is given by f (x) = ρ -1 x.

Proof. Both asymptotic expansions follow from the definitions of f . The constant c is given by

c = |SF • δ (G)| • |SF • δ-2 (G)| -|SF • δ-1 (G)| • |SF • δ-1 (G)| |SF • δ-1 (G)| 2
This constant is positive if and only if

ρ = |SF • δ-1 (G)| |SF • δ (G)| < |SF • δ-2 (G)| |SF • δ-1 (G)| . A close inspection of the proof of Lemma 3 shows that |SF • δ-2 (G)| > ρ |SF • δ-1 (G)
| holds, unless all simple paths between v and w have length 1.

The last part of the statement follows from the fact that

|SF • m-1 (G)| = ρ|SF • m (G)| holds, since every forest in SF • m-1 (G) corresponds to exactly ρ -1 ∈ N forests in SF • m (G) in this case.
Corollary 5. The function f satisfies f (x) ≤ ρ -1 x and thus x n ≤ ρ -n x 0 . If not all simple paths connecting v and w have length 1, then f (x) < ρ -1 x for x > 0.

If there is an edge connecting v and w, then f (x) ≥ x. Furthermore, if this edge is not a bridge, then f (x) > x for x > 0, whence x n → ∞ for n → ∞.

Proof. The first statement follows easily from Lemma 3:

x r(x) = m |SF • m-1 (G)|x m ≥ ρ m |SF • m (G)|x m = ρ p(x)
The improved inequality follows from the proof of Lemma 3.

In order to prove the second part, assume that v and w are connected by an edge. Then a similar computation as before yields f (x) ≥ x. If the edge connecting v and w is not a bridge, then

|SF • m-1 (G)| < |SF • m (G)| for some m. Hence f (x) > x for x > 0 in this case.
Lemma 6. Assume that x n is bounded from above. Then there is a constant

β 1 > 1, so that b n = β s n +O(1) 1
. If x n converges, then the error term can be improved:

b n = C 1 β s n 1 (1 + o(1))
for some constant C 1 > 0.

Proof. Using Equation ( 1) we obtain

log b n = s log b n-1 + log r(x n-1 ) = s n log b 0 + n-1 k=0 s -k-1 log r(x k )
by iteration. Define the constant K 1 by

K 1 = log b 0 + ∞ k=0 s -k-1 log r(x k )
(the sum converges due to the boundedness of x n and r(x) ≥ 1 for x ≥ 0). This further implies

log b n = K 1 s n + O(1) and b n = β s n +O(1) 1
,

where β 1 = exp(K 1 ). Suppose that x n → x ∞ holds, then the second part follows from

log b n = s n K 1 - ∞ k=n s -k-1 log r(x k ) = s n K 1 - ∞ k=n s -k-1 log r(x ∞ ) + O ∞ k=n s -k-1 (x k -x ∞ ) = s n K 1 - s -n log r(x ∞ ) s -1 + o(s -n ) = K 1 s n -1 s-1 log r(x ∞ ) + o(1).
Lemma 7. Assume that x n is bounded from above and that d > 1. Then there is a constant

β 2 ≥ 1, so that x n = β -d n +O(1) 2
. If x n converges, then the error term can be improved:

x n = C x β -d n 2 (1 + o(1))
for some constant C x > 0.

Proof. Since the sequence x n is bounded from above, there is a constant c so that x n ∈ [0, c]. For convenience set y n = bn an . Then y n+1 = y d n g(x n ) -1 and

log y n = d log y n-1 -log g(x n-1 ) = d n log y 0 - n-1 k=0 d -k-1 log g(x k ) . Now define K 2 by K 2 = log y 0 - ∞ k=0 d -k-1 log g(x k ).
The sum involved in the definition of K 2 converges, since x n ∈ [0, c] and g is bounded on [0, c] by positive constants. This yields

log y n = K 2 d n + O(1) and x n = β -d n +O(1) 2
, where β 2 = exp(K 2 ). Since x n is bounded, it follows that β 2 ≥ 1. The improvement of the error term is obtained in the same way as in the proof of Lemma 6:

log y n = K 2 d n + 1 d-1 log g(x ∞ ) + o(1)
, where x ∞ denotes the limit of x n .

Lemma 8. Assume that ρ < 1 and that x n is not bounded from above, then there are constants

β 3 > 1, C 3 > 0, C 4 > 0, so that a n = |SF • (X n )| = C 3 ρ -s-δ s-1 n β s n 3 (1 + O(ρ n )), b n = |SF • (X n )| = C 4 ρ δ-1 s-1 n β s n 3 (1 + O(ρ n )).
Proof. Using Proposition 4, it is easy to see that x n tends exponentially to ∞. Furthermore, it follows from Equation ( 1), that the quotient y n = bn an satisfies

y n+1 = y n r(y n ) q(y n ) ,
where q and r are the reversed polynomials of q and r, respectively. Since

r(0) q(0) = |SF • δ-1 (G)| |SF • δ (G)| = ρ, the product P = ∞ k=0 r(y k ) ρ q(y k )
converges due to the exponential decay of y n . This implies that y n = P ρ n y 0 (1+ε n ), where ε n = O(ρ n ).

Using Equation (1) we get a n+1 = a s n y s-δ n q(y n ). Define ε ′ n by the equation

q(y n )(1 + ε n ) s-δ = |SF • δ (G)|(1 + ε ′ n ). Note that ε ′ n = O(ρ n ). Altogether we obtain a n+1 = a s n ρ n(s-δ) C(1 + ε ′ n ), where the constant C is given by C = (P y 0 ) s-δ |SF • δ (G)|. This implies log a n = s n log a 0 + n-1 k=0 s -k-1 k(s -δ) log ρ + log C + log(1 + ε ′ k ) .
Now define the constant K 3 by the sum

K 3 = log a 0 + ∞ k=0 s -k-1 k(s -δ) log ρ + log C + log(1 + ε ′ k ) .
It follows that

log a n = s n K 3 - ∞ k=n s -k-1 k(s -δ) log ρ + log C - ∞ k=n s -k-1 log(1 + ε ′ k ) = K 3 s n - n(s -δ) log ρ s -1 - log C s -1 - (s -δ) log ρ (s -1) 2 + O(ρ n ),
and

log b n = log a n + log y n = K 3 s n + n(δ -1) log ρ s -1 + log(P y 0 ) - log C s -1 - (s -δ) log ρ (s -1) 2 + O(ρ n )
proving the statement. Now we are prepared to prove Theorem 1:

Proof of Theorem 1. We distinguish several cases:

(A) Assume that ρ ≥ 1. Then x n ≤ ρ -n x 0 by Corollary 5.

• ρ > 1, d > 1: Since ρ > 1, the sequence x n decays exponentially to 0. Hence Lemma 6 and Lemma 7 imply asymptotic expansions of a n and b n with improved error terms. Note that r(0) = 1 and q(0) (B) Assume that ρ < 1 and d = 1. Then Corollary 5 yields f (x) > x for x > 0, so that x n tends to ∞.

= |SF • d (G)| ≥ 1. • ρ = 1, d > 1:
In this case Lemma 8 implies the desired asymptotic expansions of a n and b n .

(C) Finally, assume that ρ < 1 and d > 1. The behavior of x n depends on the initial value x 0 . Due to Proposition 4 both 0 and ∞ are attracting fixed points of f . Thus we have to distinguish further:

• If x n → 0, then once again asymptotic expansions of a n and b n in strong forms are obtained from Lemma 6 and Lemma 7. • If x n → ∞, then asymptotic expansions of a n and b n are implied by Lemma 8.

• If x n is not caught by the fixpoints 0 or ∞, then x n is bounded by positive constants. This is the only case where we only obtain weak forms of asymptotic expansions for a n and b n by Lemma 6 and Lemma 7 in general. If x n converges in this case, then the error terms improve to the strong forms.

v w G X 0 v 0 w 0 X ′ 0 v ′ 0 w ′ 0 X ′′ 0 v ′′ 0 w ′′ 0
Fig. 4: A model graph G and three initial graphs X0, X ′ 0 , X ′′ 0 .

Example. Consider the model graph G and the initial graphs X 0 , X ′ 0 and X ′′ 0 given in Figure 4. The evolution of the sequence X n is shown in Figure 5. In this case s = 6, d = 2, δ = 4, and ρ = 2 3 . Furthermore, it is easy to compute the polynomials p and r: p(x) = 3x 2 + 12x 3 + 12x 4 and r(x) = 1 + 6x + 12x 2 + 8x 3 .

The rational function f : x → p(x) r(x) is strictly monotone and convex on [0, ∞). Hence x = 1 is the only fixpoint in (0, ∞) and this fixpoint is repelling. Finally, it is easy to compute that the ratio x 0 is given by

x 0 =      1 if we take the initial graph X 0 , 1 3
if we take the initial graph X ′ 0 , 2 if we take the initial graph X ′′ 0 .

Thus, depending on the initial graph, we obtain different types of asymptotic expansion for the number of spanning forests. Especially, these expansions are given as follows: In the first case

a n = b n = 3 3/5(6 n -1) ≈ 0.51728185 • 1.93318204 6 n ,
in the second case (note that x ∞ = 0) We conjecture that the function f is always strictly monotone and convex in [0, ∞). As a consequence f has at most one fixpoint in (0, ∞), which is then repelling, so that the sequence x n always converges improving the error term always to o(1).

a n ≈

Connected subgraphs

Denote by SG(G) the set of all non-empty (not necessarily induced) subgraphs of G and define the following subsets of SG(G): For ν ∈ {0, v, w, 2} let SG ν (G) be the set of connected subgraphs in SG(G) which contain

v 0 w 0 X 0 v 1 w 1 X 1 v 2 w 2 X 2
Fig. 5: The graphs X0, X1, X2.

• no distinguished vertices, if ν = 0,

• the vertex v but not w, if ν = v,
• the vertex w but not v, if ν = w,

• both distinguished vertices, if ν = 2.

Finally let SG x (G) be the set of all subgraphs with two connected components each of which contains one distinguished vertex. For a subgraph H of G let us define

• e 2 (H) to be the number of edges in EH,

• e v (H) to be the number of edges connecting vertices in V H and V G \ V H, whose v-end lies in V H.

• e w (H) to be the number of edges connecting V H and V G \ V H, whose w-end lies in V H.

• e x (H) to be the number of edges in G connecting vertices in V H which are not in EH.

For the sake of notation set a ν,n = |SG ν (X n )| for ν ∈ {0, v, w, 2, x}, where v and w are interpreted as v n and w n in X n . Obviously, a ν,n ≥ 1 for ν ∈ {v, w, 2, x} and n ≥ 0. It is not too difficult to prove that the following system of recursions holds:

a ν,n+1 = [ν = 0]s a 0,n + H∈SG ν (G) a ev(H) v,n a ew(H) w,n a e2(H) 2,n a ex(H) x,n . (2)
Here we have used Iverson notation: [ν = 0] is equal to 1 if ν = 0 and 0 otherwise. To see why this holds, simply notice that a connected subgraph on X n+1 induces either a connected subgraph, a subgraph of SG x -type, or the empty set on each of the parts that are isomorphic to X n . The graphs H describe all possible ways for this. The additional summand in the case ν = 0 arises from the possibility that a connected subgraph can be contained in one of the parts (without its boundary vertices) only. Of course, such a connected subgraph cannot contain v n+1 or w n+1 . The bound a 2,n+1 ≥ a s 2,n is a simple consequence of these recursions: Choose H = G in the recursion (2) for a 2,n+1 . Similarly, by choosing appropriate "extremal" subgraphs we obtain

a 0,n+1 ≥ a s-deg(v)-deg(w) 2,n , a v,n+1 ≥ a s-deg(w) 2,n , a w,n+1 ≥ a s-deg(v) 2,n , a x,n+1 ≥ a s-c 2,n ,
where c the number of edges in a minimal v-w cut. As a consequence, a 2,n grows at least doubly exponentially if G is not a path. Therefore, for ν ∈ {0, v, w, x}, the quantity a ν,n also grows at least doubly exponentially in this case. The proof of Theorem 2 is split into several lemmata. In the following we assume that v, w and v 0 , w 0 have degree 1 in G and X 0 , respectively, and write v ′ and w ′ for the unique neighbors of v and w in G.

Lemma 9. We have a ν,n ≥ a 2,n for ν ∈ {0, v, w} and

a x,n+1 a 2,n+1 ≥ 2 • a x,n a 2,n .
Proof. The first inequality is plain due to the degree restriction: since v n and w n have degree 1 in X n , we can obtain a connected subgraph that doesn't contain w n from every connected subgraph that contains w n by removing w n and its incident edge. Hence, a v,n ≥ a 2,n , and likewise for ν = w and ν = 0. In order to prove the second inequality, let us note that every connected subgraph H of G which contains v and w has to contain the edge vv ′ as well as the edge ww ′ . Therefore, we can construct two graphs H v , H w ∈ SG x (G) from H by removing the edge vv ′ respectively ww ′ . Then

e ν (H ν ) = e ν (H), e 2 (H ν ) = e 2 (H) -1, e x (H ν ) = e x (H) + 1
for ν ∈ {v, w}. Together with Equation ( 2), this shows that

a x,n+1 ≥ 2a 2,n+1 • a x,n a 2,n ,
proving the statement.

Assume that G is not a path, so that a 2,1 > 1. Then we have already noticed that a ν,n grows at least doubly exponentially for ν ∈ {0, v, w, 2} if n → ∞:

a ν,n ≥ C ν α s n (3)
for some α > 1 and constants C ν . Due to this observation it is possible to reduce the recursions given by (2) up to a very small error term: We say that a subgraph H of G is important, if every edge in G has at least one endpoint in H, and denote by SG ν i (G) the important subgraphs of SG ν (G). Lemma 10. Assume that G is not a path, then for ν ∈ {0, v, w, 2} the following asymptotic formulae hold:

a ν,n+1 = 1 + O α -s n H∈SG ν i (G) a ev(H) v,n a ew(H) w,n a e2(H) 2,n a ex(H) x,n .
Proof. Since a ν,n grows at least doubly exponentially only those summands in the Formulae (2) can be of asymptotic importance which belong to a subgraph H, where e v (H) + e w (H) + e 2 (H) + e x (H) is maximal. However, this equals se r (H), where e r (H) is the number of edges connecting vertices in V G \ V H. This means that every edge of G must have at least one endpoint in H, so that H must be an important subgraph. The error term is then implied by (3).

We note that in Lemma 12 more explicit expressions for a ν,n+1 are derived.

Lemma 11. Assume that G is not a path. Suppose that h w (vv ′ ) = v or h v (ww ′ ) = w, then there exist constants c ν for ν ∈ {0, v, w}, so that

a ν,n = c ν a 2,n + O α -s n
holds. If h w (vv ′ ) = v and h v (ww ′ ) = w, then a distinction on the parity of n is necessary: there are constants c k,ν for ν ∈ {0, v, w} and k ∈ {0, 1}, so that

a ν,n = c k,ν a 2,n + O α -s n
holds, where k ∈ {0, 1} is the remainder of the division of n by 2.

Proof. Depending on the construction of X n+1 , there are four possible arrangements with respect to the replacement of the edges vv ′ and ww ′ by copies of X n . We deal with two of these four cases, since they are all very similar. Hence assume that h v (vv ′ ) = v and h w (ww ′ ) = w. Consider an important graph H in SG v i (G). This graph H must contain w ′ but not w. Hence we can construct an important graph H w ∈ SG 2 i (G) by adding the vertex w and the edge ww ′ . The mapping

SG v i (G) → SG 2 i (G), H → H w is in fact a one-to-one correspondence. Since e v (H w ) = e v (H) -1, e w (H w ) = e w (H), e 2 (H w ) = e 2 (H) + 1, e x (H w ) = e x (H), it follows that a v,n+1 = a 2,n+1 • a v,n a 2,n + O α -s n or a v,n+1 a 2,n+1 = a v,n a 2,n + O α -s n .
If ε n denotes the error term on the right hand side, then

a v,n a 2,n = a v,0 a 2,0 + n-1 k=0 ε k , which converges to c v = a v,0 a 2,0 + ∞ k=0 ε k ,
and the error term is given by

a v,n a 2,n = c v - ∞ k=n ε k = c v + O α -s n . Analogous arguments show that a w,n a 2,n = c w + O α -s n and a 0,n a 2,n = c 0 + O α -s n ,
which implies the statement for this arrangement. If

h v (vv ′ ) = v, h w (ww ′ ) = w ′ or h v (vv ′ ) = v ′ , h w (ww ′ ) = w,
we obtain the same result by essentially the same method, but if h v (vv ′ ) = v ′ and h w (ww ′ ) = w ′ , which is equivalent to h w (vv ′ ) = v and h v (ww ′ ) = w, things are slightly different. Again, there is a one-to-one correspondence H → H w between SG v i (G) and SG 2 i (G) (constructed as before), but we have

e v (H w ) = e v (H), e w (H w ) = e w (H) -1, e 2 (H w ) = e 2 (H) + 1, e x (H w ) = e x (H).
Therefore, we get

a v,n+1 = a 2,n+1 • a w,n a 2,n + O α -s n
and analogously

a w,n+1 = a 2,n+1 • a v,n a 2,n + O α -s n .
Combining the two, we obtain

a v,n+2 = a 2,n+2 • a v,n a 2,n + O α -s n ,
and following the above arguments we find that a v,n converges to some value c 0,v for even n and some value c 1,v for odd n, which makes the distinction of the two cases necessary. The rest of the proof is analogous to the first case again.

As before we write τ (G) for the number of spanning trees in G and θ(G) for the number of thickets in G with respect to v and w. Furthermore, recall that δ = |V G| -1 is the number of edges in a spanning tree of G. A vertex of degree 1 is called a leaf and we write ℓ v to denote the number of leaves (except v, w) of G, which are not v-ends. Let t v be equal to v, if w is the w-end of the edge ww ′ , or equal to w otherwise. We use ℓ w and t w analogous to ℓ v and t v , respectively. For simplicity let ℓ = ℓ v + ℓ w be the number of leaves (except v, w) in G.

Lemma 12. If G is not a path, then, for ν ∈ {v, w},

a 0,n+1 = τ (G) a tv,n a tw,n a δ-ℓ-2 2,n (a v,n + a 2,n ) ℓv (a w,n + a 2,n ) ℓw a s-δ x,n (1 + O(2 -n )), a ν,n+1 = τ (G) a tν ,n a δ-ℓ-1 2,n (a v,n + a 2,n ) ℓv (a w,n + a 2,n ) ℓw a s-δ x,n (1 + O(2 -n )), a 2,n+1 = τ (G) a δ-ℓ 2,n (a v,n + a 2,n ) ℓv (a w,n + a 2,n ) ℓw a s-δ x,n (1 + O(2 -n )), a x,n+1 = θ(G) a δ-ℓ-1 2,n (a v,n + a 2,n ) ℓv (a w,n + a 2,n ) ℓw a s-δ+1 x,n (1 + O(2 -n )).
Proof. By Lemma 11 the quantities a v,n for ν ∈ {0, v, w, 2} are of the same asymptotic order. Lemma 9 implies a x,n ≥ c 2 n a 2,n for some constant c. Consequently, only those summands in the Equations (2) are of interest which belong to an important subgraph H, where e x (H) is maximal (all the other summands are smaller by an exponential factor). Certainly, H must not contain any circles, since we could remove edges in this case to increase e x (H) and decrease e 2 (H) instead. Furthermore, V G \ V H contains leaves only. Otherwise, assume that there is a vertex u in V G \ V H that is not a leaf. Since the subgraph H is important, all neighbors of this vertex have to be in V H, and there are at least two of them, since u is not a leaf. Now we can add u and an edge between u and one of its neighbors to H to obtain a new important subgraph H ′ , and e x (H ′ ) > e x (H) (there is at least one edge between u and one of the vertices in V H ′ that doesn't belong to EH ′ and therefore contributes to e x (H ′ ), but not to e x (H)).

Now consider for instance the recurrence for a 2,n+1 in [START_REF] Bollobás | Modern graph theory[END_REF]. Each important subgraph H in the sum for which e x (H) is maximized is obtained by taking a spanning tree and possibly removing some of the leaves (since it must be connected and cycle-free and contain all vertices except possibly for the leaves). There are τ (G) choices for the spanning tree, and for each of the leaves we may choose whether to include it or not. Edges whose one endpoint is a leaf contribute a factor a v,n (if the leaf is not included and a wend), a factor a w,n (if the leaf is not included and a v-end) or a factor a 2,n (if the leaf is included). The remaining edges contribute a factor of a 2,n if they are contained in H (there are always precisely δℓ such edges) and a x,n otherwise (there are precisely sδ such edges). Combining everything, we obtain the equation for a 2,n+1 . The other three equations follow analogously.

Corollary 13. If G is not a path, then there is a constant c x , so that

a x,n = c x ρ n a 2,n (1 + O(2 -n )).
Proof. Divide the last two equations in the previous lemma to find

a x,n+1 a 2,n+1 = θ(G) τ (G) • a x,n a 2,n (1 + O(2 -n )) = ρ • a x,n a 2,n (1 + O(2 -n )).
Now we can apply the same technique as in Lemma 8 to show that

a x,n a 2,n = c x ρ n (1 + O(2 -n ))
for some constant c x , which concludes the proof of this lemma.

Proof of Theorem 2. Suppose that h w (vv ′ ) = v or h v (ww ′ ) = w. Using Lemma 11, Lemma 12, and Corollary 13 we obtain

a 2,n+1 = Cρ n(s-δ) a s 2,n (1 + O(2 -n ))
for some constant C. The methods employed in the proof of Lemma 8 now yield the statement. The case h w (vv ′ ) = v and h v (ww ′ ) = w is similar.

We conjecture that a result similar to Theorem 2 holds, when the assumption that v, w are leaves is replaced by ρ > 1. The following example indicates the differences and problems. Example. Let us consider the number of connected subgraphs in the sequence of Austria graphs, see Example 2. Using Formula (2) and Figure 6 we obtain:

a 0,n+1 = 4a 0,n + a 2 w,n + a v,n a 2 w,n + a 3 w,n a 2,n , a v,n+1 = a v,n + a v,n a w,n a 2,n + a 2 w,n a 2 2,n , a w,n+1 = a 2 v,n + a v,n a w,n a 2,n + a 2 v,n a w,n a 2,n + a w,n a 3 2,n + 3a w,n a 2 2,n a x,n , a 2,n+1 = a 2 v,n a 2 2,n + a 4 2,n + 3a 3 2,n a x,n , a x,n+1 = a 3 v,n + a 2 v,n a w,n a 2,n + 2a 2 v,n a 2,n a x,n + a 3 2,n a x,n + 5a 2 2,n a 2 x,n .
Since all the numbers a ν,n grow at least doubly exponentially, say a ν,n ≥ C ν ζ 4 n (for some constants C ν and ζ > 1), the terms of total degree 4 are much larger than the others. So we have to study the following:

a 0,n+1 = a 3 w,n a 2,n 1 + O ζ -4 n , a v,n+1 = a 2 w,n a 2 2,n 1 + O ζ -4 n , a w,n+1 = a w,n (a 2 v,n a 2,n + a 3 2,n + 3a 2 2,n a x,n ) 1 + O ζ -4 n , a 2,n+1 = a 2,n (a 2 v,n a 2,n + a 3 2,n + 3a 2 2,n a x,n ), a x,n+1 = (a 2 v,n a w,n a 2,n + 2a 2 v,n a 2,n a x,n + a 3 2,n a x,n + 5a 2 2,n a 2 x,n ) 1 + O ζ -4 n . It follows that a 0,n+1 a v,n+1 = a w,n a 2,n • 1 + O ζ -4 n , a w,n+1 a 2,n+1 = a w,n a 2,n • 1 + O(ζ -4 n , so that a 0,n = c a v,n 1 + O ζ -4 n and a w,n = c a 2,n 1 + O ζ -4 n
for some constant c. By removing the edge incident to v n from a connected subgraph in SG 2 (X n ) a subgraph in SG x (X n ) is obtained. Thus a x,n ≥ a 2,n . Furthermore, using the recursions we get where

a x,n+1 a 2,n+1 ≥ 2a 2 v,n a 2,n a x,n + a 3 2,n a x,n + 5a 2 2,n a 2 x,n a 2 v,n a 2 2,n + a 4 2,n + 3a 3 2,n a x,n = a x,n a 2,n • 1 + a 2 v,n + 2a 2,n a x,n a 2 v,n + a 2 2,n + 3a 2,n a x,n . Since 2(a 2 v,n + 2a 2,n a x,n ) ≥ 2a 2 v,n + a 2 2,n + 3a 2,n a x,n ≥ a 2 v,n + a 2 2,n + 3a
k ν =      0 if ν = x, 1 if ν ∈ {2, w}, 2 if ν ∈ {v, 0}.
The approximate numerical value of β is 1.77280776, whereas (C 0 , C v , C w , C 2 , C x ) is approximately equal to (1.13215234, 0.793383233, 0.950775521, 0.666279023, 0.632751624).

For comparison with Theorem 2 we recall that ρ = 5 3 and that the exponent of ρ in this theorem is given by

- s -δ s -1 = - 1 3 .
Although the number of connected subgraphs is given by the same asymptotic form as before, the quantities a ν,n show a different behavior.

We notice that the asymptotics derived in the previous example always holds, when deg(v n ) = 1 and deg(w n ) = c > 1 or vice versa. The argument for this follows the line of the proof of Theorem 2 with suitable modifications. The final example demonstrates that quite a different asymptotic behavior is possible if the resistance scaling factor ρ is less than 1.

Example. We consider the graphs X n defined in Example 3. Since the graphs X n are symmetric with respect to v n and w n , the quantities a v,n and a w,n are the same: Thus set a 1,n = a v,n = a w,n . Then we get a 0,n+1 = 6a 0,n + 3a 2 1,n , a 1,n+1 = a 3 1,n + 3a Thus we can reduce the system of recursions to a 0,n+1 = 3a

b 1 ,

 1 n+1 = 12b 1,n b 2,n b 4,n + 14b 3 2,n + 3b 1,n b 2 5,n + • • • , b 2,n+1 = b 1,n b 2 4,n + 7b 2 2,n b 4,n + b 2,n b 2 4,n + 3b 2,n b 2 5,n + • • • , b 3,n+1 = 2b 1,n b 4,n b 5,n + • • • , b 4,n+1 = 6b 2,n b 2 4,n + b 3 4,n + 3b 4,n b 2 5,n , b 5,n+1 = 4b 2,n b 4,n b 5,n + • • • , b 6,n+1 = 2b 2,n b 2 5,n + • • • , b 7,n+1 = 3b 3,n b 2 5,n + • • • .

  EG) be a finite (multi-)graph with vertex set V G and edge set EG. Fix two distinguished vertices v, w in G. Throughout this work we denote by s = |EG| the number of edges in G, by d = d G (v, w) the distance of the distinguished vertices v and w in G, and by δ = |V G| -1 the number of edges in a spanning tree of G.

Figure 2 .

 2 Obviously, s = 4, d = 2, δ = 3, and ρ = 5 3 .

[ 7 ]

 7 ) we have ρ(G[B]) ≥ ρ(G) = ρ. Now define SF ⊗ (G, B) to be the set of all forests in SF ⊗ (G), where the components of v and w have union B, and define SF • (G, B) to be the set of forests in SF • (G), where the component of v and w is B. Since SF ⊗ (G, B) and SF • (G, B) only impose restrictions with respect to v and w within the set B, it follows that

  Corollary 5 yields f (x) < x for x > 0. Hence the sequence x n tends to 0 and an application of Lemma 6 and Lemma 7 shows once again, that the strong version of the asymptotic expansions holds.• ρ = 1, d = 1: In this case there is an edge connecting v and w, which is a bridge (otherwise ρ < 1). Thus f (x) = x and b n+1 = b s n r(x 0 ), whence it is easy to derive exact formulae for a n and b n .Since d = 1 implies ρ ≤ 1, the case ρ > 1 and d = 1 is impossible.

Fig. 6 :

 6 Fig. 6: The first stage in the sequence of Austria graphs. Boxed labels indicate v-ends and w-ends of edges.

3 n. 3 n a 2 ,n 1 + O 2 3 n 3 ( 2 / 3 -kν )n β 4 n 1

 33233231 Using the last two relations we get a x,n = c x 5 for some c x . Now the methods of Lemma 8 yield a ν,n = C ν 5

  As a consequence we can further simplify the recursions:a 0,n+1 = a 3 w,n a 2,n 1 + O ζ -4 n , a v,n+1 = a 2 w,n a 2 2,n 1 + O ζ -4 n ) , a w,n+1 = 3a w,n a 2 2,n a x,n 1 + O 2

	the inequality
					a x,n+1 a 2,n+1	≥	3 2	•	a x,n a 2,n	.
	follows. Using this estimate we obtain
		a x,n ≥ c ′ 3 2	n a 2,n	and		a w,n ≥ c ′′ 3 2	n a v,n ,
	for some constants c ′ and c ′′ , since
	a w,n+1 a v,n+1	≥	3a w,n a 2 2,n a x,n a 2 w,n a 2 2,n	• 1 + O ζ -4 n =	3a x,n a w,n	• 1 + O ζ -4 n	.
								3	n ,
			a 2,n+1 = 3a 3 2,n a x,n 1 + O 2 3	n ,
			a x,n+1 = 5a 2 2,n a 2 x,n 1 + O 2
								2,n a x,n

  + 2a 2,n a x,n )3 .As usual the numbers a ν,n (ν ∈ {0, 1, 2, x}) grow at least doubly exponentially, saya ν,n ≥ c ν ζ 6 n , it We have a 1,n ≤ a x,n by induction: a 1,n+1 ≤ 8a 3 1,n a 3 2,n ≤ 8a 3 2,n a 3 x,n ≤ a x,n+1 . As a consequence it follows that + 2a 2,n a x,n ) 3 a 3 1,n (1 + a 2,n ) 3 = O(3 -n ) + 2 •Using the techniques of Lemma 6 we obtaina x,n = 2 -3/2 β 3 n a 1,n (1 + O(3 -n ))for some constant β > 1. Finally this implies that

			3 1,n a 2,n + 3a 3 1,n a 2 2,n + a 3 1,n a 3 2,n = a 3 1,n (1 + a 2,n ) 3 ,
	a 2,n+1 = 3a 4 1,n a 2 2,n + 3a 2 1,n a 4 2,n + a 6 2,n + 12a 2 1,n a 3 2,n a x,n + 12a 4 2,n a 2 x,n + 6a 5 2,n a x,n ,
	a x,n+1 = a 6 1,n + 6a 4 1,n a 2,n a x,n + 12a 2 1,n a 2 2,n a 2 x,n + 8a 3 2,n a 3 x,n = (a 2 1,n follows that
		a 2,n+1 a 1,n+1	≥	3a 2 1,n a 4 2,n 1,n (1 + a 2,n ) 3 ≥ 3 • a 3	a 2,n a 1,n	• 1 + O ζ -6 n
	a x,n+1 a 1,n+1	=	(a 2 1,n a x,n a 1,n	3	1 + O ζ -6 n
		= 8	a x,n a 1,n	3	(1 + O(3 -n )).
		a 2,n+1 a x,n+1	≥	12a 4 2,n a 2 x,n 1,n + 2a 2,n a x,n ) 3 = (a 2	3 2	•	a 2,n a x,n	1 + O β -3 n	.

Acknowledgements

We would like to thank an anonymous referee for various valuable comments and suggestions.

† This material is based upon work supported by the German Research Foundation DFG under grant number 445 SUA-113/25/0-1 and the South African National Research Foundation under grant number 65972. 1365-8050 c 2009

From this we easily obtain a 0,n = 3β

where

We remark that this type of asymptotics always holds when a ν,n = o(a 2,n ) for ν ∈ {0, v, w, x}. In this case the reasoning used in the example above applies, so that

where

, and c is the number of edges in a minimal v-w cut. The behavior of a 0,n is possibly different due to the fact that G \ {v, w} may be disconnected.

Finally, we conjecture that the number of connected subgraphs exhibit a phase transition: when ρ > 1, then the asymptotics of Theorem 2 holds, whereas the asymptotics is given by (4) if ρ < 1.