On a conjecture concerning helly circle graphs
|
Descargar SCORM
¡Sea el primero en solicitar este recurso!
Para poder solicitar este recurso debe identificarse como usuario de la biblioteca
|
| |
Ver
Detalles del recurso
|
|
|
On a conjecture concerning helly circle graphs
|
| Id. |
518024 |
| Idioma |
inglés
|
| Titulo |
On a conjecture concerning helly circle graphs |
| Autor(es) |
Durán,Guillermo
Gravano,Agustín
Groshaus,Marina
Protti,Fábio
Szwarcfiter,Jayme L.
|
| Localización |
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382003000100016
|
| Versión |
1.0 |
| Estado |
Final
|
| Descripción |
We say that G is an e-circle graph if there is a bijection between its vertices and straight lines on the cartesian plane such that two vertices are adjacent in G if and only if the corresponding lines intersect inside the circle of radius one. This definition suggests a method for deciding whether a given graph G is an e-circle graph, by constructing a convenient system S of equations and inequations which represents the structure of G, in such a way that G is an e-circle graph if and only if S has a solution. In fact, e-circle graphs are exactly the circle graphs (intersection graphs of chords in a circle), and thus this method provides an analytic way for recognizing circle graphs. A graph G is a Helly circle graph if G is a circle graph and there exists a model of G by chords such that every three pairwise intersecting chords intersect at the same point. A conjecture by Durán (2000) states that G is a Helly circle graph if and only if G is a circle graph and contains no induced diamonds (a diamond is a graph formed by four vertices and five edges). Many unsuccessful efforts - mainly based on combinatorial and geometrical approaches - have been done in order to validate this conjecture. In this work, we utilize the ideas behind the definition of e-circle graphs and restate this conjecture in terms of an equivalence between two systems of equations and inequations, providing a new, analytic tool to deal with it.
|
| Tipo |
text/html
|
| Palabras clave |
circle graph
|
| Tipo de recurso |
journal article
|
| Tipo de Interactividad |
Expositivo
|
| Nivel de Interactividad |
muy bajo
|
| Audiencia |
Estudiante
Profesor
Autor
|
| Estructura |
Atomic |
| Coste |
no
|
| Copyright |
sí
|
| Formatos |
text/html
|
| Requerimientos técnicos |
Browser: Any
|
| Fecha de contribución |
23-may-2005 |
| Contacto |
|
|
|
|
|
Valoración de los usuarios
No hay ninguna valoración para este recurso. Sea el primero en
valorar este recurso.
|
|
|
|
