Bounds for Partial List
Colourings
(in Ars Comb.),
R. Haas, D. Hanson and G. MacGillivray
Bases for Splines on a Subdivided Domain
(in Acta Math.)
Ruth Haas
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.
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}.
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: 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. WexlerAbstract: 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*)|.