Vertex-transitivity e proprietà di edge swapping

Aug 18 2020

Un grafico semplice e non orientato$G=(V,E)$si dice transitivo al vertice se per qualsiasi$a,b\in V$c'è un isomorfismo grafico$\varphi:V\to V$tale che$\varphi(a) = b$.

Diciamo che un grafico$G=(V,E)$ha la proprietà di scambio di spigoli se per qualsiasi spigolo$e = \{x,y\} \in E$c'è un isomorfismo grafico$\varphi:V\to V$tale che$\varphi(x) = y$e$\varphi(y) = x$.

Una di queste proprietà implica l'altra per i grafi connessi?

Risposte

2 DánielG. Aug 20 2020 at 00:36

Come dice Ekin nei commenti, per i grafi connessi la proprietà di scambio di spigoli implica la transitività dei vertici tramite la composizione degli scambi di spigoli lungo un percorso.

L'altra implicazione non è vera. Un grafo è simmetrico se per qualsiasi coppia di vertici adiacenti$(u_1,v_1)$e$(u_2,v_2)$c'è un invio di automorfismo$u_1$a$u_2$e$v_1$a$v_2$. Si noti che questo è più forte della transitività del bordo, perché possiamo specificare il modo in cui i punti finali del bordo si mappano ai punti finali dell'altro bordo (quindi, tale grafico è anche chiamato arc-transitive ).

Ora Wikipedia afferma che ci sono grafi transitivi al vertice e transitivi al bordo ma non simmetrici. Tale grafo non può avere la proprietà di scambio di archi, altrimenti potremmo inviare qualsiasi coppia di vertici adiacenti a un'altra coppia di vertici adiacenti utilizzando la transitività di bordo e quindi scambiando l'arco, se necessario.

Per quanto riguarda la connessione tra transitività di vertice, transitività di bordo e proprietà di scambio di bordo: il grafico del prisma triangolare ha la proprietà di scambio di bordo e quindi è transitivo di vertice, ma non è transitivo di bordo. Non riesco a pensare a un grafico che sia transitivo di vertice ma non transitivo di bordo né abbia la proprietà di scambio di bordo dalla parte superiore della mia testa, anche se sarei sorpreso se non esistessero tali grafici.