×

Independence numbers of product graphs. (English) Zbl 0811.05033

Authors’ abstract: We present a greedy algorithm which leads to an improvement over Vizing’s lower bound on the independence number of a Cartesian-product graph. We further obtain certain bounds on independence numbers of Kronecker-product and strong-product graphs.

MSC:

05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Miller, D. J., The categorical product of graphs, Canad. J. Math, 20, 1511-1521 (1968) · Zbl 0167.21902
[2] Harary, F., Graph Theory (1969), Addison-Wesley · Zbl 0797.05064
[3] Computer Elements and Systems, Vol. 1-9, 352-365 (1966), Israel Program for Scientific Translation, Jerusalem
[4] Shannon, C. E., The zero-error capacity of a noisy channel, IRE Trans. Information Theory, IT-2, 8-19 (1956)
[5] Lovasz, L., On the Shannon capacity of a graph, IEEE Trans. Information Theory, IT-25, 1-7 (1979) · Zbl 0395.94021
[6] Rosenfeld, M., On a problem of C.E. Shannon in graph theory, Proc. Am. Math. Soc., 18, 315-319 (1967) · Zbl 0147.42801
[7] Sonnemann, E.; Kraft, O., Independence numbers of product graphs, J. Combin. Theory B, 17, 133-142 (1974) · Zbl 0305.05113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.