On The Independence Number Of Some Strong Products Of Cycle-Powers

Marcin Jurkiewicz; Marek Kubale; Krzysztof Ocetkiewicz

doi:10.1515/fcds-2015-0009

.blurhash-client-img { display: none !important; }

On The Independence Number Of Some Strong Products Of Cycle-Powers

Foundations of Computing and Decision Sciences

Volume 40 (2015): Issue 2 (June 2015)

By: Marcin Jurkiewicz, Marek Kubale and Krzysztof Ocetkiewicz

Open Access

|May 2015

Abstract

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.

References

[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.
Search in Google Scholar
[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.
Search in Google Scholar
[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.
Search in Google Scholar
[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.10.37236/2598
Search in Google Scholar
[5] Codenotti, B., Gerace, I., and Resta, G. Some remarks on the Shannon capacity of odd cycles. Ars Combin. 66 (2003), 243–257.
Search in Google Scholar
[6] Hales, R. S. Numerical invariants and the strong product of graphs. J. Combinatorial Theory Ser. B 15 (1973), 146–155.10.1016/0095-8956(73)90014-2
Search in Google Scholar
[7] Körner, J., and Orlitsky, A. Zero-error information theory. IEEE Trans. Inform. Theory 44, 6 (1998), 2207–2229. Information theory: 1948–1998.10.1109/18.720537
Search in Google Scholar
[8] Lovász, L. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1 (1979), 1–7.
Search in Google Scholar
[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.1109/TIT.1956.1056798
Search in Google Scholar
[10] Vesel, A., and Žerovnik, J. Improved lower bound on the Shannon capacity of C₇. Inform. Process. Lett. 81, 5 (2002), 277–282.
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.1515/fcds-2015-0009 | Journal eISSN: 2300-3405 | Journal ISSN: 0867-6356

Journal RSS Feed

Language: English

Page range: 133 - 141

Submitted on: Oct 6, 2014

Accepted on: Feb 11, 2015

Published on: May 16, 2015

Published by: Poznan University of Technology

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

strong product,

exhaustive search algorithm,

independence number,

Shannon capacity

Related subjects:

Computer sciences,

Artificial intelligence,

Software development

© 2015 Marcin Jurkiewicz, Marek Kubale, Krzysztof Ocetkiewicz, published by Poznan University of Technology
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 40 (2015): Issue 2 (June 2015)