Richard Nowakowski - Multiplicative measures on graphs

Next: Suzanne Seager - Variants Up: Discrete Mathematics / Mathématiques Previous: Santosh Kabadi - Delta-matroid

Richard Nowakowski - Multiplicative measures on graphs

	RICHARD NOWAKOWSKI, Department of Mathematics, Statistics and Computing Science, Dalhousie University, Halifax, Nova Scotia B3J 3J5, Canada
	Multiplicative measures on graphs

Graph products have been used to find the `essential' value of a graph parameter (such as independence number or chromatic number) of a graph G by `multiplying' G by itself n times and examining the growth of the parameter on Gⁿ. For example, the Shannon capacity of a graph G is defined by

$\begin{displaymath} \Theta(G) = \lim_{k\rightarrow\infty}\beta(\otimes^k_{i=1}G)^{1/k}\end{displaymath}$

where $\otimes$ is the strong product of graphs and $\beta(H)$ denotes the independence number of graph H. Another such concept, introduced by Hilton, Rado & Scott, is the ultimate chromatic number of a graph G; that is

$\begin{displaymath} \chi_u(G)=\lim_{k\rightarrow\infty}\bigl(\chi(\bullet_{i=1}^kG)\bigr)^{1/k}\end{displaymath}$

here $\bullet$ denotes the lexicographic product and $\chi(H)$ the chromatic number of H.

eo@camel.math.ca