Physical Sciences and Mathematics Commons^™

Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens

Theory and Applications of Graphs

It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of K_n with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently …

An Eternal Domination Problem In Grids, William Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello

Theory and Applications of Graphs

A dynamic domination problem in graphs is considered in which an infinite sequence of attacks occur at vertices with mobile guards; the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack, the vertices containing guards must form a dominating set of the graph. The minimum number of guards that can defend the graph against such an arbitrary sequence of attacks is called the m-eviction number of the graph. In this paper, the m-eviction …

Mcnair Journal: The 2017-2018 Cohort, Georgia Southern University Mcnair Scholars Program

Georgia Southern University McNair Scholars Journal

Full issue of the Georgia Southern University McNair Journal presented by the Ronald E. McNair Post-Baccalaureate Achievement Program at Georgia Southern University.

This issue features the 2017-2018 cohort of McNair Scholars.

• Health Promotion Through Self-Management Among College Students Olamide Adebayo; Anunay Bhattacharya, DrPH(c); Marian M. Tabi, PhD
• Boring Sponges “Inhibition on Easter Oysters” health Conditions and Growth in Reference to the Tidal Height Johanna Dieudonne; John Carroll, PhD
• Synthesis of 1,2,3-Triazole Amino Acid Derivatives for Structure Activity Relationship Investigations Arneshia T. Henderson; Raven Richardson; Brandon Sellers; Ria Ramoutar PhD.; Karelle Aiken PhD.
• Detection of Saccharides Using Boronic Acid Derivatives Taylor …

Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb

Theory and Applications of Graphs

A perfect forest is a spanning forest of a connected graph G, all of whose components are induced subgraphs of G and such that all vertices have odd degree in the forest. A perfect forest can be thought of as a generalization of a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra.

We give here two very short proofs of the Perfect Forest Theorem which use only …

An Updated Survey On Rainbow Connections Of Graphs - A Dynamic Survey, Xueliang Li, Yuefang Sun

Theory and Applications of Graphs

The concept of rainbow connection was introduced by Chartrand, Johns, McKeon and Zhang in 2008. Nowadays it has become a new and active subject in graph theory. There is a book on this topic by Li and Sun in 2012, and a survey paper by Li, Shi and Sun in 2013. More and more researchers are working in this field, and many new papers have been published in journals. In this survey we attempt to bring together most of the new results and papers that deal with this topic. We begin with an introduction, and then try to organize the …

Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang

Theory and Applications of Graphs

For positive integers m, n, the greatest number of colors that can appear in an edge coloring of K(m,n) which avoids rainbow cycles is m + n - 1. Here these colorings are constructively characterized. It turns out that these colorings can be encoded by certain vertex labelings of full binary trees with m + n leafs.

On The Graceful Cartesian Product Of Alpha-Trees, Christian Barrientos, Sarah Minion

Theory and Applications of Graphs

A graceful labeling of a graph G of size n is an injective assignment of integers from the set {0,1,…,n} to the vertices of G such that when each edge has assigned a weight, given by the absolute value of the difference of the labels of its end vertices, all the weights are distinct. A graceful labeling is called an α-labeling when the graph G is bipartite, with stable sets A and B, and the labels assigned to the vertices in A are smaller than the labels assigned to the vertices in B. In this …

Note On 6-Regular Graphs On The Klein Bottle, Michiko Kasai, Naoki Matsumoto, Atsuhiro Nakamoto, Takayuki Nozawa, Hiroki Seno, Yosuke Takiguchi

Theory and Applications of Graphs

Altshuler classified six regular graphs on the torus, but Thomassen and Negami gave different classifications for six regular graphs on the Klein bottle. In this note, we unify those two classifications, pointing out their difference and similarity.

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory and Applications of Graphs

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.