رابطۀ بین عدد و شاخص متمایزکننده با عدد قابل شناسایی یک گرا‎ف

عدد متمایز کننده d(g)، گراف g عبارت است از کوچک‌ترین عدد صحیح به‌طوری‌که گراف d دارای رنگ‌آمیزی راسی با d رنگ است که تنها تحت خودریختی همانی حفظ می‌شود. به‌صورت مشابه، شاخص متمایزکننده d'(g) از گراف g، کوچک‌ترین عدد صحیح d است که برای آن گراف دارای یک رنگ‌آمیزی یالی با d رنگ باشد که تنها تحت خودریختی همانی حفظ می‌شود. فرض کنیم g گراف همبند از مرتبۀ n≥3 و c:e(g)→{1,2,...,k} یک رنگ‌آمیزی از یال‌ها ی g است (ممکن است یال‌های مجاور، رنگ‌های یک‌سانی داشته باشند). برای هر راس v از g، کد رنگی v با توجه به رنگ‌آمیزی c ،kتایی مرتب c(v)=(a1, a2, ..., ak) است که در آن ai تعداد یال‌های به رنگ i ، k≥i≥1 ، واقع بر v است. رنگ‌آمیزی c قابل شناسایی است اگر رئوس مختلف، کدهای رنگی متفاوتی داشته باشند. عدد شناسایی det(g) گراف g، کوچک‌ترین عدد صحیح و مثبت k است که برای آن گراف g یک رنگ‌آمیزی قابل شناسایی با k رنگ داشته باشد. در این مقاله، رابطۀ بین عدد و شاخص متمایزکننده با عدد شناسایی یک گراف بررسی می‌شود. به‌ویژه، نشان می‌دهیم شاخص متمایز کننده هر گراف همبند حداکثر با عدد شناسایی آن برابر است، یعنی، det(g)≥d'(g) است.

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

IntroductionThe 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 Rubinchr('39')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) rarr; {1,2, hellip;, r}, is said to be rdistinguishing 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 byD(G)=min {r| G has a labeling that is rdistinguishing}.Similarly, the distinguishing index D prime;(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 ge; 3 and let c: E(G) rarr; {1, 2, hellip;, 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 ktuple c(v) = (a1, a2, hellip;, ak), where ai is the number of edges incident with v that are colored i (1 le; i le; 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 kcoloring.Material and methodsWe 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 discussionIn 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., Dchr('39')(G) le; det(G).ConclusionThe 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