Artículo
Miscellaneous properties of embeddings of line, total and middle graphs
Autor/es | Boza Prieto, Luis
Dávila de Tena, María Teresa Márquez Pérez, Alberto Moyano Franco, Rafael |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2001 |
Fecha de depósito | 2016-02-04 |
Publicado en |
|
Resumen | Chartrand et al. (J. Combin. Theory Ser. B 10 (1971) 12–41) proved that the line graph of a graph G is outerplanar if and only if the total graph of G is planar. In this paper, we prove that these two conditions are ... Chartrand et al. (J. Combin. Theory Ser. B 10 (1971) 12–41) proved that the line graph of a graph G is outerplanar if and only if the total graph of G is planar. In this paper, we prove that these two conditions are equivalent to the middle graph of G been generalized outerplanar. Also, we show that a total graph is generalized outerplanar if and only if it is outerplanar. Later on, we characterize the graphs G such that Full-size image (<1 K) is planar, where Full-size image (<1 K) is a composition of the operations line, middle and total graphs. Also, we give an algorithm which decides whether or not Full-size image (<1 K) is planar in an Full-size image (<1 K) time, where n is the number of vertices of G. Finally, we give two characterizations of graphs so that their total and middle graphs admit an embedding in the projective plane. The first characterization shows the properties that a graph must verify in order to have a projective total and middle graph. The second one is in terms of forbidden subgraphs. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Micellaneous properties.pdf | 243.9Kb | [PDF] | Ver/ | |