Search
Abstract
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 (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- 5th International Interdisciplinary Technical Conference of Young Scientists InterTech 2012 : proceedings, Poznań, Poland, 16-18 May 2012 strony 253 - 255
- Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- Jurkiewicz M., Kubale M.: Product Graph Invariants with Applications in the Theory of Information// 5th International Interdisciplinary Technical Conference of Young Scientists InterTech 2012 : proceedings, Poznań, Poland, 16-18 May 2012/ Poznań: Politechnika Poznańska, 2012, s.253-255
- Verified by:
- Gdańsk University of Technology
seen 138 times
Recommended for you
On the super domination number of lexicographic product graphs
- M. Dettlaff,
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ
- + 1 authors