Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002     

The number of edge 3-colorings of a planar cubic graph as a permanent

In this paper, we establish that the number of edge 3-colorings of a finite planar cubic graph G, i.e., 3-colorings of its interchange graph H, is equal to 2^?N|Permanent(A)|, where N is the number of edges of G, and A is the 2N × 2N square matrix formed by repeating each row of the N × 2N vertex-directed edge incidence matrix of H (with an arbitrary orientation). As the number of 4-colorings of a finite maximal (fully triangulated) planar graph is equal to four times the number of edge 3-colorings of its planar cubic dual, this result gives a formula for the number of 4-colorings of a finite maximal planar graph.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

The integrity of a cubic graph

Integrity, a measure of network reliability, is defined as

where G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:

Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible.     

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     

On the number of hamilton cycles in a random graph

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n) distinct hamilton cycles for any fixed ?>0.     

Expose-and-merge exploration and the chromatic number of a random graph

The expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexityn ^O(logn) is described and used to show that the chromatic number of a random graph for any edge probability 0<p<1 falls in the interval $$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$ with probability approaching unity asn→∞.     

On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3-regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ?)n, for any constant ?>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.     

The number of endpoints of a random walk on a semi-infinite metric path graph

Theoretical and Mathematical Physics - We study a semi-infinite metric path graph and construct the long-time asymptotic logarithm of the number of possible endpoints of a random walk.     

The independent domination number of a cubic 3-connected graph can be much larger than its domination number

We show that the difference between independent domination number of a cubic 3-connected graph and its domination number can be arbitrarily large. This disproves a conjecture posed inGraphs and Combinatorics by C. Barefoot, F. Harary, and K.F. Jones [2].     

A note on the chromatic number of a dense random graph

Let G_n,p denote the random graph on n labeled vertices, where each edge is included with probability p independent of the others. We show that for all constant p

     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.     

The semi-chromatic number of a graph

We introduce the notion of the semi-chromatic number of a graph with a nonempty number of edges. Then we prove that the difference between the semi-chromatic number and the half of the chromatic number is at most 1.     

On the chromatic number of a random subgraph of the Kneser graph

Results are obtained that substantially strengthen a previously known bound for the chromatic number of a random subgraph of the Kneser graph.     

On the number of vertices of given degree in a random graph

This note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ ??(n, p) asymptotically has a normal distribution.