´
UNIVERSIDAD DE CONCEPCION Álgebra IV 525412
FACULTAD DE CIENCIAS FÍSICAS Y MATEMÁTICAS 2 de octubre de 2019
DEPARTAMENTO DE INGENIERÍA MATEMÁTICA Porf. C. Thraves Caro.
Listado 4
1. Usando la definición de isomorfismo de grafos, demuestre que dos grafos G y H son isomorfos si y
solo si sus complementos Ḡ y H̄ son isomorfos.
2. Demuestre que si removemos dos esquinas opuestas en un tablero de ajedrez de 8 × 8 obtenemos un
(sub)tablero que no puede ser cubierto por fichas rectangulares de tamaño 2 × 1 y 1 × 2. ¿ Podrı́a
extender el argumento para hacer una afirmación que aplique a todos los grafos bipartitos?.
3. Determine cuantos grafos no isomorfos existen que sean 4-regulares con 7 vértices.
4. Sea G un grafo k- regular con cintura igual a 4. Demuestre que G tiene al menos 2k vértices.
Determine todos los tales grafos con exactamente 2k vértices.
5. Sea G un grafo k-regular con cintura igual a 5. Demuestre que G tiene al menos k 2 + 1 vértices.
Encuentre un grafo con exactamente k 2 + 1 vértices para k = 2 y k = 3.
6. Determine valores para p y q para que Kp,q sea un grafo Euleriano.
7. Demuestre las siguientes afirmaciones o encuentre un contraejemplo.
Todo grafo Euleriano bipartito tiene un número par de aristas.
Todo grafo Euleriano con un número par de vértices tiene un número par de aristas.
8. Demuestre o encuentre un contraejemplo para la siguiente afirmación. Si G es un grafo Euleriano
con aristas e y f compartiendo un vértice, entonces G tiene una caminata Euleriana en la que e y
f aparecen de forma consecutiva.
9. Suponga que X e Y son dos conjuntos independientes maximales en un grafo G. ¿Es verdad que
X ∩ Y = ∅?
10. ¿Cual es tamaño de un conjunto independiente máximo en un camino de largo n?, ¿y en un ciclo de
largo n?.
11. Encuentre un conjunto independiente máximo en el k-cubo.
12. Sea G un grafo bipartito con bipartición U y W tal que |U | ≥ |W |. ¿Es verdad que α(G) = |U |?.
n(G)
13. Demuestre que todo conjunto independiente maximal de un grafo G contiene al menos d ∆(G)+1 e
n(G)
vértices. Luego, demuestre que para todo grafo G se cumple: α(G) ≥ ∆(G)+1 .
14. Demuestre que para todo grafo G se cumple la siguiente desigualdad:
X 1
α(G) ≥ .
d(v) + 1
v∈V (G)
15. Demuestre que X es un clique en un grafo G si y solo si X es un conjunto independiente en Ḡ (el
complemento de G). Demuestre entonces que ω(G) = α(Ḡ).
16. Suponga que ω(G) ≤ k. ¿Cual es el máximo número de aristas que G puede tener (en relación con
el número de vértices) ?.
17. ¿Es verdad que todo clique maximal en un árbol también es máximo?.
18. Sea G un grafo planar. Demuestre que ω(G) ≤ 4.
19. Encuentre una cobertura de vértices mı́nima en el k-cubo.
20. Demuestre que X es una cobertura de vértices en un grafo G si y solo si V (G) \ X es un conjunto
independiente. Deduzca que β(G) = n(G) − α(G).
21. Sea T un árbol, ¿es verdad que toda cobertura de vértices minimal en T es también mı́nima?.
22. Sea G un grafo bipartito con bipartición U y W . Sea {X, X 0 } una bipartición de U y {Y, Y 0 } una
bipartición de W . Suponga que el conjunto N (X) := ∪x∈X N (x) ⊆ Y . Demuestre que Y ∪ X 0 es una
cobertura de vértices de G.
