Topological additive numbering of directed acyclic graphs

DOI10.1016/J.IPL.2014.09.011zbMATH Open1304.05119arXiv1310.4141OpenAlexW2052876314MaRDI QIDQ477623FDOQ477623

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

Publication date: 9 December 2014

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

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.

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

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

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)

Cites Work

• Lucky labelings of graphs
• Title not available (Why is that?)
• Computation of lucky number of planar graphs is NP-hard
• Title not available (Why is that?)
• Balancing problems in acyclic networks

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)