Dominance Graph of Binary Words

Document Type : Original Paper

Authors

1 Department of Mathematics, Faculty of Science, Razi University, Kermanshah, Iran

2 Department of Mathematics, Razi University, Kermanshah, Iran

Abstract

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.

Keywords

Main Subjects

References

[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.
Journal of Advanced Mathematical Modeling
Volume 9, Issue 2
September 2019
Pages 191-205

Files

History

  • Receive Date: 05 August 2018
  • Revise Date: 28 April 2019
  • Accept Date: 27 June 2019

Share

How to cite

Statistics