Abstract | ||
---|---|---|
For n≤2k we study the maximum number of edges of an induced subgraph on n vertices of the k-dimensional hypercube Qk. In the process we revisit a well-known divide-and-conquer maximin recurrence f(n)=max(min(n1,n2)+f(n1)+f(n2)) where the maximum is taken over all proper bipartitions n=n1+n2. We first use known results to present a characterization of those bipartitions n=n1+n2 that yield the maximum 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∈N, the determination of the number h(n) of these bipartitions that yield the said maximum f(n). We present recursive formulae for h(n), a generating function h(x), and an explicit formula for h(n) in terms of a special representation of n. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.disc.2013.08.033 | Discrete Mathematics |
Keywords | Field | DocType |
Rectangular grid,Hypercube,Induced subgraphs,Bipartition,Divide-and-conquer,Divide-and-conquer maximin recurrence | Integer,Generating function,Discrete mathematics,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
313 | 24 | 0012-365X |
Citations | PageRank | References |
1 | 0.41 | 7 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Geir Agnarsson | 1 | 103 | 14.69 |