×

zbMATH — the first resource for mathematics

Neighborhood subtree tolerance graphs. (English) Zbl 0788.05083
The notion of interval tolerance graphs is extended to so-called neighborhood subtree tolerance graphs. Some relationships between these to notions as well as to weakly triangulated graphs are examined.

MSC:
05C99 Graph theory
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Broin, M.W.; Lower, T.J., A dynamic programming algorithm for covering problems with (greedy) totally balanced constraint matrices, SIAM J. algebraic discrete methods, 7, 348-357, (1986) · Zbl 0594.90062
[2] Dearing, P.M.; Francis, R.L., A minimax location problem on a network, Transportation sci., 8, 333-343, (1974)
[3] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[4] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[5] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[6] Golumbic, M.C.; Jamison, R.E., The edge intersection graphs of paths in a tree, J. combin. theory ser. B., 38, 8-22, (1985) · Zbl 0537.05063
[7] Golumbic, M.C.; Monma, C.L., A generalization of interval graphs with tolerances, (), 321-331 · Zbl 0537.05062
[8] Golumbic, M.C.; Monma, C.L.; Trotter, W.T., Tolerance graphs, Discrete appl. math., 9, 57-170, (1984) · Zbl 0547.05054
[9] Hayward, R.B., Weakly triangulated graphs, J. combin. theory ser B, 39, 200-209, (1985) · Zbl 0551.05055
[10] Hayward, R.B.; Hoang, C.T.; Maffray, F.; Hayward, R.B.; Hoang, C.T.; Maffray, F., Optimizing weakly triangulated graphs, Graphs combin., Graphs combin., 6, 33-35, (1990), erratum in · Zbl 0744.68108
[11] M.S. Jacobson, F.R. McMorris and H.M. Mulder, An introduction to tolerance intersection graphs, in: Y. Alari et al., eds., Proceedings of the Sixth International Conference on the Theory and Applications of Graphs (Wiley, New York, to appear). · Zbl 0840.05079
[12] Jacobson, M.S.; McMorris, F.R.; Scheinerman, E.R., General results on tolerance intersection graphs, J. graph theory, 15, 573-577, (1991) · Zbl 0741.05070
[13] Monma, C.L.; Reed, B.; Trotter, W.T., Threshold tolerance graphs, J. graph theory, 12, 343-362, (1988) · Zbl 0652.05059
[14] Tamir, A., A class of balanced matrices arising from location problems, SIAM J. algebraic discrete methods, 4, 363-370, (1983) · Zbl 0557.05021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.