Research papers available for download.

You can download some of my papers(in pdf form) here. They can be viewed and printed with the free Adobe Acrobat Reader. Click here to get the latest version.)

Bounds for Partial List Colourings (in Ars Comb.), R. Haas, D. Hanson and G. MacGillivray
Let G be a simple graph on n vertices with list chromatic number s. If each vertex of G is assigned a list of t colours Albertson, Grossman and Haas [1] asked how many of the vertices, l_{t,s}, are necessarily colourable from these lists? They conjectured that l_{t,s} >= tn/s. Their work was extended by Chappell [2]. We improve the known lower bounds for l_{t,s}.

Bases for Splines on a Subdivided Domain (in Acta Math.) Ruth Haas
Let Sr(D) be the module of all splines of smoothness r on the rectilinear partition D which subdivides some domain D. Further, let Sr(G) be the module of all splines of smoothness r on G which also subdivides D, where G is a finer subdivision of D. We study the relationship between a generating set of Sr(D) and a generating set for Sr(G) . This paper gives an algorithm for extending a generating set for Sr(D) to one for for Sr(G) . This method is built on algebraic properties of splines and the Grobner Basis Algorithm.


Characterizations of Arboricity of Graphs(in Ars Comb.) Ruth Haas
The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any l edges produces a graph which is decomposible into k spanning trees and (ii) graphs for which adding some l edges produces a graph which is decomposible into k spanning trees.



Partial List Colorings
( in Discrete Mathematics) Michael O. Albertson, Sara Grossman and Ruth Haas
Suppose G is an s-choosable graph with n vertices, and every vertex of G is assigned a list of t colors. We conjecture that at least (t/s) n of the vertices of G can be colored from these lists.
We provide lower bounds and consider related questions. For instance we show that if G is X-colorable (rather than being s-choosable), then more than [1 - ({X - 1}/X)^t]n of the vertices of G can be colored from the lists and that this is asymptotically best possible. We include a number of open questions.

Star Forests, Dominating Sets and Ramsey-type Problems.( in Discrete Math.)

Sheila Ferneyhough, Ruth Haas, Denis Hanson and Gary MacGillivray

Abstract: A star forest of a graph G is a spanning subgraph of G in which each component is a star. The minimum number of edges required to guarantee that an arbitrary graph, or a bipartite graph, has a star forest of size n is determined. Sharp lower bounds on the size of a largest star forest are also determined. For bipartite graphs, these are used to obtain an upper bound on the domination number in terms of the number of vertices and edges in the graph, which is an improvement on a bound of Vizing. In turn, the results on bipartite graphs are used to determine the minimum number of lattice points required so that there exists a subset of n lattice points, no three of which form a right triangle with legs parallel to the coordinate axes.

 

Bounds on the signed domination number of a graph. Ruth Haas and Thomas B. Wexler

Abstract: Let G=(V,E) be a simple graph on vertex set V and define a function f: V->{-1,1}. The function f is a signed dominating function if for every vertex xe V, the closed neighborhood of x contains more vertices with function value 1 than with -1. The signed domination number of G, gs(G), is the minimum weight of a signed dominating function on G. We give a sharp lower bound on the signed domination number of a general graph with a given minimum and maximum degree, generalizing a number of previously known results. Using similar techniques we give upper and lower bounds for the signed domination number of some simple graph products: the grid PjxPk CjxPk and CjxCk. For fixed width, these bounds differ by only a constant.

 

Signed domination number of a graph and its complement. Ruth Haas and Thomas B. Wexler

Abstract: Let G=(V,E) be a simple graph on vertex set V and define a function f: V->{-1,1}. The function f is a signed dominating function if for every vertex xe V, the closed neighborhood of x contains more vertices with function value 1 than with -1. The signed domination number of G, gs(G), is the minimum weight of a signed dominating function on G. Let G* denote the complement of G. In this paper we establish upper and lower bounds on gs(G) + gs(G*) and |gs(G)| |gs(G*)|.