Many networks arise in a random and distributed fashion, and yet result in having a specific type of degree structure: e.g., the WWW, many social networks, biological networks, etc., exhibit power-law, stretched exponential, or similar degree structures. Much work has examined how a graph's degree-structure influences other graph properties such as connectivity, diameter, etc. Probabilistic edge removal models link failures, information spreading, and processes that consider (random) subgraphs. They also model spreading influence of information as in the independent cascade model [20]. We examine what happens to a graph's degree structure under edge failures where the edges are removed independently with identical probabilities. We start by analyzing the effect of edge failure on the degree sequence for power-law and exponential networks, and improve upon results of Martin, Carr & Faulon and Cooper & Lu; then, using intuition from the power-law case, we derive asymptotic results for almost any degree sequence of interest. Our major result shows a classification of degree sequences which leads to simple rules that give much of the new expected degree sequence after random edge-removal; we also provide associated concentration bounds.

A rigid vertex of a graph is one that has a prescribed cyclic order of its incident edges. We study orientable genus ranges of 4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values over all orientable surfaces into which a graph is embedded cellularly, and the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic order of incident edges at every vertex. The genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers, and we address two questions: which intervals of integers appear as genus ranges of such graphs, and what types of graphs realize a given genus range. For graphs with 2 vertices ( 1), we prove that all intervals [] for all ≤ , and singletons [] for some ≤ , are realized as genus ranges. For graphs with 2 - 1 vertices ( ≥ 1), we prove that all intervals [] for all ≤ except [0], and [] for some ≤ , are realized as genus ranges. We also provide constructions of graphs that realize these ranges.