No description available.

Let G = (V,E) be a graph. The transitivity of a graph G, denoted Tr(G), equals the maximum order k of a partition x = {Vi,of V such that for every i,j, 1 i j k, Vi dominates Vj. We consider the transitivity in many special classes of graphs, including cactus graphs, coronas, Cartesian products, and joins. We also consider the effects of vertex or edge deletion and edge addition on the transivity of a graph.

A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as generalized deBruijn cycles or U-cycles) of several combinatorial objects. We extend the body of known results by presenting new results on the existence of universal cycles of monotone, augmented onto, and Lipschitz functions in addition to universal cycles of certain types of lattice paths and random walks.

We have listed many of Pete Slater's most important papers, which generated a lot of interest in the graph theory community. We have also listed a sample of some of the interesting graph theory concepts which he introduced or helped to introduce. And we have listed a sample of some of his more interesting paper titles. A complete listing of all 238 of his publications would take some 23 pages; due to page limitations we do not list them here. Instead, they can easily be found using either MathSciNet or Google Scholar. The MathSciNet source provides Math Reviews abstracts of all of Pete's publications, while Google Scholar shows current citation numbers and provides links to pdfs of many of Pete's papers which can be freely downloaded. We conclude with some photographs. Obviously, the research of Professor Slater is vast and continues to have an enormous impact on Graph Theory. We miss you, Pete!.

A vertex set U ⊂ V in a connected graph G = (V, E) is a cutset if G - U is disconnected. If no proper subset of U is also a cutset of G, then U is a minimal cutset. An XVC-partition π = {V1, V2,..........Vn} of the vertex set V(G) of a connected graph G is a partition of V(G) such that every VJ ϵ n is a minimal cutset of G. For an MVC- partition π of G, the π-graph G of G has vertex set -n such that V, V" e n are adjacent in G if and only if there exist v ϵ V and vv ϵ E(G) such that v v ϵ E(G). Graphs that are π-graphs of cycles are characterized. A homomorphic image H of a graph G can be obtained from a partition π = {V1, V2,..........Vn} of V(G) into independent sets such that V(H) = {V1, V2,..........Vn} , where vi is adjacent to Vj if and only if some vertex of K is adjacent to some vertex of Vj in G. By investigating graphs H that are homomorphic images of the Cartesian product H □ K2, it is shown that for every nontrivial connected graph H and every integer r > 2, there exists an r-regular graph G such that H is a homomorphic image of G. It is also shown that every nontrivial tree T is a homomorphic image of T □ K2 but that not all graphs H are homomorphic images of HDK2.

The complementary prism GG 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 G. A Roman dominating function on a graph G = (V, E) is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 is adjacent to a vertex with label 2. The Roman domination number γR(G) of G is the minimum f(V) = Σv∈V f(v) over all such functions of G. We study the Roman domination number of complementary prisms. Our main results show that γR(GG) takes on a limited number of values in terms of the domination number of GG and the Roman domination numbers of G and G.

Given an arbitrary graph, a new graph can be obtained by deleting a vertex, or adding or deleting an edge. Much work has been done concerning these graph alterations and their effects on the domination number of a graph. A survey of the literature in this area is found in [13], Chapter 5. Here we are concerned with generalizations of the alterations involving edges.

Inspired by the "two envelopes exchange paradox," a finitely additive probability measure m on the natural numbers is introduced. The measure is uniform in the sense that m ((i))=m ((j)) for all i, j∈□. The measure is shown to be translation invariant and has such desirable properties as m ((i∈□| i=0 (mod2)))=1/2. For any r∈ [0, 1], a set A is constructed such that m (A)=r; however, m is not defined on the power set of □. Finally, a resolution to the two envelopes exchange paradox is presented in terms of m.

No description available.

Background: It has become increasingly apparent that a comprehensive database of RNA motifs is essential in order to achieve new goals in genomic and proteomic research. Secondary RNA structures have frequently been represented by various modeling methods as graph-theoretic trees. Using graph theory as a modeling tool allows the vast resources of graphical invariants to be utilized to numerically identify secondary RNA motifs. The domination number of a graph is a graphical invariant that is sensitive to even a slight change in the structure of a tree. The invariants selected in this study are variations of the domination number of a graph. These graphical invariants are partitioned into two classes, and we define two parameters based on each of these classes. These parameters are calculated for all small order trees and a statistical analysis of the resulting data is conducted to determine if the values of these parameters can be utilized to identify which trees of orders seven and eight are RNA-like in structure. Results: The statistical analysis shows that the domination based parameters correctly distinguish between the trees that represent native structures and those that are not likely candidates to represent RNA. Some of the trees previously identified as candidate structures are found to be "very" RNA like, while others are not, thereby refining the space of structures likely to be found as representing secondary RNA structure. Conclusion: Search algorithms are available that mine nucleotide sequence databases. However, the number of motifs identified can be quite large, making a further search for similar motif computationally difficult. Much of the work in the bioinformatics arena is toward the development of better algorithms to address the computational problem. This work, on the other hand, uses mathematical descriptors to more clearly characterize the RNA motifs and thereby reduce the corresponding search space. These preliminary findings demonstrate that graph-theoretic quantifiers utilized in fields such as computer network design hold significant promise as an added tool for genomics and proteomics.