In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
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.
In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.