Volume 6, Issue 1 (Vol. 6, No. 1 2020)
mmr 2020, 6(1): 109-118 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Alikhani S, Soltani S. The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number. mmr 2020; 6 (1) :109-118
URL: http://mmr.khu.ac.ir/article-1-2625-en.html
URL: http://mmr.khu.ac.ir/article-1-2625-en.html
1- Yazd University , alikhani@yazd.ac.ir
2- Yazd University
2- Yazd University
Abstract: (3262 Views)
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) = (a1, a2, …, ak), 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.
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.
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) = (a1, a2, …, ak), 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.
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
Type of Study: Original Manuscript |
Subject:
alg
Received: 2017/05/24 | Revised: 2020/07/8 | Accepted: 2018/09/17 | Published: 2020/01/25 | ePublished: 2020/01/25
Received: 2017/05/24 | Revised: 2020/07/8 | Accepted: 2018/09/17 | Published: 2020/01/25 | ePublished: 2020/01/25
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
