The Stable Set Number for the Strong Product of Generalized Cycles
Abstract
The strong product of an odd cycle and a generalized cycle and the strong product of two generalized cycles are investigated. For both cases a method is given to construct a stable set of vertices in product graph to achieve the known upper bound α(GxH) ≤ ρ(G)xα(H) in case some conditions hold. For the stable set number of strong product of generalized cycles a lower bound is found.
References
C.E. Shannon, “The zero-error capacity of a noisy channel", Trans. 1956 Symp. Information Theory, Inst. Radio Eng. IT-2, 8-19.
L.Lovasz, “On the Shannon capacity of a graph", IEEE Transactions on Information Theory IT-25, pp. 1-7, 1979.
O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, R.I., 1962.
M. Rosenfeld, “On a problem of C.E. Shannon in graph theory", Proc. Amer. Math. Soc., pp. 315-319, 1967.
R.S. Hales, “Numerical invariants and the strong product of graphs", Combin. Theory (B) 15, pp. 146-155, 1973.
A.G. Markosyan, “The internal stability number in a Cartesian product of simple cycles", Izvestiya Akademii Nauk Armyanskoy SSR. Seriya Matematika 6:5, pp. 386-392, 1971.
A. Schrijver, Combinatorial Optimization. Berlin-Heidelberg-NewYork, Springer-Verlag, 2003.
C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
