Crossing graphs of fiber-complemented graphs |
| |
Affiliation: | 1. Department of Psychology, University of Oviedo, 33009 Oviedo, Spain;2. Department of English, Santiago Apóstol Infant and Primary School, 13760 Almuradiel, Spain;3. Department of Computer Sciences and Numerical Analysis, University of Córdoba, 14071 Córdoba, Spain |
| |
Abstract: | Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|