Tu sei qui

Size and covering numbers of graphs

18 Luglio 2016
San Francesco - Via della Quarquonia 1 (Classroom 1 )
A problem of Harary is substantially generalized. A set S of vertices in a graph G is a vertex-cover if every edge of G is incident to a vertex in S; a set X of edges in G is an edge-cover if every vertex of G is incident to an edge in X. For G triangle-free, any vertex-cover S of G and any edge-cover X of G, we define injective functions phi: E_G --> S x X so the size of the graph is majorized by the product of its covering numbers. The bound is shown to be an equality iff G is a bipartite complete graph. The triangle-free graphs are of some interest as models for Brownian motion and for contact structures.