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

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

ALIKHANI SAEID; SOLTANI SAMANEH

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: MATHEMATICAL RESEARCHES Year:2020 | Volume:6 | Issue:1 Page(s): 109-118

Download Full-Text

Persian Verion

View:

486

Download:

Cites:

Information Journal Paper

Title

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

Author(s)

ALIKHANI SAEID | SOLTANI SAMANEH | Issue Writer Certificate

Keywords

distinguishing numberQ1

distinguishing indexQ1

detection numberQ1

Abstract

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 D'(G) ≤ det(G). 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.

Cites

No record.

References

No record.

Cite

APA: Copy

ALIKHANI, SAEID, & SOLTANI, SAMANEH. (2020). The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number. MATHEMATICAL RESEARCHES, 6(1 ), 109-118. SID. https://sid.ir/paper/386966/en

Vancouver: Copy

ALIKHANI SAEID, SOLTANI SAMANEH. The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number. MATHEMATICAL RESEARCHES[Internet]. 2020;6(1 ):109-118. Available from: https://sid.ir/paper/386966/en

IEEE: Copy

SAEID ALIKHANI, and SAMANEH SOLTANI, “The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number,” MATHEMATICAL RESEARCHES, vol. 6, no. 1 , pp. 109–118, 2020, [Online]. Available: https://sid.ir/paper/386966/en

Related Journal Papers