Mathematical Researches

fa رابطۀ بین عدد و شاخص متمایزکننده با عدد قابل شناسایی یک گرا‎ف The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number جبر alg مقاله مستقل Original Manuscript عدد متمایز کننده <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image001.png" > ، گراف &lrm;&lrm;&lrm;&lrm;&lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm;&rlm; &lrm;&lrm;عبارت است از کوچک‌ترین عدد صحیح &lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image003.png" > &lrm;&lrm; به‌طوری‌که گراف &lrm;&lrm;&lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm; دارای رنگ‌آمیزی رأسی با &lrm;&lrm;&lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image003.png" > &lrm;&lrm; رنگ است که تنها تحت خودریختی همانی حفظ می‌شود. به‌صورت مشابه، شاخص متمایزکنند&lrm;ه <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image004.png" > &lrm; از گرا&lrm;ف &lrm;&lrm;&lrm;G&lrm;، کوچک‌ترین عدد صحیح &lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image003.png" >  است که برای آن گراف &lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" >  دارای یک رنگ‌آمیزی یالی با &lrm;&lrm;&lrm;d&lrm;&lrm; رنگ باشد &lrm;&lrm;که تنها تحت خودریختی همانی حفظ می‌شود. فرض کنیم &lrm;&lrm;&lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm; گراف همبند از مرتبۀ &lrm;&lrm;&lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image005.png" > &lrm;&lrm; و <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image006.png" >  یک رنگ‌آمیزی از یال‌ها&lrm;ی &lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" >  است (ممکن است یال‌های مجاور، رنگ‌های یک‌سانی داشته باشند). برای هر رأ&lrm;س &lrm;&lrm;&lrm;v&lrm;&lrm; ا&lrm;ز <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm;، کد رنگی &lrm;&lrm;v&lrm;&lrm; با توجه به&lrm;&lrm; رنگ‌آمیزی &lrm;&lrm;&lrm;&lrm;&lrm;c&lrm;&lrm;&lrm;،k-تایی مرتب&lrm;&lrm; &lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image007.png" >  است که در آن &lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image008.png" > &lrm;&lrm; تعداد یال‌های به رنگ&lrm;&lrm; &lrm;&lrm;&lrm;&lrm;i&lrm;&lrm;، &lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image009.png" > &lrm;&lrm;، واقع بر &lrm;&lrm;&lrm;&lrm;v&lrm;&lrm;&lrm; است. رنگ‌آمیز&lrm;ی &lrm;&lrm;&lrm;c&lrm;&lrm; قابل شناسایی است اگر رئوس مختلف، کدهای رنگی متفاوتی داشته باشند. عدد شناسایی   <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image010.png" > &lrm; گراف &lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm;، کوچک‌ترین عدد صحیح و مثبت k&lrm;&lrm; است که برای آن گرا&lrm;ف &lrm;&lrm;&lrm; <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.png" > &lrm;&lrm; یک رنگ‌آمیزی قابل شناسایی با&lrm; k&lrm; رنگ داشته باشد. در این مقاله، رابطۀ بین عدد و شاخص متمایزکننده با عدد شناسایی یک گراف بررسی می‌شود. به‌ویژه، نشان می‌دهیم شاخص متمایز کننده هر گراف همبند حداکثر با عدد شناسایی آن برابر است، یعنی،  <img alt="" chromakey="white" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image011.png" >  است. 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 <a href="https://en.wikipedia.org/wiki/Graph_theory" title="Graph theory">graph theory</a>, graph coloring is a special case of <a href="https://en.wikipedia.org/wiki/Graph_labeling" title="Graph labeling">graph labeling</a>; it is an assignment of labels traditionally called "colors" to elements of a <a href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent <a href="https://en.wikipedia.org/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> share the same color; this is called a vertex coloring. Similarly, an <a href="https://en.wikipedia.org/wiki/Edge_coloring" title="Edge coloring">edge coloring</a> 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 <a href="https://en.wikipedia.org/wiki/Sudoku" title="Sudoku">Sudoku</a>. 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&lrm; automorphism&lrm;. 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 <img alt="" height="20" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif" width="43" > and prove that <img alt="" height="20" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image004.gif" width="107" >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. <ul> <li>An upper bound for D(G) by the detection number of its spanning trees.</li> <li>The upper and lower bounds for the distinguishing number by the detection number of a graph.</li> <li>Every detectable coloring is a distinguishing labeling of the edges of a graph.</li> <li>The upper bounds for the distinguishing index by the detection number of a graph.<a href="./files/site1/files/61/11.pdf">./files/site1/files/61/11.pdf</a></li> </ul> عدد متمایز کننده, شاخص متمایز کننده, عدد شناسایی. distinguishing number, distinguishing index, detection number. 109 118 http://mmr.khu.ac.ir/browse.php?a_code=A-10-81-1&slc_lang=fa&sid=1 Saeid Alikhani سعید علیخانی alikhani@yazd.ac.ir 10031947532846003593 10031947532846003593 Yes Yazd University ‎ دانشگاه یزد، دانشکدۀ ریاضی Samaneh Soltani سمانه سلطانی s.soltani1979@gmail.com 10031947532846003594 10031947532846003594 No Yazd University ‎ دانشگاه یزد، دانشکدۀ ریاضی