Edge disjoint spanning trees in random graphs

We show that almost everyG _m-out containsm edge disjoint spanning trees.     

On random minimum length spanning trees

We extend and strengthen the result that, in the complete graphK _n with independent random edge-lengths uniformly distributed on [0, 1], the expected length of the minimum spanning tree tends to(3) asn. In particular, ifK _n is replaced by the complete bipartite graphK _{n, n} then there is a corresponding limit of 2 (3).     

A simple formula for the number of spanning trees of line graphs

Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k () times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula: Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].     

On the spanning trees of weighted graphs

Given a weighted graph, letW ₁,W ₂,W ₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW ₁ is at mostk–1 edge swaps away from some spanning tree of weightW _k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW _k .This work was supported in part by a grant from the AT&T foundation and NSF grant DCR-8351757.Primarily supported by a 1967 Science and Engineering Scholarship from the Natural Sciences and Engineering Research Council of Canada.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

Hitting time fork edge-disjoint spanning trees in a random graph

We show that in almost every random graph process, the hitting time for havingk edge-disjoint spanning trees equals the hitting time for having minimum degreek.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

The asymptotic number of graphs not containing a fixed color-critical subgraph

For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphT _n ().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math. 7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge.     

The chromatic number of random graphs at the double-jump threshold

A crucial step in the Erdös-Rényi (1960) proof that the double-jump threshold is also the planarity threshold for random graphs is shown to be invalid. We prove that whenp=1/n, almost all graphs do not contain a cycle with a diagonal edge, contradicting Theorem 8a of Erdös and Rényi (1960). As a consequence, it is proved that the chromatic number is 3 for almost all graphs whenp=1/n.Research supported U.S. National Science Foundation Grants DMS-8303238 and DMS-8403646. The research was conducted on an exchange visit by Professor Wierman to Poland supported by the national Academy of Sciences of the USA and the Polish Academy of Sciences.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

The forcing number of graphs with given girth

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

The asymptotic behaviour of the number of three-connected triangulations of the disk,with a reflective symmetry in a line

We consider the enumeration of the three-connected triangulations of the disk, with a reflective symmetry about a line. The asymptotic behavior is unlike that observed for rooted maps or for maps having rotational symmetry.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Contractions of graphs with no spanning eulerian subgraphs

Letp2 be a fixed integer, and letG be a connected graph onn vertices. If(G)2, ifd(u)+d(v)>2n/p–2 holds wheneveruvE(G), and ifn is sufficiently large compared top, then eitherG has a spanning eulerian subgraph, orG is contractible to a graphG ₁ of order less thenp and with no spanning eulerian subgraph. The casep=2 was proved by Lesniak-Foster and Williamson. The casep=5 was conjectured by Benhocine, Clark, Köhler, and Veldman, when they proved virtually the casep=3. The inequality is best-possible.