Graphs and topologies on discrete sets

AbstractWe show that a graph admits a topology on its node set which is compatible with the usual connectivity of undirected graphs if, and only if, it is a comparability graph. Then, we give a similar condition for the weak connectivity of oriented graphs and show there is no topology which is compatible with the strong connectivity of oriented graphs. We also give a necessary and sufficient condition for a topology on a discrete set to be ‘representable’ by an undirected graph.fr|Nous montrons qu'un graphe admet une topologie sur l'ensemble de ses sommets compatible avec la connexité usuelle des graphes non-orientés si, et seulement si c'est un graphe de comparabilité; puis nous donnons une condition similaire pour la connexité faible des graphes orientés et montrons la non-existence d'une topologie compatible avec la connexité forte. Nous donnons également une condition nécessaire et suffisante pour qu'une topologie sur un ensemble discret soit ‘représentable’ par un graphe non-orienté