On the existence of (k,k-1) - kernels in directed graphs

• Autorzy: Bród D. , Włoch A. , Włoch I.
• Języki publikacji: EN

Abstrakty

EN

We calI a subset J of vertices of a digraph D as a (k, k-1) - kerneI of D, for a fixed k ≥ 2, if all distanees between vertices from J are at Ieast k and the distance from each vertex not belonging to J to the set J is at most k - 1. Some theorems concerning the existence of (k, k - 1) - kernels are proved. The resuIts generalize the well - known Riehardson theorem [9], which says: A digraph without odd circuits has a kernel.

Słowa kluczowe

EN

kernels; distances; directed graphs

PL

jądra; odległości; grafy skierowane

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej
• Czasopismo: Journal of Mathematics and Applications
• Rocznik: 2006
• Tom: Vol. 28
• Strony: 7--12
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Bród D.

autor

Włoch A.

autor

Włoch I.

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

Bibliografia

• [1] C.Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
• [2] P.Duchet, Graphes noyau - parfaits, Ann. Discrete Math. 9(1980), 93-101.
• [3] P.Duchet, H.Meyniel, Une generelization d Theoreme de. Richardson sur l'existence de noyaux dans ie graphes orientes, Discrete Math. 43(1983), 21-27.
• [4] G-H.Fricke, S.T.Hedetniemi, M.A.Henning, Distance independent domination in graphs, Ars Combinatoria 41(3995), 33-44.
• [5] H.Galeana-Sanchez, On the existence of (k,l) - kernels in digraphs, Discrete Math. 85(1990), 99-102.
• [6] H.Galeana-Sanchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110(1992), 251-255.
• [7] M.Kwaśnik, On (k,l) - kernels in graphs and their products, The doctoral dissertation, Technical University of Wrocław, Wrocław, 1980.
• [8] M.Kwaśnik, A .Włoch, I.Włoch, Some. remarks about (k,l) - kernels in directed and undirected graphs, Discuss.Math. 13(1993), 29-37.
• [9] M.Richardson, Solution of irreflexive relations, Annals of Math. 58(1953), 573-580.