کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647485 | 1342354 | 2013 | 8 صفحه PDF | دانلود رایگان |
For n≤2kn≤2k we study the maximum number of edges of an induced subgraph on nn vertices of the kk-dimensional hypercube QkQk. In the process we revisit a well-known divide-and-conquer maximin recurrence f(n)=max(min(n1,n2)+f(n1)+f(n2))f(n)=max(min(n1,n2)+f(n1)+f(n2)) where the maximum is taken over all proper bipartitions n=n1+n2n=n1+n2. We first use known results to present a characterization of those bipartitions n=n1+n2n=n1+n2 that yield the maximum f(n)=min(n1,n2)+f(n1)+f(n2)f(n)=min(n1,n2)+f(n1)+f(n2). Then we use this characterization to present the main result of this article, namely, for a given n∈Nn∈N, the determination of the number h(n)h(n) of these bipartitions that yield the said maximum f(n)f(n). We present recursive formulae for h(n)h(n), a generating function h(x)h(x), and an explicit formula for h(n)h(n) in terms of a special representation of nn.
Journal: Discrete Mathematics - Volume 313, Issue 24, 28 December 2013, Pages 2857–2864