There are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled using graph theoretical structures and are measured by the independence and chromatic numbers of some products of graphs, i.e. graphs arise from other graphs. It turns out that for some classes of product graphs, there exist algorithms and methods for determining these invariants. Using optimization algorithms together with some theoretical results we can establish some values and bounds on previously mentioned invariants of product graphs.
Authors
- Marcin Jurkiewicz,
- prof. dr hab. inż. Marek Kubale link open in new tab
Additional information
- Category
- Aktywność konferencyjna
- Type
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Language
- angielski
- Publication year
- 2012
