An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N.

Abstract. In the classical model of network creation games introduced by Fabrikant et al. [ On a network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (PODC‘03), 2003, pp. 347–351], [Formula: see text] players correspond to the nodes of a network buying links of price [Formula: see text] and to the other players with the goal of being well-connected to the resulting network. Still as an open problem, the constant PoA conjecture states that the Price of Anarchy (PoA) is constant for any [Formula: see text]. When tackling this problem distinct behaviors must be taken into the account depending on whether [Formula: see text] has either large or low value. It is known that for [Formula: see text] every ne is a tree and for [Formula: see text] with [Formula: see text] the diameter of networks that are in equilibrium when restricting to deviations that consist only in buying links ( buying equilibria) is at most a constant. These results imply that the PoA is constant for the disjoint union of the two ranges, and thus the constant PoA conjecture seems to be true for most of all the possible values [Formula: see text]. In this paper we study the PoA for the remaining range of [Formula: see text] and we show the following: (i) For [Formula: see text] the PoA is constant by proving that the size of any biconnected component of an equilibrium graph is constant. (ii) For [Formula: see text] we have that [Formula: see text], where [Formula: see text] is the maximum diameter of an equilibrium graph for the same range of [Formula: see text]. Therefore if the constant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter. Towards this direction we find nontrivial buying equilibria of nonconstant diameter when [Formula: see text] and [Formula: see text], exploring new intimate relationships between distance-uniform graphs and buying equilibria.

An $\epsilon$-distance-uniform graph is one with a critical distance $d$ such that from every vertex, all but at most an $\epsilon$-fraction of the remaining vertices are at distance exactly $d$. Motivated by the theory of network creation games, Alon, Demaine, Hajiaghayi, and Leighton made the following conjecture of independent interest: that every $\epsilon$-distance-uniform graph (and, in fact, a broader class of $\epsilon$-distance-almost-uniform graphs) has critical distance at most logarithmic in the number of vertices $n$. We disprove this conjecture and characterize the asymptotics of this extremal problem. Specifically, for $\frac1n \le \epsilon \le \frac1{\log n}$, we construct $\epsilon$-distance-uniform graphs with critical distance $2^{\Omega(\frac{\log n}{\log \epsilon^{-1}})}$. We also prove an upper bound on the critical distance of the form $2^{O(\frac{\log n}{\log \epsilon^{-1}})}$ for all $\epsilon$ and $n$. Our lower bound construction introduces a novel method inspired by the Tower of Hanoi puzzle and may itself be of independent interest.