Geodesic
On independence number of strong generalized cycles product
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2010), pp. 35-40 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the present paper the independence number of generalized cycles product is investigated. A method for constructing the maximal independent set in the product graph is presented. The method is particularly based on a specific combinatorial problem, which is also solved in the paper. The main result generalizes the similar fact known for odd cycles [6].
Keywords: independence number, generalized cycles.
Mots-clés : cycles product 
@article{UZERU_2010_2_a5,
     author = {S. H. Badalyan and S. Y. Markosyan},
     title = {On independence number of strong generalized cycles product},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {35--40},
     year = {2010},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2010_2_a5/}
}
TY  - JOUR
AU  - S. H. Badalyan
AU  - S. Y. Markosyan
TI  - On independence number of strong generalized cycles product
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2010
SP  - 35
EP  - 40
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZERU_2010_2_a5/
LA  - en
ID  - UZERU_2010_2_a5
ER  - 
%0 Journal Article
%A S. H. Badalyan
%A S. Y. Markosyan
%T On independence number of strong generalized cycles product
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2010
%P 35-40
%N 2
%U http://geodesic.mathdoc.fr/item/UZERU_2010_2_a5/
%G en
%F UZERU_2010_2_a5
S. H. Badalyan; S. Y. Markosyan. On independence number of strong generalized cycles product. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2010), pp. 35-40. http://geodesic.mathdoc.fr/item/UZERU_2010_2_a5/

[1] C.E. Shannon, “The Zero-error Capacity of a Noisy Channel”, Date of Current Version: 06 January 2003, IRE Transactions on Information Theory, 2 (1956), 8–19 | DOI | MR

[2] L. Lovasz, “On the Shannon Capacity of a Graph”, Date of Current Version: 06 January 2003, IEEE Transactions on Information Theory, 25 (1979), 1–7 | DOI | MR | Zbl

[3] C. Berge, Théorie Des Graphes et Ses Applications, Dunod, Paris, 1958 | MR

[4] O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, R.I., 1962 | MR | Zbl

[5] M. Rosenfeld, “On a problem of C. E. Shannon in graph theory”, Proc. Amer. Math. Soc., 18 (1967), 315–319 | DOI | MR | Zbl

[6] R.S. Hales, “Numerical invariants and the strong product of graphs”, Combin. Theory B, 15 (1973), 146–155 | DOI | MR | Zbl

[7] S.H. Badalyan, S.E. Markosyan, “The Stable Set Number for the Strong Product of Generalized Cycles”, Transactions of IIAP of NAS RA: Mathematical Problems of Computer Science, 32, 2009, 27–34

[8] A.G. Markosyan, “On number of internal stability of simple cycles of cartesian factors”, Izv. AN Arm. SSR. Matematika, 6:5 (1971), 386–392 (in Russian) | MR

[9] A. Schrijver, Combinatorial Optimization, v. B, Springer–Verlag, Berlin–Heidelberg–New York, 2003 | Zbl

[10] M. Valencia-Pabon J. Vera, “Independence and coloring properties of direct products of some vertex-transitive graphs”, Discrete Math., 306 (2006), 2275–2281 | DOI | MR | Zbl