The chromatic difference sequence of a graph

Let α_k(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set α_k(G)=α_k(G)?α_(k?1)(G). The sequence a₁(G), a₂(G),… is called the chromatic difference sequence of the graph G. We present necessary and sufficient conditions for a sequence to be the chromatic difference sequence of some 4-colorable graph.     

On the power sequence of a graph

Necessary and sufficient conditions for a sequence (p ₁,p ₂, …,p _n ) of positive integers to be the power sequence of a connected graph onn vertices withm edges are given. The maximum power of a connected graph onn vertices withm edges and the class of all extremal graphs are also determined.     

The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

The scaling window for a random graph with a given degree sequence

We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( \begin{align*}\mathcal {D}\end{align*}) and prove that if |Q| = O(n^‐1/3R^2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n^2/3R^‐1/3). If |Q| is asymptotically larger than n^‐1/3R^2/3 then the size of the largest component is asymptotically smaller or larger than n^2/3R^‐1/3. Thus, we establish that the scaling window is |Q| = O(n^‐1/3R^2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The number of graphs and a random graph with a given degree sequence

We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d₁,…,d_n). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

The degree sequence of a scale‐free random graph process

Recently, Barabási and Albert [2] suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P(d) of vertices with degree d should obey a power law P(d)αd^?γ. They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P(d) asymptotically for all d≤n^1/15, where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001     

The realization graph of a degree sequence with majorization gap 1 is Hamiltonian

It is known that the degree sequences of threshold graphs are characterized by the property that they are not majorized strictly by any degree sequence. Consequently every degree sequence d can be transformed into a threshold sequence by repeated operations consisting of subtracting I from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform d into a threshold sequence is called the majorization gap of d. A realization of a degree sequence d of length n is a graph on the vertices 1, …, n, where the degree of vertex i is d_i. The realization graph %plane1D;4A2;(d) of a degree sequence d has as vertices the realizations of d, and two realizations are neighbors in %plane1D;4A2;(d) if one can be obtained from the other by deleting two existing edges [a, b], [c, d] and adding two new edges [a, d]; [b, c] for some distinct vertices a, b, c, d. It is known that %plane1D;4A2;(d) is connected. We show that if d has a majorization gap of 1, then %plane1D;4A2;(d) is Hamiltonian.     

The dimension of a graph

For each graph G the dimension of G is defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of G are segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown.     

The biparticity of a graph

The biparticity β(G) of a graph G is the minimum number of bipartite graphs required to cover G. It is proved that for any graph G, β(G) = {log₂χ(G)}. In view of the recent announcement of the Four Color Theorem, it follows that the biparticity of every planar graph is 2.     

The point-arboricity of a graph

The point-arboricity ρ(G) of a graphG is defined as the minimum number of subsets in a partition of the point set ofG so that each subset induces an acyclic subgraph. Dually, the tuleity τ(G) is the maximum number of disjoint, point-induced, non-acyclic subgraphs contained inG. Several results concerning these numbers are presented, among which are formulas for the point arboricity and tulgeity of the class of completen-partite graphs. Definitions not given in this article may be found in [5].     

The splittance of a graph

The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).     

The graph of a foliation

Let M be a riemannian manifold with a riemannian foliation F. Among other things we construct a special metric on the graph of the foliation, , (which is complete, when M is complete), and use the relations of Gray [1] and O'Neill [7] and the elementary structural properties of , to find a necessary and sufficient condition that also have non-positive sectional curvature, when M does. This condition depends only on the second fundamental form and the holonomy of the leaves. As a corollary we obtain a generalization of the Cartan-Hadamard Theorem. Partially supported by NSF Grant MCS77-02721.     

The spectral radii of a graph and its line graph

The spectral radius of a (directed) graph is the largest eigenvalue of adjacency matrix of the (directed) graph. We give the relation on the characteristic polynomials of a directed graph and its line graph, and obtain sharp bounds on the spectral radius of directed graphs. We also give the relation on the spectral radii of a graph and its line graph. As a consequence, the spectral radius of a connected graph does not exceed that of its line graph except that the graph is a path.     

The total graph and regular graph of a commutative ring

Let R be a commutative ring. The total graph of R, denoted by T(Γ(R)) is a graph with all elements of R as vertices, and two distinct vertices x,y∈R, are adjacent if and only if x+y∈Z(R), where Z(R) denotes the set of zero-divisors of R. Let regular graph of R, Reg(Γ(R)), be the induced subgraph of T(Γ(R)) on the regular elements of R. Let R be a commutative Noetherian ring and Z(R) is not an ideal. In this paper we show that if T(Γ(R)) is a connected graph, then . Also, we prove that if R is a finite ring, then T(Γ(R)) is a Hamiltonian graph. Finally, we show that if S is a commutative Noetherian ring and Reg(S) is finite, then S is finite.     

A Rao-type characterization for a sequence to have a realization containing a split graph

For a given graph H, a non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. The split graph on r+s vertices is denoted by S_r,s. In this paper, we give a Rao-type characterization for π to be potentially S_r,s-graphic. A simplification of this characterization is also presented.