Helly EPT graphs on bounded degree trees : Characterization and recognition
The edge-intersection graph of a family of paths on a host tree is called an <i>EPT</i> graph. When the tree has maximum degree h, we say that the graph is [<i>h</i>, 2, 2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [<i>h...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/102919 https://www.sciencedirect.com/science/article/abs/pii/S0012365X17302571?via%3Dihub |
| Aporte de: |
| Sumario: | The edge-intersection graph of a family of paths on a host tree is called an <i>EPT</i> graph. When the tree has maximum degree h, we say that the graph is [<i>h</i>, 2, 2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [<i>h</i>, 2, 2]. In this paper, we present a family of <i>EPT</i> graphs called gates which are forbidden induced subgraphs for [<i>h</i>, 2, 2] graphs. Using these we characterize by forbidden induced subgraphs the Helly [<i>h</i>, 2, 2] graphs. As a byproduct we prove that in getting a Helly <i>EPT</i> -representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly [<i>h</i>, 2, 2] graphs based on their decomposition by maximal clique separators. |
|---|