Minimum proper interval graphs : Notas de Matemática, 52
A graph G is a proper interval graph if there exists a mapping r from V(G) to the class of closed intervals of the real line with the properties that for distinct vertices v and w we have r(n) ∩ r(w) 7^ 0 if and only if v and w are adjacent and neither of the intervals r(v), r(w) contain the other....
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Publicacion seriada |
| Lenguaje: | Inglés |
| Publicado: |
1993
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/170313 |
| Aporte de: |
| id |
I19-R120-10915-170313 |
|---|---|
| record_format |
dspace |
| spelling |
I19-R120-10915-1703132024-09-18T04:11:11Z http://sedici.unlp.edu.ar/handle/10915/170313 Minimum proper interval graphs : Notas de Matemática, 52 Gutiérrez, Marisa Oubiña, Lía 1993 2024-09-17T17:49:35Z en Matemática A graph G is a proper interval graph if there exists a mapping r from V(G) to the class of closed intervals of the real line with the properties that for distinct vertices v and w we have r(n) ∩ r(w) 7^ 0 if and only if v and w are adjacent and neither of the intervals r(v), r(w) contain the other. We prove that for every proper interval graph G, | V(C7)| > 2c(G) — c(7C(Gi)), where c(G) is the number of cliques of G and Λ’((7) is the clique graph of G. If the equality is verified we call G a minimum proper interval graph. The main result is that the restriction to the class of minimum proper interval graphs of clique mapping G —> A(G) is a bijection (up to isomorphism) onto the class of proper interval graphs. We find the greatest clique-closed class Σ (i.e. Α(Σ) = Σ) contained in the union of the class of connected minimum proper interval graphs and the class of complete graphs . We enumerate the minimun proper interval graphs with n vertices. 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 Minimum proper interval graphs : Notas de Matemática, 52 |
| topic_facet |
Matemática |
| description |
A graph G is a proper interval graph if there exists a mapping r from V(G) to the class of closed intervals of the real line with the properties that for distinct vertices v and w we have r(n) ∩ r(w) 7^ 0 if and only if v and w are adjacent and neither of the intervals r(v), r(w) contain the other. We prove that for every proper interval graph G, | V(C7)| > 2c(G) — c(7C(Gi)), where c(G) is the number of cliques of G and Λ’((7) is the clique graph of G. If the equality is verified we call G a minimum proper interval graph. The main result is that the restriction to the class of minimum proper interval graphs of clique mapping G —> A(G) is a bijection (up to isomorphism) onto the class of proper interval graphs. We find the greatest clique-closed class Σ (i.e. Α(Σ) = Σ) contained in the union of the class of connected minimum proper interval graphs and the class of complete graphs . We enumerate the minimun proper interval graphs with n vertices. |
| 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 |
Minimum proper interval graphs : Notas de Matemática, 52 |
| title_short |
Minimum proper interval graphs : Notas de Matemática, 52 |
| title_full |
Minimum proper interval graphs : Notas de Matemática, 52 |
| title_fullStr |
Minimum proper interval graphs : Notas de Matemática, 52 |
| title_full_unstemmed |
Minimum proper interval graphs : Notas de Matemática, 52 |
| title_sort |
minimum proper interval graphs : notas de matemática, 52 |
| publishDate |
1993 |
| url |
http://sedici.unlp.edu.ar/handle/10915/170313 |
| work_keys_str_mv |
AT gutierrezmarisa minimumproperintervalgraphsnotasdematematica52 AT oubinalia minimumproperintervalgraphsnotasdematematica52 |
| _version_ |
1825276043146035200 |