The diameter of a graph is defined as the minimum path length, measured in number of edges, that suffices to connect any two nodes; we confine ourselves to undirected connected graphs with at most 1 edge between any two nodes. Nodes connected by an edge are called each other's neighbours. The degree of a node is defined as the number of edges incident on that node; it equals the number of neighbours of that node. Note that summing the degrees of all nodes yields twice the number of edges.
At the one extreme we have the complete graph: it has the minimum diameter, but the maximum number of edges. At the other extreme we have the string: it has the maximum diameter and the minimum number of edges. We are interested in graphs with modest diameter and modest maximum degree.
A well-known example of such a graph is the n-dimensional "cube": its diameter equals n and so does the degree of each of its 2n nodes. To see this, we identify the nodes with the 2n n-digit binary labels and connect any two labels that differ in exactly 1 digit. Thus each node has n neighbours and, hence, degree n; the length of a shortest path between two such labels equals the number of bit positions in which these labels differ and, hence, the diameter equals n. We shall now construct graphs whose diameter is smaller than the 2logarithm of the number of nodes while the maximum degree remains at that bound or is decreased as well.
To this end we generalize the solution presented by the hypercube in three different ways.
Firstly, we replace our binary labels by mixed-radix labels, in which one digit, which we denote as "the leading digit", plays a special role. For the purpose of this exposition, we can confine ourselves to labels consisting of a leading x-ary digit followed by k y-ary digits; the graph has then x∙yk nodes.
Secondly, the edges correspond to a subset of the pairs of labels that differ in exactly 1 digit. (It is this subsetting that allows the departure from binary digits while keeping the degrees down.) Note that, as in the case of the hypercube, a path consists of a sequence of labels in which each next label differs in exactly 1 digit from its predecessor.
Thirdly, the restriction that on the paths considered each digit position is subjected to at most 1 transition —viz. from source value to target value— is waived for the leading digit.
Our construction has the following characteristics:
* whether two labels differing only in one of the y-ary digits are connected or not depends on the pair of y-ary digits in that position and on the (common) leading digit; the dependence is such that there exists at least one value for the leading digit such that the two labels would be connected; we refer to such a leading digit value as "enabling" the y-ary transition in question;
* whether two labels differing only in their leading digits are connected or not depends only on the pair of leading digit values; among the x possible values of the leading digit these connections form a connected graph, to which we shall refer as "the x-ary connectivity".
To determine a path from a given source label to a given target label, we determine on the x-ary connectivity a shortest path P from source leading digit to target leading digit, such that each of the at most k y-ary transitions required is enabled by at least one x-ary value on P. We can now effectuate the stepwise transformation from source label to target label by performing (in order) the x-ary transitions of P, interleaved with the required y-ary transitions in such a way that each of the latter is enabled by the leading digit of the intermediate label. As a result, the diameter is at most k + the maximum length of P. (The proviso "at most" has been included because for very few required y-ary transitions the above procedure sometimes does not lead to the shortest path between source and target label; only for very small k, the proviso may not be vacuous.) In the following, L will denote the maximum length of P.
The purpose of the remainder of this note is to show how we can choose the parameters —primarily x, y, k, and the enabling rules— so as to gain on the hypercube.
(i) We begin by exploring the case y = 4 by partitioning the 6 possible y-ary transitions in classes A, B, and C as follows:
Name:
Anonymous2010-03-01 17:46
okay fuck, I give up, someone explain to me how this thread turned the whole of the site italic
>>2
It's my thread
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
Name:
Anonymous2010-03-01 18:37
[i]
int main(){
lolwut;
return my anus;
}
[/i]
Name:
Anonymous2010-03-01 18:38
int main(){
I got trolled ._. ;
return zomg;
}
Name:
Anonymous2010-03-01 18:42
[b][u][i]It's my thread
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
[code]
[/i][/u][/b]
[/code]
Name:
Anonymous2010-03-01 18:43
It's my thread
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "i" tag inside the "code" tag or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I [u]put[/u] the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly
I put the "lime" inside the "coconut" or vice-versa. Idk exactly