Seminar za računarstvo i primenjenu matematiku, 24. april 2012.

Naredni sastanak Seminara za računarstvo i primenjenu matematiku održaće se u utorak, 24. aprila 2012. u 14:15, soba 301f MI SANU.

Predavač: Alain Hertz, GERAD - Ecole des HEC & Ecole Polytechnique, Montreal, Canada

Naslov predavanja: ON THE MAXIMUM DIFFERENCE BETWEEN SEVERAL GRAPH INVARIANTS

Abstract: A graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. Although bounds on invariants have been studied for a long time by graph theorists, the past few years have seen a surge of interest in the systematic study of linear relations (or other kinds of relations) between graph invariants. We focus our attention on the difference between the maximum orders of an induced (linear) forest, an induced tree, an induced bipartite graph, and a stable set. We give upper bounds on these differences, and prove that there are tight.


 Ostavite vaš komentar 

Komentari(0)

Ostavite vaš komentar:


(opciono)
(nece biti prikazano)