20.500.12556/DKUM-51605 Crossing graphs of fiber-complemented graphs Križni grafi grafov zastraženih inverzov Grafi zastraženih inverzov tvorijo obsežno nedvodelno posplošitev medianskih grafov. Z uporabo določenega naravnega barvanja povezav, ki je porojeno z relacijo vzporednosti med predvlakni grafov zastraženih inverzov, vpeljemo križni graf grafa zastraženega inverza ▫$G$▫ kot graf, katerega vozlišča so barve, dve barvi pa sta sosednji, če se križata na kakem induciranem 4-ciklu v grafu ▫$G$▫. V članku pokažemo, da je graf zastraženega inverza 2-povezan natanko tedaj, ko je njegov križni graf povezan. Karakteriziramo tiste grafe zastraženih inverzov, ki imajo poln križni graf pa tudi tiste s tetivnim križnim grafom. 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. matematika teorija grafov medianski grafi zastražene množice predvlakna kartezični produkt grafov ekspanzija mathematics graph theory median graphs gated sets prefibers kartezični produkti expansion true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:59:28 2015-07-10 14:59:28 2022-05-30 03:06:35 2019-07-11 07:23:31 2008 0 0 str. 1176-1184 iss. 7 Vol. 308 2008 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 14520665 0012-365X URN:SI:UM:DK:OJI2DV3T http://dx.doi.org/10.1016/j.disc.2007.04.005 1 https://dk.um.si/Dokument.php?lang=slv&id=76165 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0