Dominating cliques in graphs (Q5925264)

From MaRDI portal
scientific article; zbMATH DE number 4189764
Language Label Description Also known as
English
Dominating cliques in graphs
scientific article; zbMATH DE number 4189764

    Statements

    Dominating cliques in graphs (English)
    0 references
    0 references
    0 references
    1990
    0 references
    A subset D of the vertex set V(G) of a graph G is called dominating, if for each vertex \(x\in V(G)-D\) there exists a vertex \(y\in D\) adjacent to x. If a dominating set induces a complete subgraph of G, it is called a dominating clique. Some existence theorems for dominating clique sets of small cardinalities are proved. The clique domination number of G is defined as the minimum cardinality of a dominating clique in G. It is compared with the domination number and with the independent domination number of G. An algorithm for finding a dominating clique is presented; it works in the time \(O(n^ 3)\), where n is the number of vertices. Further, the so-called threshold dimension of a graph is studied; this is the minimum number of subgraphs which cover all edges of the graph and none of which contains \(P_ 4\), \(C_ 4\) or \(2K_ 2\) as an induced subgraph.
    0 references
    clique dominating set
    0 references
    clique domination number
    0 references
    threshold dimension
    0 references

    Identifiers