ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5 Khelladi, Abdelkader, USTHE, Institut de Mathématiques, Départment de Recherche Opérationnelle, Alger, Algerien Some Results on the Fiber Product of Graphs Fiber product of graphs, which is a special case of cartesian product in a category [10], generalizes the usual cross product of graphs and has been first introduced by P. Hell (1972) [4]. Let us recall that a homomorphism f from a graph G = (Y, E) into a graph H = (W, F), denoted f : G → H, is a usual maping from the set Y into W such that uv ∈ E implies f(u)f(v)inF. The fiber product of the graphs G = (Y, E) and G′ = (Y′, E′) over the homomorphisms f : G → H and f : G′ → H is the graph denoted G×_{H} G′ whose vertex set is Y (G×_{H} G′) = {(u, u′) ∈ Y ×Y′ | f(u) = f′(u′)} and where the vertices (u, u′) and (v, v′) are adjacent iff (u is adjacent to v and (u′ is adjacent to v′) 4.