Maximum size of a connected graph with given domination parameters
Four domination parameters of graphs are considered. A subset \(S\) of the vertex set \(V\) of a graph \(G\) is called dominating, if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). If a dominating set \(S\) induces a connected subgraphs \(\langle S\rangle\) of \(G\), it is called connected dominating. If moreover \(\langle S\rangle\) is a clique of \(G\), then \(S\) is called clique dominating. If each vertex of \(G\) is adjacent to a vertex of \(S\), then \(S\) is called total dominating. If \(S\) is a subset of the edge set \(E\) of \(G\) such that each edge of \(G\) either is in \(S\), or has a common end vertex with an edge of \(S\), then \(S\) is called an edge dominating set in \(G\). If moreover \(S\) induces a connected subgraph of \(G\), it is called connected edge dominating. The minimum cardinalities of such sets are subsequently the domination number \(\gamma(G)\), the connected domination number \(\gamma_c(G)\), the clique domination number \(\gamma_k(G)\), the total domination number \(\gamma_t(G)\), the edge domination number \(\gamma'(G)\) and the connected edge domination number \(\gamma_c'(G)\) of \(G\). For each of those parameters the paper shows an upper bound for the number \(q\) of edges of \(G\) in terms of that parameter and the number \(p\) of vertices of \(G\). Always the conditions for attaining this bound exactly are stated.
- Maximum sizes of graphs with given domination parameters
- Relating the size of a connected graph to its total and restricted domination numbers
- Strong kernel number in certain oriented cycle extension of graphs
- Equality in a bound that relates the size and the restrained domination number of a graph
- Connected domination
- On domination parameters and maximum degree of a graph
- scientific article; zbMATH DE number 1416472 (Why is no real title available?)
- Some bounds on domination related parameters
- Size, Order, and Connected Domination
- scientific article; zbMATH DE number 5498807 (Why is no real title available?)
- An inequality that relates the size of a bipartite graph with its order and restrained domination number
- Domination in edge cycle graphs
- Improving a bound that relates the size of a bipartite graph with its restrained domination number
This page was built for publication: Maximum size of a connected graph with given domination parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2761000)
