Detectable coloring of graphs

A basic problem in graph theory is to distinguish the vertices of a connected graph from one another in some manner. In this study, we investigate the problem of coloring the edges of a graph in a manner that distinguishes the vertices of the graph. The method we use combines many of the features of previously introduced methods.; Let G be a connected graph of order n ≥ 3 and let c : E(G) → {lcub}1,2,...,k{rcub} be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v with respect to c is the k-tuple c( v) = (alpha1,alpha2,···,alpha k), where ai is the number of edges incident with v that are colored i (1 ≤ i ≤ k). The coloring c is detectable if distinct vertices have distinct color codes. The detection number det( G) of G is the minimum positive integer k for which G has a detectable k-coloring.; The detection number of stars, double stars, cycles, paths, complete graphs, and complete bipartite graphs are determined. It is also shown that a pair k, n of positive integers is realizable as the detection number and the order of some nontrivial connected graph if and only if k = n = 3 or 2 ≤ k ≤ n - 1.; Extremal problems on detectable colorings of graphs are investigated in this study. If G is a connected graph of order n and size m, then the number of edges that must be deleted from G to obtain a spanning tree of G is m - n + 1. The number m - n + 1 is called the cycle rank of G. For integers y and n, where y ≥ 0 and n ≥ &ceill0;3+1+8y2 &ceilr0; , let Dy (n) denote the maximum detection number among all connected graphs of order n with cycle rank y and let dy (n) denote the minimum detection number among all connected graphs of order n with cycle rank y . Hence, if Gy,n denotes the set of all connected graphs of order n with cycle rank y , then Dyn= max&cubl0;detG :G∈Gy ,n&cubr0; dy n=min&cubl0;det G:G∈ Gy,n&cubr0;. (Abstract shortened by UMI.)...