نوع مقاله : مقاله پژوهشی
نویسندگان
گروه ریاضی، دانشگاه رازی
چکیده
کلیدواژهها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
The dominance graph of the binary words, which is denoted by (Γ_n ) ⃗ , is a directed graph whose vertex set is the set of all binary words of length n. Setting B_1 (w)={1≤i≤n┤| w_i=1}, for every vertex 〖w_1 w_2…w〗_n, we join two vertices v and w by an arc if B_1 (w) is contained in B_1 (v). In this paper, we study some graphical parameters of this graph. For example, after computing the distance of every two vertices and the eccentricity of any vertex, it is proved that the diameter and the radius of the underlying graph of (Γ_n ) ⃗ equals 3 and 2, respectively. Also, it is proved that this graph has 〖 3〗^n-3(2^n-1) edges. Then we prove that both of the clique nmber and the chromatic number of the dominance graph of binary words of length n are n-1. Among other results, it is shown that the edge chromatic number and the maximum degree of vertices are equal to 2^(n-1)-2. Finally, by a combinatorial method, the independence number of this graph is determined, too.
کلیدواژهها [English]
)