×

Topological additive numbering of directed acyclic graphs. (English) Zbl 1304.05119

Summary: We propose to study a problem that arises naturally from both topological numbering of directed acyclic graphs, and additive coloring (also known as lucky labeling). Let \(D\) be a digraph and \(f\) a labeling of its vertices with positive integers; denote by \(S(v)\) the sum of labels over all neighbors of each vertex \(v\). The labeling \(f\) is called topological additive numbering if \(S(u)<S(v)\) for each arc \((u,v)\) of the digraph. The problem asks to find the minimum number \(k\) for which \(D\) has a topological additive numbering with labels belonging to \(\{1,\dots,k\}\), denoted by \(\eta_t(D)\).
We characterize when a digraph has topological additive numberings, give a lower bound for \(\eta_t(D)\) and provide an integer programming formulation for our problem. We also present some families for which \(\eta_t(D)\) can be computed in polynomial time. Finally, we prove that this problem is \(\mathcal{NP}\)-hard even when its input is restricted to planar bipartite digraphs.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahadi, A.; Dehghan, A.; Kazemi, M.; Mollaahmadi, E., Computation of lucky number of planar graphs is NP-hard, Inf. Process. Lett., 112, 109-112 (2012) · Zbl 1239.05161
[2] Ahadi, A.; Dehghan, A.; Mollaahmadi, E., On the lucky labeling of graphs, Manuscript · Zbl 1239.05161
[3] Akbari, S.; Ghanbari, M.; Manaviyat, R.; Zare, S., On the lucky choice number of graphs, Graphs Comb., 1-7 (2011)
[4] Borndörfer, R.; Eisenblätter, A.; Gröstchel, M.; Martin, A., The orientation model for frequency assignment problems (April 1998), Konrad-Zuse-Zentrum Berlin, Tech. Rep. TR 98-01
[5] Boros, E.; Hammer, P. L.; Hardmann, M. E.; Shamir, R., Balancing problems in acyclic networks, Discrete Appl. Math., 49, 77-93 (1994) · Zbl 0811.90108
[6] Czerwiński, S.; Grytczuk, J.; Żelazny, W., Lucky labelings of graphs, Inf. Process. Lett., 109, 1078-1081 (2009) · Zbl 1197.05125
[7] Di Battista, G., Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice Hall · Zbl 1057.68653
[8] Du, Ding-Zhu; Ko, Ker-K.; Wang, J., Introduction to Computational Complexity (2002), Higher Education Press
[9] Gallai, T., On directed graphs and circuits, (Theory of Graphs (1968), Academic Press: Academic Press Tihany, New York), 115-118 · Zbl 0159.54403
[10] Grytczuk, J.; Bartnicki, T.; Czerwiński, S.; Bosek, B.; Matecki, G.; Żelazny, W., Additive colorings of planar graphs, Graphs Comb., 1-12 (2013)
[11] Marenco, J.; Mydlarz, M.; Severín, D., A combinatorial Benders’ approach for the lucky labeling problem, (IV Congreso de Matemática Aplicada (May 2013), Computacional e Industrial), 251-254
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.