Graphs and topologies on discrete sets

✍ Scribed by Pascal Préa

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 597 KB
• Volume: 103
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90269-l

✦ Synopsis

PrCa, P., Graphs and topologies on discrete sets, Discrete Mathematics 103 (1992) 189-197.

We 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.

R&sum6

Nous montrons qu'un graphe admet une topologie sur I'ensemble de ses sommets compatible avec la connexit6 usuelle des graphes non-orient& si, et settlement si c'est un graphe de comparabilitt; puis nous donnons une condition similaire pour la connexite faible des graphes orient& et montrons la non-existence d'une topologie compatible avec la connexite forte. Nous donnons Cgalement une condition necessaire et suffisante pour qu'une topologie sur un ensemble discret soit 'representable' par un graphe non-oriente.