We specify what is meant for a polytope to be reconstructible from its graph or dual graph, and we introduce the problem of class reconstructibility; i.e., the face lattice of the polytope can be determined from the (dual) graph within a given class. We provide examples of cubical polytopes that are not reconstructible from their dual graphs. Furthermore, we show that matroid (base) polytopes are not reconstructible from their graphs and not class reconstructible from their dual graphs; our counterexamples include hypersimplices. Additionally, we prove that matroid polytopes are class reconstructible from their graphs, and we present an $O(n^3)$ algorithm that computes the vertices of a matroid polytope from its $n$-vertex graph. Moreover, our proof includes a characterization of all matroids with isomorphic basis exchange graphs.

The problem of calculating exact lower bounds for the number of k-faces of d-polytopes with n vertices, for each value of k, and characterizing the minimizers has recently been solved for n not exceeding 2 d. We establish the corresponding result for $n=2d+1$; the nature of the lower bounds and the minimizing polytopes are quite different in this case. As a byproduct, we also characterize all d-polytopes with $d+3$ vertices and only one or two edges more than the minimum.

We define the excess degree $\xi(P)$ of a $d$-polytope $P$ as $2f_1-df_0$, where $f_0$ and $f_1$ denote the number of vertices and edges, respectively. This parameter measures how much $P$ deviates from being simple. It turns out that the excess degree of a $d$-polytope does not take every natural number: the smallest possible values are $0$ and $d-2$, and the value $d-1$ only occurs when $d=3$ or 5. On the other hand, for fixed $d$, the number of values not taken by the excess degree is finite if $d$ is odd, and the number of even values not taken by the excess degree is finite if $d$ is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., $\xi(P)

Large-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ Δ ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks.

Abstract In the pursuit of obtaining largest graphs of given maximum degree Δ and diameter D, many construction techniques have been developed. Compounding of graphs is one such technique. In this article, by means of the compounding of complete graphs into a bipartite Moore graph of diameter 6, we obtain a family of large graphs of the same diameter. For maximum degrees Δ = 5, 6, 9, 12, and 14, members of this family constitute the largest known graphs of diameter 6. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009