Topological additive numbering of directed acyclic graphs

DOI10.1016/J.IPL.2014.09.011MaRDI QIDQ477623zbMATH OpenOpenAlexFDO

Authors Javier Marenco, Marcelo Mydlarz, D. Severín

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.4141

zbMATH Keywords

computational complexitydirected acyclic graphslucky labelingadditive coloringtopological additive numbering

Mathematics Subject Classification ID

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

Abstract: 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 emph{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,ldots,k$, denoted by $et{a}_t(D)$. We characterize when a digraph has topological additive numberings, give a lower bound for $et{a}_t(D)$, and provide an integer programming formulation for our problem, characterizing when its coefficient matrix is totally unimodular. We also present some families for which $et{a}_t(D)$ can be computed in polynomial time. Finally, we prove that this problem is p-Hard even when its input is restricted to planar bipartite digraphs.

Recommendations

• On computing the number of topological orderings of a directed acyclic graph
• Topological integer additive set-sequential graphs
• On topological numbers of graphs
• Acyclic numbers of graphs
• Topological Decomposition of Directed Graphs
• Counting directed acyclic and elementary digraphs
• Topological orderings of weighted directed acyclic graphs
• On Counting Homomorphisms to Directed Acyclic Graphs
• scientific article; zbMATH DE number 846942
• Counting acyclic orderings in directed acyclic graphs

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Balancing problems in acyclic networks
• Computation of lucky number of planar graphs is NP-hard
• Lucky labelings of graphs

Cited in

(3)

• On the additive chromatic number of several families of graphs
• Topological orderings of weighted directed acyclic graphs
• Topological integer additive set-sequential graphs

This page was built for publication: Topological additive numbering of directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477623)