For k∈{Z}+ and G a simple connected graph, a k-radio labeling f:VG→Z+ of G requires all pairs of distinct vertices u and v to satisfy |f(u)-f(v)|≥ k+1-d(u,v). When k=1, this requirement gives rise to the familiar labeling known as vertex coloring for which each vertex of a graph is labeled so that adjacent vertices have different "colors". We consider k-radio labelings of G when k=diam(G). In this setting, no two vertices can have the same label, so graphs that have radio labelings of consecutive integers are one extreme on the spectrum of possibilities; graphs that can be labeled with such a labeling are called radio graceful. In this thesis, we give four main results on the existence of radio graceful graphs, which focus on Hamming graphs (Cartesian products of complete graphs) and a generalization of the Petersen graph. In particular, we prove the existence of radio graceful graphs of arbitrary diameter, a result previously unknown. Two of these main results show that, under certain conditions, the tth Cartesian power Gt of a radio graceful graph G is also radio graceful. We will also speak to occasions when Gt is not radio graceful despite G being so, as well as some partial results about necessary and sufficient conditions for a graph G so that Gt is radio graceful.

To investigate the feasibility of improving performance for EcmaScript code in environments that restricts the usage of dynamic just in time compilers, an ahead of time EcmaScript to C compiler capable of compiling a substantial subset of the EcmaScript language has been constructed. The compiler recovers type information without customized type information by using the Cartesian Product Algorithm. While the compiler is not complete enough to be used in production it has shown to be capable of producing code that matches contemporary optimizing just in time compilers in terms of performance and substantially outperforms the interpreters currently used in restricted environments. In addition to constructing and benchmarking the compiler a survey was conducted to gauge if the selected subset of the language was acceptable for use by developers.

The complementary prism GḠ of a graph G is formed from the disjoint union of G and its complement Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A set S ⊆ V(G) is a double dominating set of G if for every v ∈ V(G)\S, v is adjacent to at least two vertices of S, and for every w ∈ S, w is adjacent to at least one vertex of S. The double domination number of G is the minimum cardinality of a double dominating set of G. We begin by determining the double domination number of complementary prisms of paths and cycles. Then we characterize the graphs G whose complementary prisms have small double domination numbers. Finally, we establish lower and upper bounds on the double domination number of GḠ and show that all values between these bounds are attainable.

The complementary prism GḠ of a graph G is formed from the disjoint union of G and its complement Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A set S ⊆ V(G) is a double dominating set of G if for every v ∈ V(G)\S, v is adjacent to at least two vertices of S, and for every w ∈ S, w is adjacent to at least one vertex of S. The double domination number of G is the minimum cardinality of a double dominating set of G. We begin by determining the double domination number of complementary prisms of paths and cycles. Then we characterize the graphs G whose complementary prisms have small double domination numbers. Finally, we establish lower and upper bounds on the double domination number of GḠ and show that all values between these bounds are attainable.

The complementary prism GḠ of a graph G is formed from the disjoint union of G and its complement G by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A set S ⊆ V(G) is a restrained dominating set of G if for every v € V(G) \S, v is adjacent to a vertex in S and a vertex in V(G) \S. The restrained domination number of G is the minimum cardinality of a restrained dominating set of G. We study restrained domination of complementary prisms. In particular, we establish lower and upper bounds on the restrained domination number of GḠ, show that the restrained domination number can be attained for all values between these bounds, and characterize the graphs which attain the lower bound.

Placing degree constraints on the vertices of a path yields the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2, ⋯ vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(v1) ≥ deg(vi+1). Conversely, a path π = u1, u2, ⋯ uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(u1) ≤ deg(ui+1). The downhill domination number of a graph G is defined to be the minimum cardinality of a set S of vertices such that every vertex in V lies on a downhill path from some vertex in S. The uphill domination number is defined as expected. We explore the properties of these invariants and their relationships with other invariants. We also determine a Vizing-like result for the downhill (respectively, uphill) domination numbers of Cartesian products.

No description available.

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs. (authors' abstract) / Series: Research Report Series / Department of Statistics and Mathematics

The diploma thesis presents a collection of solved problems in binary relations. Students are familiarized with various applications of binary relations on high school mathematics and geometry. The work focuses on graphical representation of binary relations and their use in solving equations, inequalities and their sys- tems. It is a teaching text designated for a mathematics seminar at high school. In addition to exercises, it also includes an introduction of new concepts which are supplemented by relevant definitions and illustrative examples. 1