On the independence number of some strong products of cycle-powers

• Autorzy: Jurkiewicz M. , Kubale M. , Ocetkiewicz K.

Identyfikatory

DOI

10.1515/fcds-2015-0009

• Języki publikacji: EN

Abstrakty

EN

In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers α((C²₁₀)^⊠3) = 30 and α((C⁴₁₄)^⊠3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.

Słowa kluczowe

EN

strong product; exhaustive search algorithm; independence number; Shannon capacity

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2015
• Tom: Vol. 40, No. 2
• Strony: 133--141
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Jurkiewicz M.

• Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Department of Algorithms and System Modelling, Gabriela Narutowicza 11/12, 80-233 Gdansk, Poland

autor

Kubale M.

• Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Department of Algorithms and System Modelling, Gabriela Narutowicza 11/12, 80-233 Gdansk, Poland

autor

Ocetkiewicz K.

• Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Department of Algorithms and System Modelling, Gabriela Narutowicza 11/12, 80-233 Gdansk, Poland

Bibliografia

• [1] Bachoc, C., Pêcher, A., and Thiéry, A. On the theta number of powers of cycle graphs. Combinatorica 33, 3 (2013), 297–317.
• [2] Badalyan, S. H., and Markosyan, S. E. On the independence number of the strong product of cycle-powers. Discrete Math. 313, 1 (2013), 105–110.
• [3] Baumert, L. D., McEliece, R. J., Rodemich, E., Rumsey, Jr., H. C., Stanley, R., and Taylor, H. A combinatorial packing problem. In Computers in algebra and number theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970). Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108. SIAM–AMS Proc., Vol. IV.
• [4] Bohman, T., Holzman, R., and Natarajan, V. On the independence numbers of the cubes of odd cycles. Electron. J. Combin. 20, 3 (2013), Paper 10, 19.
• [5] Codenotti, B., Gerace, I., and Resta, G. Some remarks on the Shannon capacity of odd cycles. Ars Combin. 66 (2003), 243–257.
• [6] Hales, R. S. Numerical invariants and the strong product of graphs. J. Combinatorial Theory Ser. B 15 (1973), 146–155.
• [7] Körner, J., and Orlitsky, A. Zero-error information theory. IEEE Trans. Inform. Theory 44, 6 (1998), 2207–2229. Information theory: 1948–1998.
• [8] Lovász, L. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1 (1979), 1–7.
• [9] Shannon, C. E. The zero error capacity of a noisy channel. Institute of Radio Engineers, Transactions on Information Theory, IT-2, September (1956), 8–19.
• [10] Vesel, A., and Žerovnik, J. Improved lower bound on the Shannon capacity of C7. Inform. Process. Lett. 81, 5 (2002), 277–282.