Academic
Publications
Tolerance intersection graphs on binary trees with constant tolerance 3

Tolerance intersection graphs on binary trees with constant tolerance 3,10.1016/S0012-365X(99)00231-9,Discrete Mathematics,Robert E. Jamison,Henry Mar

Tolerance intersection graphs on binary trees with constant tolerance 3   (Citations: 14)
BibTex | RIS | RefWorks Download
A chordal graph is the intersection graph of a family of subtrees of a tree, or, equivalently, it is the (edge-)intersection graph of leaf-generated 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. 1-3, pp. 115-131, 2000
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.
    • ...One of them is new, whereas the others also appear in [34] and [25], but were not analyzed in detail in these papers...
    • ...The k-simplicial graphs are already defined in [25] and [34], whereas in the latter paper they are called ˜...

    Frank Kammeret 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 Cohenet 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 Golumbicet 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 Golumbicet al. The recognition of kEPT graphs

Sort by: