Search

Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple, connected, and undirected graph, where V and E are the set of vertices and the set of edges of G. An edge magic total labeling on G is a bijection f: V → E → {1, 2, ..., |V | + |E|}, provided that for every uv ∈ E,w(uv) = f(u) + f(v) + f(uv) = K for a constant number K. Such a labeling is said to be a super edge magic total labeling if f(V) = {1, 2,..., |V |} and a b-edge consecutive edge magic total labeling if f(E) = {b + 1, b + 2, ..., b + |E|} with b ≥ 1. In this research, we give sufficient conditions for a graph G having a super edge magic total labeling to have a b-edge consecutive edge magic total labeling. We also give several classes of connected graphs which have both labelings. [ABSTRACT FROM AUTHOR]

Let G be a graph with an edge k-coloring γ: E(G) → {1; …; k} (not necessarily proper). A path is called a rainbow path if all of its edges have different colors. The map γis called a rainbow coloring if any two vertices can be connected by a rainbow path. The map γis called a strong rainbow coloring if any two vertices can be connected by a rainbow geodesic. The smallest k for which there is a rainbow k-coloring (resp. strong rainbow k-coloring) on G is called the rainbow connection number (resp. strong rainbow connection number) of G, denoted rc(G) (resp. src(G)). In this paper we generalize the notion of "color codes" that was originally used by Chartrand et al. in their study of the rc and src of complete bipartite graphs, so that it now applies to any connected graph. Using color codes, we prove a new class of lower bounds depending on the existence of sets with common neighbours. Tight examples are discussed, involving the amalgamation of complete graphs, generalized wheel graphs, and a special class of sequential join of graphs. [ABSTRACT FROM AUTHOR]

An uncertain graph is a graph in which the edges are indeterminate and the existence of edges are characterized by belief degrees which are uncertain measures. This paper aims to bring graph coloring and uncertainty theory together. A new approach for uncertain graph coloring based on an α-cut of an uncertain graph is introduced in this paper. Firstly, the concept of α-cut of uncertain graph is given and some of its properties are explored. By means of α-cut coloring, we get an α-cut chromatic number and examine some of its properties as well. Then, a fact that every α-cut chromatic number may be a chromatic number of an uncertain graph is obtained, and the concept of uncertain chromatic set is introduced. In addition, an uncertain chromatic algorithm is constructed. Finally, a real-life decision making problem is given to illustrate the application of the uncertain chromatic set and the effectiveness of the uncertain chromatic algorithm. [ABSTRACT FROM AUTHOR]

An edge-coloring of a graph is called rainbow if any two vertices are connected by a path consisting of edges of different colors. The least number of colors in such a coloring is called the rainbow connection number of G , denoted by rc( G ). An edge-coloring of a graph is called strong rainbow if any two vertices are connected by a geodesic consisting of edges of different colors. The least number of colors in such a coloring is called the strong rainbow connection number of G , denoted by src( G ). In this paper we study the rc and src of the m -splitting of a graph. In particular we study Spl m ( K n ). We present the exact values of its rc and src in several cases, and we prove several bounds in the other cases. [ABSTRACT FROM AUTHOR]