Constant tolerance intersection graphs of subtrees of a tree |
| |
Authors: | Robert E Jamison |
| |
Institution: | a Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-1907, USA b Econometrisch Instituut, Erasmus Universiteit Rotterdam, P.O. Box 1738, NL-3000 DR Rotterdam, Netherlands |
| |
Abstract: | A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {Sv}v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |Su∩Sv|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well. |
| |
Keywords: | Intersection graph Tolerance Chordal graph k-simplicial vertex Subtree representation Regular tree |
本文献已被 ScienceDirect 等数据库收录! |
|