IJPAM: Volume 43, No. 3 (2008)

BOUNDS OF THE NUMBER OF IMP-SETS
IN EDGE-COLOURED GRAPHS

Iwona W\loch
Faculty of Mathematics and Applied Physics
Technical University of Rzeszów
ul. W. Pola 2, Rzeszów, 35-959, POLAND
e-mail: iwloch@prz.edu.pl


Abstract.We call the graph $G$ an edge-$m$-coloured if its edges are coloured with $m$ colours. A path is called monochromatic if all its edges are coloured alike. A subset $S\subset V(G)$ is independent by monochromatic paths if for every pair of different vertices from $S$ there is no monochromatic paths between them. We consider the number $NI_{mp}(G)$ of independent by monochromatic paths sets. We present several lower and upper bounds for $NI_{mp}(G)$ in terms of order, size or independence by monochromatic paths number.

Received: December 10, 2007

AMS Subject Classification: 05C69, 05C15

Key Words and Phrases: independent sets, independent by monochromatic paths sets, counting

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 43
Issue: 3