Giusto per dar credito al fatto che anche i matematici hanno una vita sociale e postano alle 23.30 il sabato sera del ponte di ferragosto e chi piu' ne ha piu' ne metta...
Partizione di grafi
Partizione di grafi
Dimostrare che un grafo finito connesso di mindegree k (ovvero tutti i vertici hanno almeno k vicini) avente un numero sufficientemente elevato di vertici (diciamo V(k)), ha una partizione $ V_1,V_2 $ dei vertici tale che i grafi indotti da questi due insiemi siano almeno di mindegree (k-1).
Giusto per dar credito al fatto che anche i matematici hanno una vita sociale e postano alle 23.30 il sabato sera del ponte di ferragosto e chi piu' ne ha piu' ne metta...
Giusto per dar credito al fatto che anche i matematici hanno una vita sociale e postano alle 23.30 il sabato sera del ponte di ferragosto e chi piu' ne ha piu' ne metta...
Ultima modifica di Catraga il 13 ago 2006, 13:29, modificato 1 volta in totale.
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Considero un grafo completo con 5 vertici (quindi k=4).
Tra le sue 2 partizioni $ V_1,V_2 $ ce ne sarà almeno una con o 2 o 1 vertice.
Il grafo indotto da questa partizione ha mindegree $ \leq 1 $.
Ma se la tesi fosse vera dovrebbero avere mindegree $ \ge k-1=3 $.
Forse ho frainteso il problema..oppure manca qualche ipotesi?
Tra le sue 2 partizioni $ V_1,V_2 $ ce ne sarà almeno una con o 2 o 1 vertice.
Il grafo indotto da questa partizione ha mindegree $ \leq 1 $.
Ma se la tesi fosse vera dovrebbero avere mindegree $ \ge k-1=3 $.
Forse ho frainteso il problema..oppure manca qualche ipotesi?
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Prendo due copie di $ \displaystyle \mathbb{Z}_n $, in ciascuna copia collego ciascun elemento con il successivo e con il precedente, inoltre collego ciascun elemento della prima copia con il corrispondente e con il successivo della prima copia.
Ottengo un grafo 4-regolare connesso, arbitrariamente grande.
Mettiamo che ho una partizione (A,B) come dici tu. Un triangolo deve stare completamente dentro A o B, altrimenti trovo un vertice che ha due archi che scappano dall'altra parte, e quindi gli restano al massimo due dalla sua, troppo pochi. Ma se ogni triangolo sta completamente in A o in B, da come è fatto il grafo esibito prima si vede subito che uno tra A e B è vuoto.
Ora, se Catraga è ancora vivo (speriamo!) e si ricorda cosa aveva in mente quel lontano sabato sera potrebbe aggiungere qualche altra ipotesi
Ottengo un grafo 4-regolare connesso, arbitrariamente grande.
Mettiamo che ho una partizione (A,B) come dici tu. Un triangolo deve stare completamente dentro A o B, altrimenti trovo un vertice che ha due archi che scappano dall'altra parte, e quindi gli restano al massimo due dalla sua, troppo pochi. Ma se ogni triangolo sta completamente in A o in B, da come è fatto il grafo esibito prima si vede subito che uno tra A e B è vuoto.
Ora, se Catraga è ancora vivo (speriamo!) e si ricorda cosa aveva in mente quel lontano sabato sera potrebbe aggiungere qualche altra ipotesi