Expanding graphs contain all small trees

The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.     

On graphsG for which all large trees areG-good

LetG be a graph satisfying x(G) = k. The following problem is considered: WhichG have the property that, if n is large enough, the Ramsey numberr(G, T) has the value (k — 1)(n — 1) + 1 for all treesT onn vertices? It is shown thatG has this property if and only if for somem, G is a subgraph of bothL _k,m andM _K.m , whereL _k,m andM _k,m are two particulark-chromatic graphs. Indeed, it is shown thatr(L _k,m ,M _k,m ,T _n ) = (k — 1)(n — 1) + 1 whenn is large.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

A graph which embeds all small graphs on any large set of vertices

For certain cardinals λ and κ a colouring P:[λ]²→λ is constructed such that if X ϵ[λ]^λ and Q:[κ]²→λ, then there is a one-to-one function i:κ→X such that P(i″A)=Q(A) for every Aϵ[κ]². Additional results are obtained.     

The graphs for which all strong orientations are hamiltonian

We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.     

A Steiner triple system which colors all cubic graphs

We prove that there is a Steiner triple system ?? such that every simple cubic graph can have its edges colored by points of ?? in such a way that for each vertex the colors of the three incident edges form a triple in ??. This result complements the result of Holroyd and ?koviera that every bridgeless cubic graph admits a similar coloring by any Steiner triple system of order greater than 3. The Steiner triple system employed in our proof has order 381 and is probably not the smallest possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 15–24, 2004     

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.     

On homeomorphically irreducible spanning trees in cubic graphs

A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.     

On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

Occupation games on graphs in which the second player takes almost all vertices

Given a connected graph G=(V,E), two players take turns occupying vertices v∈V by placing black and white tokens so that the current vertex sets B,W⊆V are disjoint, B∩W=0?, and the corresponding induced subgraphs G[B] and G[W] are connected any time. A player must pass whenever (s)he has no legal move. (Obviously, after this, the opponent will take all remaining vertices, since G is assumed connected.) The game is over when all vertices are taken, V=B^∗∪W^∗. Then, Black and White get b=|B^∗|/|V| and w=|W^∗|/|V|, respectively. Thus, the occupation game is one-sum, b+w=1, and we could easily reduce it to a zero-sum game by simply shifting the payoffs, b^′=b−1/2,w^′=w−1/2. Let us also notice that b≥0 and w≥0; moreover, b>0 and w>0 whenever |V|>1.[Let us remark that the so-called Chinese rules define similar payoffs for the classic game of GO, yet, the legal moves are defined in GO differently.]Like in GO, we assume that Black begins. It is easy to construct graphs in which Black can take almost all vertices, more precisely, for each ε>0 there is a graph G for which b>1−ε. In this paper we show that, somewhat surprisingly, there are also graphs in which White can take almost all vertices.