Intersection representation of digraphs in trees with few leaves

DOI10.1002/(SICI)1097-0118(199912)32:4%3C340::AID-JGT3%3E3.0.CO;2-RMaRDI QIDQ4719324zbMATH OpenOpenAlexFDO

Authors Injen Lin, Douglas B. West, Malay K. Sen

Publication date 15 February 2000

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

zbMATH Keywords

digraphdominating setFerrers dimensionhost treeintersection representationleaves

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The leafage of a digraph is the minimum number of leaves in a host tree in which it has a subtree intersection representation. We discuss bounds on the leafage in terms of other parameters (including Ferrers dimension), obtaining a string of sharp inequalities.

Recommendations

• On k-trees with given leafages
• scientific article; zbMATH DE number 1185600
• Interval digraphs: An analogue of interval graphs
• The leafage of a chordal graph

Cites work

• A characterization of interval catch digraphs
• A decomposition theorem for partially ordered sets
• Algorithms for interval catch digraphs
• Circular‐arc digraphs: A characterization
• Connection digraphs and second-order line digraphs
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• On realizable biorders and the biorder dimension of a relation
• Recognizing interval digraphs and interval bigraphs in polynomial time
• The Complexity of the Partial Order Dimension Problem
• The leafage of a chordal graph

Cited in

(5)

• On the growth rate of leaf-wise intersections
• On the intractability landscape of digraph intersection representations
• Représentations en arbre de proximités relatives
• scientific article; zbMATH DE number 1185600 (Why is no real title available?)
• Directed Intersection Representations and the Information Content of Digraphs

This page was built for publication: Intersection representation of digraphs in trees with few leaves

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