Dominating direct products of graphs (Q879339)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Dominating direct products of graphs
scientific article

    Statements

    Dominating direct products of graphs (English)
    0 references
    0 references
    0 references
    0 references
    11 May 2007
    0 references
    Let \(G=(V,E)\) be a graph. A set \(S\subset V\) is called dominating if each vertex in \(V\backslash S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) of a graph \(G\) is the minimum cardinality of a dominating set. For graphs \(G\) and \(H\), the direct product \(G\times H\) is the graph with vertex set \(V(G)\times V(H)\) where two vertices \((x,y)\) and \((v,w)\) are adjacent if and only if \(xv\in E(G)\) and \(yw\in E(H)\). The purpose of the paper is to estimate the domination number and some related parameters (upper domination number and paired-domination number) of a direct product of graphs. Two of the main results are: (1) \(\gamma(G\times H)\leq 3\gamma(G)\gamma(H)\). (2) Graphs with arbitrarily large domination numbers for which there is an equality in this inequality are constructed.
    0 references
    domination
    0 references

    Identifiers