Pagina 1 di 1
Grafi piuttosto asimmetrici
Inviato: 05 apr 2007, 12:05
da edriv
Sia G un grafo. Diciamo che una corrispondenza biunivoca tra i suoi vertici è un automorfismo se esiste l'arco (a,b) se e soltanto se esiste l'arco (f(a),f(b)).
Dimostrare che esistono infiniti grafi con un solo automorfismo.
Grafi rigidi
Inviato: 05 apr 2007, 14:38
da giumazz
Tra le tante possibili propongo questa:
Considero un grafo formato da un ciclo di lunghezza n a cui ad ogni vertici del ciclo attacco un cammino di diversa lunghezza (ad esempio da 1 a n). Quello che vedo è tipo un sole con tutti i raggi di lunghezze diverse.
Direi che è semplice verificare che non esistono automorfismi non banali di G e al variare di n ottengo così infiniti grafi che soddisfano la richiesta.