Gravier, Sylvain; Khelladi, Abdelkader On the domination number of cross products of graphs. (English) Zbl 0833.05053 Discrete Math. 145, No. 1-3, 273-277 (1995). The cross product \(G\otimes G'\) of two graphs \(G\), \(G'\) is the graph whose vertex set is the Cartesian product of the vertex sets of \(G\) and \(G'\) and in which two vertices \((u, u')\), \((v, v')\) are adjacent if and only if \(u\), \(v\) are adjacent in \(G\) and \(u'\), \(v'\) are adjacent in \(G'\). A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(x\in V(G)- D\) there exists a vertex \(y\in D\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is called the domination number of \(G\). In the paper, the domination number of the cross product \(P_n\otimes P^c_k\) of a path \(P_n\) of length \(n\) with the complement \(P^c_k\) of a path of length \(k\) is found for all values of \(n\) and \(k\). Some corollaries are stated and a conjecture is expressed saying that \(\gamma(G\otimes H)\geq \gamma(G) \gamma(H)\), where \(\gamma\) denotes the domination number. Reviewer: B.Zelinka (Liberec) Cited in 1 ReviewCited in 10 Documents MSC: 05C38 Paths and cycles 05C35 Extremal problems in graph theory Keywords:dominating set; domination number; cross product; path; complement PDFBibTeX XMLCite \textit{S. Gravier} and \textit{A. Khelladi}, Discrete Math. 145, No. 1--3, 273--277 (1995; Zbl 0833.05053) Full Text: DOI References: [1] El-Zahar, M.; Pareek, C. M., Domination number of products of graphs, Ars Combin., 31, 223-227 (1991) · Zbl 0746.05067 [2] J.F. Fink, M.S. Jacobson and L.F. Kinch, On graphs with domination number half their order, Periodica Math. Hungarica.; J.F. Fink, M.S. Jacobson and L.F. Kinch, On graphs with domination number half their order, Periodica Math. Hungarica. · Zbl 0602.05043 [3] Gernert, D., Inequalities between the domination number and the chromatique number of graph, Discrete Math., 76, 151-153 (1989) · Zbl 0674.05030 [4] Hedetniemi, S. T.; Laskar, R. C., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math., 86, 257-277 (1990) · Zbl 0733.05076 [5] Jacobson, M. S.; Kinch, L. F., On the domination number of products of graphs I, Arc Combin., 18, 33-44 (1983) · Zbl 0566.05050 [6] Jacobson, M. S.; Kinch, L. F., On the domination number of products of graphs II, J. Graph Theory, 10, 97-106 (1986) · Zbl 0584.05053 [7] Jaeger, F.; Payan, C., Relation du type Nordhauss-Gaddum pour le Nombre d’absorbtion d’un graphe simple, C.R. Acad. Sci. Paris Sér. A, 274, 728-730 (1972) · Zbl 0226.05121 [8] Marcu, D., A new upper bound for the domination number of a graph, Quar. J. Math. (Oxford) Ser., 36, 2, 221-223 (1985) · Zbl 0564.05051 [9] Vizing, V. G., The cartesian product of graphs, Vyc. Sis., 9, 30-43 (1963) · Zbl 0931.05033 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.