Exercices de mathématiques Oraux de l'ENS : Algebre 2 by S.Francinou, H.Gianella, S.Nicolas

By S.Francinou, H.Gianella, S.Nicolas

Read or Download Exercices de mathématiques Oraux de l'ENS : Algebre 2 PDF

Best mathematics books

The Mathematics of Paul Erdos II (Algorithms and Combinatorics 14)

This is often the main finished survey of the mathematical lifetime of the mythical Paul Erd? s, the most flexible and prolific mathematicians of our time. For the 1st time, all of the major components of Erd? s' study are lined in one venture. due to overwhelming reaction from the mathematical neighborhood, the venture now occupies over 900 pages, prepared into volumes.

Extra resources for Exercices de mathématiques Oraux de l'ENS : Algebre 2

Example text

Conjecture of Berge-Duchet [3]). Is it true that (7) j (8)? (Perfect Graph Conjecture). Is it true that (6) j (8)? (Weak form of the Perfect Graph Conjecture). Is it true that the odd circuits are the only connected kernless graphs such that the removal of any arc results in a graph with a kernel? (Conjecture of Duchet, [91) References [l] C. Berge, Graphs, North-Holland Mathematical Library, Vol. 6 (North-Holland, Amsterdam, 1985) Chapter 14. [2] C. Berge, Nouvelles extensions du noyau d‘un graphe et ses applications en theorie des jeux, Publ.

The graph H obtained by removing two adjacent edges from C,, consists of an isolated vertex and a path of order n - 1. Thus, a ( H ) = 1 + a(P,,-,) = 1 + [(n - 1)/3] = 1 + [n/3] = 1 + a(C,,), whence b(C,,)S 2 in this case. Combining this with the upper bound obtained earlier, we have b(C,,) = 2 if n = 0, 2 (mod 3). Case 2. Suppose now that n = 1(mod 3). The graph H resulting from the deletion of three consecutive edges of C,, consists of two isolated vertices and a path of order n - 2. Thus, + [ ( n - 2)/3] = 2 + (n - 1)/3 = 2 + ( I d 3 1 - 1) = 1 + ~(c,,), a ( H )= 2 so that b(C,,)S 3.

If b ( G )S deg u, then b (G) s p - 1, so we suppose that b (G) > deg u. Let Eu denote the set of edges incident with u. Then a(G - E,) = a(G) and a(G - u ) = a(G) - 1. Also, if D denotes the union of all minimum dominating sets for G - u , then u is adjacent in G to no vertex of D . Hence, JE,(s p - 1 - (Dl and v t\$ D . Now, if F, denotes the set of edges from v to a vertex in D , then since u t\$ D we must have a(G - u - F , ) > a(G - u ) , or equivalently, a(G - u - F , ) > a(G) - 1. Thus a((; - (E, U 4))> a(G) and we see that b ( G )S IEU u F,I = lEUl+ lFvl S ( p - 1 - IDl)+ ID1 = p - 1.