Directed Intersection Representations and the Information Content of Digraphs

DOI10.1109/TIT.2020.3033168MaRDI QIDQ5151714zbMATH OpenFDO

Authors

Publication date 22 February 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

directed acyclic graphsupper boundsdirected intersection number (DIN)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory to circuits and networks (94C15)

Abstract: Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds.

Recommendations

• On the intractability landscape of digraph intersection representations
• Intersection-link representations of graphs
• Intersection-link representations of graphs
• On the complexity of directed intersection representation of DAGs
• Directed Information Graphs
• Information flow on directed acyclic graphs
• Intersection properties of maximal directed cuts in digraphs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• On set intersection representations of graphs
• Intersection representation of digraphs in trees with few leaves

Cited in

(3)

• On the complexity of directed intersection representation of DAGs
• On the intractability landscape of digraph intersection representations
• scientific article; zbMATH DE number 1185600 (Why is no real title available?)

This page was built for publication: Directed Intersection Representations and the Information Content of Digraphs

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