Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gutiérrez, Marisa, Oubiña, Lía
Formato: Publicacion seriada
Lenguaje:Inglés
Publicado: 1994
Materias:
Matemática
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/170672
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-170672
record_format dspace
spelling I19-R120-10915-1706722024-09-26T04:09:01Z http://sedici.unlp.edu.ar/handle/10915/170672 Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54 Gutiérrez, Marisa Oubiña, Lía 1994 2024-09-25T18:54:39Z en Matemática A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. We present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This is done by demonstrating ’’local” properties of tree-clique graphs with respect to the subgraphs induced by paths of a compatible tree. Material digitalizado en SEDICI gracias a la colaboración de la Biblioteca del Departamento de Matemática de la Facultad de Ciencias Exactas (UNLP). Facultad de Ciencias Exactas Publicacion seriada Publicacion seriada http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
spellingShingle Matemática
Gutiérrez, Marisa
Oubiña, Lía
Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
topic_facet Matemática
description A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. We present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This is done by demonstrating ’’local” properties of tree-clique graphs with respect to the subgraphs induced by paths of a compatible tree.
format Publicacion seriada
Publicacion seriada
author Gutiérrez, Marisa
Oubiña, Lía
author_facet Gutiérrez, Marisa
Oubiña, Lía
author_sort Gutiérrez, Marisa
title Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
title_short Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
title_full Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
title_fullStr Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
title_full_unstemmed Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
title_sort metric characterizations of proper interval graphs and tree-clique graphs : notas de matemática, 54
publishDate 1994
url http://sedici.unlp.edu.ar/handle/10915/170672
work_keys_str_mv AT gutierrezmarisa metriccharacterizationsofproperintervalgraphsandtreecliquegraphsnotasdematematica54
AT oubinalia metriccharacterizationsofproperintervalgraphsandtreecliquegraphsnotasdematematica54
_version_ 1825910239913836544

Ejemplares similares