Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- $\alpha$-labeling (1)
- (n (1)
- 6-regular graphs (1)
- Algorithm (1)
- Anti-Ramsey problems (1)
-
- Cartesian product (1)
- Computational complexity (1)
- Dominating set (1)
- Edge coloring (1)
- Erdos-Stone Theorem (1)
- Eternal domination (1)
- Fences (1)
- Full binary trees (1)
- Graceful labeling (1)
- Grid graph (1)
- Independent set (1)
- K (1)
- Klein bottle (1)
- Matching (1)
- Rainbow $k$-connectivity (1)
- Rainbow connection coloring (1)
- Rainbow connection number (1)
- Rainbow index (1)
- Rainbow subgraphs (1)
- Rainbow vertex-connection number (1)
- Rainbow-cycle-forbidding (1)
- Strong rainbow connection number (1)
- T) problem (1)
- Total rainbow connection number (1)
- Triangulations (1)
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens
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 Kn 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
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 …
An Updated Survey On Rainbow Connections Of Graphs - A Dynamic Survey, Xueliang Li, Yuefang Sun
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
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
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 …
Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb
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 …
Note On 6-Regular Graphs On The Klein Bottle, Michiko Kasai, Naoki Matsumoto, Atsuhiro Nakamoto, Takayuki Nozawa, Hiroki Seno, Yosuke Takiguchi
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
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.