گراف تسلط کلمات دودویی

نوع مقاله: مقاله پژوهشی

نویسندگان

گروه ریاضی، دانشگاه رازی

چکیده

گراف تسلط کلمات دودویی، گرافی است جهت‌دار با مجموعه رئوس تمام کلمات دودویی به طول n که با نماد (Γ_n ) ⃗ نشان داده می‌شود، برای هر رأس دلخواه w=w_1 w_2⋯w_n از آن قرار می‌دهیم B_1 (w)={1≤i≤n|w_i=1} و دو رأس v و w را با پیکان جهت‌دار v→w به هم وصل می‌کنیم هرگاه داشته باشیم B_1 (w)⊆B_1 (v). در این مقاله، به مطالعه و محاسبه برخی پارامترهای این گراف می‌پردازیم؛ به عنوان مثال، پس از محاسبه فاصله هر دو رأس و نیز انحراف از مرکز هر رأس، ثابت می‌شود که قطر گراف زمینه (Γ_n ) ⃗ برابر 3 و شعاع آن برابر 2 است. همچنین ثابت خواهد شد که این گراف دارای تعداد 〖 3〗^n-3(2^n-1)یال است. در ادامه نشان خواهیم داد که عدد خوشه‌ای و عدد رنگی رأسی گراف تسلط کلمات دودویی با طول n هردو برابر n-1 هستند. در دیگر نتایج، ثابت می‌شود که عدد رنگی یالی این گراف و ماکزیمم درجه رئوس آن مساوی 2^(n-1)-2 هستند. در پایان، عدد استقلال این گراف نیز به روش‌ ترکیبیاتی محاسبه خواهد شد

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Dominance Graph of Binary Words

نویسندگان [English]

  • Farzad Shaveisi
  • Soheila Nasouri
Department of Mathematics, Faculty of Science, Razi University, Kermanshah, Iran
چکیده [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]

  • Dominance graph of Binary words
  • Diameter
  • Girth
  • Radius
  • Chromatic number
  • Independence number
[1] Beineke, L.W. and Wilson, B.J. (1978), Selected Topics in Graph Theory, Academic Press Inc., London.

[2] Farzan, A. and Ian Munro, J. (2013), Succident encoding of arbitrary graphs, Theoretical Computer Science, 513, 38-52.

[3] Fish, W., Key, J.D., and Mwambene, E. (2010), Binary codes from the line graph of the n-cube, Journal of Symbolic Computation, 45, 800-812.

[4] Foucaud, F., Gravier, J., Naserasr, R., Parreau, A. and Valecov, P. (2013), Identifying codes in line graphs, Journal of Graph Theory, 73(4), 425-448.

[5] Gadouleau, M. (2018), On the possible values of the entropy of undirected graphs, Journal of Graph Theory, 88(2), 302-311.

[6] Grady, A. and Poznanovic, S. (2018), Graphical Mahonian statistics on words. The electronic journal of combinatorics, 25(1), #P1.1.

[7] Jukna, S. (2001), Extermal combinatorics with applications in computer science, Texts in theoretical computer science, Springer.

[8] Kitaev, S., Lozin, V. (2015), Words and Graphs, Springer Cham Heidelberg New York.

[9] Leibniz, G. (1703), Explication de l’Arithmétique Binaire (Explanation of Binary Arithmetic). Mathematical Writings VII, Gerhardt, 223.

[10] Millo, J. -V. and Simone, R. de (2012), Periodic scheduling of marked graphs using balanced binary words, Theoretical Computer Science, 458, 113-130.

[11] Rawlings, D. (1981), The r-major index, J. Combin. Theory Ser. A, 31(2), 175-183.

[12] West,D.B. (2001), Introductionto to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River.