DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 151-155
DOI: 10.7151/dmgt.1030

A NOTE ON STRONG AND CO-STRONG PERFECTNESS OF THE X-JOIN OF GRAPHS

Alina Szelecka

Institute of Mathematics, Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland

e-mail: A.Szelecka@im.uz.zgora.pl

Andrzej Włoch

Department of Mathematics, Technical University of Rzeszów
W. Pola 2, 35-359 Rzeszów, Poland

e-mail: awloch@ewa.prz.rzeszow.pl

Abstract

Strongly perfect graphs were introduced by C. Berge and P. Duchet in [1]. In [4], [3] the following was studied: the problem of strong perfectness for the Cartesian product, the tensor product, the symmetrical difference of n, n ≥ 2, graphs and for the generalized Cartesian product of graphs. Co-strong perfectness was first studied by G. Ravindra andD. Basavayya [5]. In this paper we discuss strong perfectness and co-strong perfectness for the generalized composition (the lexicographic product) of graphs named as the X-join of graphs.

Keywords: strongly perfect graphs, co-strongly perfect graphs, the X-join of graphs.

1991 Mathematics Subject Classification: 05C75, 05C60.

References

[1] C. Berge and P. Duchet, Strongly perfect graphs, Ann. Disc. Math. 21 (1984) 57-61.
[2] M. Borowiecki and A. Szelecka, One factorizations of the generalized Cartesian product and of the X-join of regular graphs, Discussiones Mathematicae 13 (1993) 15-19.
[3] M. Kwaśnik and A. Szelecka, Strong perfectness of the generalized Cartesian product of graphs, accepted for publication in the special issue of Discrete Math., devoted to the Second Krako w Conference on Graph Theory, Zakopane 1994.
[4] E. Mandrescu, Strongly perfect product of graphs, Czech. Math. Journal, 41 (116) (1991) 368-372.
[5] G. Ravindra and D. Basavayya, Co-strongly perfect bipartite graphs, Jour. Math. Phy. Sci. 26 (1992) 321-327.