The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number

Introduction

The graph is a mathematical model for a discrete set whose members are interlinked in some way. The members of this collection can be the different parts of the earth and the connections between them are bridges that tie them together (like the Konigsberg problem). Graph theory is one of the important issues in discrete mathematics, which studies graphs and modeling issues by them. In 1736, Leonard Euler established the graph theory for solving the Konigsberg Bridge problem. But James Joseph Sylvester was the first to use the word "graph" in 1878 to name these mathematical models.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. The convention of using colors originates from coloring the countries of a map, where each face is literally colored. Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research. This paper is concerned with a specific coloring, say the distinguishing coloring which is originated from a classic elementary problem, Frank Rubin's key problem, which Stan Wagon circulated in the Macalester College problem column:

Professor X, who is blind, keeps keys on a circular key ring. Suppose there are a variety of handle shapes available that can be distinguished by touch. Assume that all keys are symmetrical so that a rotation of the key ring about an axis in its plane is undetectable from an examination of a single key. How many shapes does Professor X need to use in order to keep n keys on the ring and still be able to select the proper key by feel?

The surprise is that if six or more keys are on the ring, there need only be 2 different handle shapes; but if there are three, four, or five keys on the ring, there must be 3 different handle shapes to distinguish them. The answer to the key problem depends on the shape of the key ring. A labeling of a graph G, ɸ: V(G) → {1,2, …, r}, is said to be r-distinguishing if no automorphism of G preserves all of the vertex labels. The point of the labels on the vertices is to destroy the symmetries of the graph, that is, to make the automorphism group of the labeled graph trivial. Consequently, we define the distinguishing number of a graph G by

D(G)=min {r| G has a labeling that is r-distinguishing}.

Similarly, the distinguishing index D′(G) of a graph G is the least integer d such that G has an edge labeling with d labels that is preserved only by a trivial‎ automorphism‎.

Let G be a connected graph of order n ≥ 3 and let c: E(G) → {1, 2, …, k} 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) = (a₁, a₂, …, a_k), where a_i 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.

Material and methods

We use cycle rank parameter and first consider the case and prove that and then using spanning trees we obtain an upper bound for distinguishing number.

Results and discussion

In this paper, we consider the relationship between the distinguishing number and index with the detection number of a graph. In particular, we show that the distinguishing index of a connected graph is at most equal with the detection number, i.e., D'(G) ≤ det(G).

Conclusion

The following conclusions were drawn from this research.

An upper bound for D(G) by the detection number of its spanning trees.
The upper and lower bounds for the distinguishing number by the detection number of a graph.
Every detectable coloring is a distinguishing labeling of the edges of a graph.
The upper bounds for the distinguishing index by the detection number of a graph../files/site1/files/61/11.pdf