IJPAM: Volume 117, No. 1 (2017)

Title

ANOTHER STEP TOWARDS DETERMINING
THE HIT NUMBER OF SUBDIVIDED STARS

Authors

Jozef Bucko$^1$, Július Czap$^2$
$^{1,2}$Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Košice
Němcovej 32, 040 01 Košice, SLOVAKIA

Abstract

A total-coloring $c$ of a directed graph $G$ is called edge-distinguishing if for any two edges $e_1=u_1v_1$ and $e_2=u_2v_2$ of $G$ the associated ordered triplets $(c(u_1),c(e_1),c(v_1))$ and $(c(u_2),c(e_2),c(v_2))$ are different. The problem is to determine the minimum number of colors used in such a coloring of $G$. In this paper we investigate this parameter for directed subdivided stars.

History

Received: 2017-10-18
Revised: 2017-11-13
Published: December 12, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C15, 05C20, 05C78
Key Words and Phrases: directed graph, total-coloring

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
B. Alspach, H. Gavlas, M. Šajna, H. Verrall, Cycle decomposition IV: complete graphs and fixed length directed cycles, J. Combin. Theory Ser. A, 103 (2003), 165-208, doi: https://doi.org/10.1016/S0097-3165(03)00098-0.

2
K. Budajová, Total edge irregular number of digraphs, Acta Avionica, 21 (2011), 12-16.

3
K. Budajová, J. Czap, Hit number of directed bipartite graphs, Appl. Math. Sciences, 6 (2012), 5689-5693.

4
K. Budajová, J. Czap, Hit number of sparse subdivided stars, Appl. Math. Sciences, 6 (2012), 6753-6759.

5
O. Frank, F. Harary, M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin., 14 (1982), 241-252.

6
S.W. Golomb, How to number a graph, Graph Theory and Computing, Academic Press, New York (1972), 23-37.

7
R.L. Graham, N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Disc. Meth., 1 (1980), 382-404, doi: https://doi.org/10.1137/0601045.

8
J. Hopcroft, M.S. Krishnamoorthy, On the harmonious coloring of graphs, SIAM J. Alg. Disc. Meth., 4 (1983), 306-311, doi: https://doi.org/10.1137/0604032.

9
B. Jendroľ, Total edge-distinguishing number, Doctoral thesis, University of P.J. Šafárik (2002) (in Slovak).

10
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs, Gordon and Breach, New York (1967), 349-355.

How to Cite?

DOI: 10.12732/ijpam.v117i1.18 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 117
Issue: 1
Pages: 247 - 254


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).