TY - JOUR
T1 - Directed Intersection Representations and the Information Content of Digraphs
AU - Liu, Xujun
AU - Machado, Roberto Assis
AU - Milenkovic, Olgica
N1 - Funding Information:
The work was supported in part by the NSF STC Center for Science of Information under Grant 4101-38050, in part by the Sao Paulo Research Foundation under Grant 2015/11286-8 and Grant NSF CCF 15-26875, and in part by the UIUC Research Board under Grant RB17164.
Funding Information:
Manuscript received July 20, 2019; revised May 22, 2020; accepted September 2, 2020. Date of publication October 22, 2020; date of current version December 21, 2020. The work was supported in part by the NSF STC Center for Science of Information under Grant 4101-38050, in part by the São Paulo Research Foundation under Grant 2015/11286-8 and Grant NSF CCF 15-26875, and in part by the UIUC Research Board under Grant RB17164. This article was presented at the 2019 International Symposium on Information Theory (ISIT). (Corresponding author: Xujun Liu.) Xujun Liu is with the Department of Mathematics, University of Illinois at Urbana–Champaign, Champaign, IL 61801-3028 USA (e-mail: xliu150@illinois.edu).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2021/1
Y1 - 2021/1
N2 - 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.
AB - 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.
KW - Directed intersection number
KW - directed acyclic graph
KW - intersection representation
UR - http://www.scopus.com/inward/record.url?scp=85098555243&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85098555243&partnerID=8YFLogxK
U2 - 10.1109/TIT.2020.3033168
DO - 10.1109/TIT.2020.3033168
M3 - Article
AN - SCOPUS:85098555243
SN - 0018-9448
VL - 67
SP - 347
EP - 357
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 1
M1 - 9236641
ER -