Directed Intersection Representations and the Information Content of Digraphs

Xujun Liu, Roberto Assis Machado, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number9236641
Pages (from-to)347-357
Number of pages11
JournalIEEE Transactions on Information Theory
Volume67
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • Directed intersection number
  • directed acyclic graph
  • intersection representation

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Directed Intersection Representations and the Information Content of Digraphs'. Together they form a unique fingerprint.

Cite this