Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Binary Tree
Chordal Graph
Intersection Graphs
Related Publications
(1)
Constant tolerance intersection graphs of subtrees of a tree
Subscribe
Academic
Publications
Tolerance intersection graphs on binary trees with constant tolerance 3
Tolerance intersection graphs on binary trees with constant tolerance 3,10.1016/S0012365X(99)002319,Discrete Mathematics,Robert E. Jamison,Henry Mar
Edit
Tolerance intersection graphs on binary trees with constant tolerance 3
(
Citations: 14
)
BibTex

RIS

RefWorks
Download
Robert E. Jamison
,
Henry Martyn Mulder
A
chordal graph
is the intersection graph of a family of subtrees of a tree, or, equivalently, it is the (edge)intersection graph of leafgenerated subtrees of a full binary tree. In this paper, a generalization of chordal graphs from this viewpoint is studied: a graph G=(V,E) is representable if there is a family of subtrees {Sv}v∈V of a binary tree, such that uv∈E if and only if Su∩Sv⩾3.
Journal:
Discrete Mathematics  DM
, vol. 215, no. 13, pp. 115131, 2000
DOI:
10.1016/S0012365X(99)002319
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
linkinghub.elsevier.com
)
More »
Citation Context
(4)
...One of them is new, whereas the others also appear in [34] and [
25
], but were not analyzed in detail in these papers...
...The ksimplicial graphs are already defined in [
25
] and [34], whereas in the latter paper they are called ˜...
Frank Kammer
,
et al.
Approximation Algorithms for Intersection Graphs
...In [11], [
12
], the intersection representation of a graph on a tree is generally defined as follows...
...In [11], [
12
], a function f(h, s, t) is given, such that for any n>f (h, s, t), the K2,n graph has no (h, s, t)representation...
...Jamison and Mulder [11], [
12
] have investigated the intersection graph of subtrees of a tree by studying the representations of the complete bipartite graph K2,n...
Elad Cohen
,
et al.
What Is between Chordal and Weakly Chordal Graphs?
...In [12,
13
], Jamison and Mulder define a (h,s,p)representation, which consists of a collection of subtrees of a tree, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum Representations of Edge Intersection Graphs of Paths in a Tree 89...
...The terminology of an orthodox representation is used in Jamison and Mulder[12,
13
], who cite an earlier result of McMorris and Scheinerman [14], namely, (i) , (ii) , (iii) in Theorem 1.8 below, and prove in [12] the remaining equalities...
...Theorem 1.8 [12,
13
, 14] The following statements are equivalent: (i) A graph G is chordal, (ii) G has a (3,3,1)representation, (iii) G has an orthodox (3,3,1)representation, (iv) G has a (3,3,2)representation, (v) G has an orthodox (3,3,2)representation...
Martin Charles Golumbic
,
et al.
Representations of Edge Intersection Graphs of Paths in a Tree
...In [12,
13
], Jamison and Mulder have placed these tolerance models into a more general setting...
...An (h; s; p)subtree representation consists of a collection of subtrees of a tree, such that (i) the maximum degree of T is at most h (ii) every subtree has maximum degree at most s (iii) there is an edge between two vertices in the graph if the corresponding subtrees have at least p vertices in common in T. The class [3;3;3] is studied in [
13
]...
Martin Charles Golumbic
,
et al.
The recognition of kEPT graphs
Sort by:
Citations
(14)
Approximation Algorithms for Intersection Graphs
(
Citations: 2
)
Frank Kammer
,
Torsten Tholey
,
Heiko Voepel
Conference:
Approximation Algorithms for Combinatorial Optimization  APPROX
, pp. 260273, 2010
Elimination Graphs
(
Citations: 3
)
Yuli Ye
,
Allan Borodin
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 774785, 2009
Intersection models of weakly chordal graphs
Martin Charles Golumbic
,
Marina Lipshteyn
,
Michal Stern
Journal:
Discrete Applied Mathematics  DAM
, vol. 157, no. 9, pp. 20312047, 2009
The kedge intersection graphs of paths in a tree
(
Citations: 9
)
Martin Charles Golumbic
,
Marina Lipshteyn
,
Michal Stern
Journal:
Discrete Applied Mathematics  DAM
, vol. 156, no. 4, pp. 451461, 2008
Equivalences and the complete hierarchy of intersection graphs of paths in a tree
(
Citations: 3
)
Martin Charles Golumbic
,
Marina Lipshteyn
,
Michal Stern
Journal:
Discrete Applied Mathematics  DAM
, vol. 156, no. 17, pp. 32033215, 2008