On the domination number of cross products of graphs (Q1901047): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:53, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the domination number of cross products of graphs |
scientific article |
Statements
On the domination number of cross products of graphs (English)
0 references
11 March 1996
0 references
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.
0 references
dominating set
0 references
domination number
0 references
cross product
0 references
path
0 references
complement
0 references