101 |
Graph approximation : issues and complexityHorton, Steven Bradish 05 1900 (has links)
No description available.
|
102 |
The Bernoulli salesmanWhitaker, Linda M. 08 1900 (has links)
No description available.
|
103 |
On partial completion problemsEaston, Todd William 08 1900 (has links)
No description available.
|
104 |
Linear algorithms for graphs of tree-width at most fourSanders, Daniel Preston 08 1900 (has links)
No description available.
|
105 |
Varieties of graph congruencesWeiss, Alex. January 1984 (has links)
Graph-monoids are introduced as algebraic objects which correspond to congruences over graphs. Varieties are defined, and a one-to-one correspondence between varieties of graph-monoids and varieties of graph-congruences is demonstrated. This is viewed as a generalization of the known correspondence between monoid varieties and congruence varieties. Some classification and effective characterizations of graph-monoid varieties are obtained. These are used to decide membership in the wreath product of certain monoids varieties and the variety of definite semigroups.
|
106 |
Perfect graphsHoang, Chinh T. January 1985 (has links)
No description available.
|
107 |
Two classes of perfect graphs / 2 classes of perfect graphs.Hayward, Ryan B. January 1986 (has links)
No description available.
|
108 |
Aspects of graph vulnerability.Day, David Peter. January 1994 (has links)
This dissertation details the results of an investigation into, primarily, three aspects of graph vulnerability namely, l-connectivity, Steiner Distance hereditatiness and functional isolation. Following the introduction in Chapter one, Chapter two focusses on the l-connectivity of graphs and introduces the concept of the strong l-connectivity of digraphs. Bounds on this latter parameter are investigated and then the l-connectivity function of particular types of graphs, namely caterpillars and complete multipartite graphs as well as the strong l-connectivity function of digraphs, is explored. The chapter concludes with an examination of extremal graphs with a given l-connectivity. Chapter three investigates Steiner distance hereditary graphs. It is shown that if G is 2-Steiner distance hereditary, then G is k-Steiner distance hereditary for all k≥2. Further, it is shown that if G is k-Steiner distance hereditary (k≥ 3), then G need not be (k - l)-Steiner distance hereditary. An efficient algorithm for determining the Steiner distance of a set of k vertices in a k-Steiner distance hereditary graph is discussed and a characterization of 2-Steiner distance hereditary graphs is given which leads to an efficient algorithm for testing whether a graph is 2-Steiner distance hereditary. Some general properties about the cycle structure of k-Steiner distance hereditary graphs are established and are then used to characterize 3-Steiner distance hereditary graphs. Chapter four contains an investigation of functional isolation sequences of supply graphs. The concept of the Ranked supply graph is introduced and both necessary and sufficient conditions for a sequence of positive nondecreasing integers to be a functional isolation sequence of a ranked supply graph are determined. / Thesis (Ph.D.)-University of Natal, 1994.
|
109 |
Aspects of distance and domination in graphs.Smithdorf, Vivienne. January 1995 (has links)
The first half of this thesis deals with an aspect of domination; more specifically, we
investigate the vertex integrity of n-distance-domination in a graph, i.e., the extent
to which n-distance-domination properties of a graph are preserved by the deletion
of vertices, as well as the following: Let G be a connected graph of order p and let
oi- S s;:; V(G). An S-n-distance-dominating set in G is a set D s;:; V(G) such that
each vertex in S is n-distance-dominated by a vertex in D. The size of a smallest
S-n-dominating set in G is denoted by I'n(S, G). If S satisfies I'n(S, G) = I'n(G),
then S is called an n-distance-domination-forcing set of G, and the cardinality of a
smallest n-distance-domination-forcing set of G is denoted by On(G). We investigate
the value of On(G) for various graphs G, and we characterize graphs G for which
On(G) achieves its lowest value, namely, I'n(G), and, for n = 1, its highest value,
namely, p(G). A corresponding parameter, 1](G), defined by replacing the concept
of n-distance-domination of vertices (above) by the concept of the covering of edges
is also investigated.
For k E {a, 1, ... ,rad(G)}, the set S is said to be a k-radius-forcing set if, for each
v E V(G), there exists Vi E S with dG(v, Vi) ~ k. The cardinality of a smallest
k-radius-forcing set of G is called the k-radius-forcing number of G and is denoted
by Pk(G). We investigate the value of Prad(G) for various classes of graphs G,
and we characterize graphs G for which Prad(G) and Pk(G) achieve specified values.
We show that the problem of determining Pk(G) is NP-complete, study the
sequences (Po(G),Pl(G),P2(G), ... ,Prad(G)(G)), and we investigate the relationship
between Prad(G)(G) and Prad(G)(G + e), and between Prad(G)(G + e) and the connectivity
of G, for an edge e of the complement of G.
Finally, we characterize integral triples representing realizable values of the triples
b,i,p), b,l't,i), b,l'c,p), b,l't,p) and b,l't,l'c) for a graph. / Thesis (Ph.D.-Mathematics and Applied Mathematics)-University of Natal, 1995.
|
110 |
Graph and digraph embedding problems.Maharaj, Hiren. January 1996 (has links)
This thesis is a study of the symmetry of graphs and digraphs by considering certain
homogeneous embedding requirements.
Chapter 1 is an introduction to the chapters that follow. In Chapter 2 we present
a brief survey of the main results and some new results in framing number theory.
In Chapter 3, the notions of frames and framing numbers is adapted to digraphs. A
digraph D is homogeneously embedded in a digraph H if for each vertex x of D and
each vertex y of H, there exists an embedding of D in H as an induced subdigraph
with x at y. A digraph F of minimum order in which D can be homogeneously
embedded is called a frame of D and the order of F is called the framing number of
D. We show that that every digraph has at least one frame and, consequently, that
the framing number of a digraph is a well defined concept. Several results involving
the framing number of graphs and digraphs then follow. Analogous problems to those
considered for graphs are considered for digraphs.
In Chapter 4, the notions of edge frames and edge framing numbers are studied.
A nonempty graph G is said to be edge homogeneously embedded in a graph H if for
each edge e of G and each edge f of H, there is an edge isomorphism between G and
a vertex induced subgraph of H which sends e to f. A graph F of minimum size
in which G can be edge homogeneously embedded is called an edge frame of G and
the size of F is called the edge framing number efr(G) of G. We also say that G is
edge framed by F. Several results involving edge frames and edge framing numbers
of graphs are presented.
For graphs G1 and G2 , the framing number fr(G1 , G2 ) (edge framing number
ef r(GI, G2 )) of G1 and G2 is defined as the minimum order (size, respectively) of a
graph F such that Gj (i = 1,2) can be homogeneously embedded in F. In Chapter 5
we study edge framing numbers and framing number for pairs of cycles. We also
investigate the framing number of pairs of directed cycles. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 1996.
|
Page generated in 0.0539 seconds