Zykov sums of digraphs with diachromatic number equal to its harmonious number | [Discrete Mathematics Letters • 2024]

Author(s):

1. Mika Olsen: Departamento de Matem´aticas Aplicadas y Sistemas, UAM-Cuajimalpa, Mexico City, Mexico

2. Christian Rubio-Montiel: Divisio ́n de Matem a ́ticas e Ingenier ́ıa, FES Acatl a ́n, Universidad Nacional Auto ́noma de Me ́xico,Naucalpan,Mexico

3. Alejandra Silva-Ramirez: Posgrado de Ciencias Naturales e Ingenier ́ıa, UAM-Cuajimalpa,Mexico City,Mexico

Abstract:

The dichromatic number and the diachromatic number are generalizations of the chromatic number and the achromatic number for digraphs considering acyclic colorings. In this paper, we determine the diachromatic number of digraphs arising from the Zykov sum of digraphs that accept a complete k-coloring with k = 1+p1+4m for a suitable m. As a consequence, 2 the diachromatic number equals the harmonious number for every digraph in this family. In particular, we determine the diachromatic number of digraphs arising from the Zykov sum of Hamiltonian factorizations of complete digraphs over a suitable digraph. We also obtain the equivalent results for graphs. Furthermore, we determine the achromatic number for digraphs arising from the generalized composition in terms of the thickness of complete graphs. Finally, we extend some results on the dichromatic number of Zykov sums of tournaments to the class of digraphs that are not tournaments and apply them, and the results obtained for the diachromatic number, to the problem of the existence of a digraph with dichromatic number r and diachromatic number t for some particular cases with 2 r t.

Page(s): 7-12

DOI: 10.47443/dml.2023.214

Published: Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Keywords:

factorization , diachromatic number , dichromatic number , achromatic number , harmonious number , products of digraphs

References:

[1] Araujo-Pardo G.,Montellano-Ballesteros J. J.,Olsen M.,Rubio-Montiel C. .2018 .The diachromatic number of digraphs, Electron. , 25(3) : 51.

[2] Araujo-Pardo G.,Montellano-Ballesteros J. J.,Olsen M.,Rubio-Montiel C. .2021 .Achromatic number, achromatic index and diachromatic number of circulant graphs and digraphs. Discuss. Math. Graph Theory, 41 : 713-724.

[3] Bhave V. N. .1979 .On the pseudoachromatic number of a graph, Fund. , 102 : 159-164.

[4] Chartrand G.,Zhang P. .2009 .. , : .

[5] Edwards K. J. .2013 .Harmonious chromatic number of directed graphs. Discrete Appl. Math, 161(3) : 369-376.

[6] Hegde S. M.,Castelino L. P. .2011 .Further results on harmonious colorings of digraphs. AKCE Int. J. Graphs Comb, 8(2) : 151-159.

[7] Hegde S. M.,Castelino L. P. .2015 .. Ars Combin, 119 : 339-352.

[8] Llano B.,Olsen M. .2017 .Disproof of a conjecture of Neumann-Lara, Electron. , 24(4) : P4.

[9] Meyer W. .1973 .. Amer. Math. Monthly, 80 : 920-922.

[10] Neumann-Lara V. .1982 .The dichromatic number of a digraph. J. Combin. Theory Ser. B, 33(3) : 265-270.

[11] Neumann-Lara V. .2000 .Dichromatic number, circulant tournaments and Zykov sums of digraphs. Discuss. Math. Graph Theory, 20(2) : 197-207.

[12] A. M. Odlyzko H. S.,Wilf H. S. .1991 .Functional iteration and the Josephus problem. , 33(2) : 235-240.

Citations

Downloads

Views