On the number of edges in graphs with a given connected domination number
The paper is devoted to the problem of finding the maximum number of edges in a graph with given connected domination number. A connected dominating set \(V\) of a graph \(G\) is a set of vertices that is dominating and the graph induced by \(V\) is connected. The connected domination number of \(G\) is the size of its smallest connected dominating set. The main result of the paper is a characterization of graphs with given connected domination number. It is proved that for a connected graph \(G\) with \(n\) vertices and connected domination number \(d\) the number of edges in \(G\) is at most \(\binom{n-d+1} {2}+(d-1)\). Moreover extremal graphs achieving this bound are characterized.
- Maximum number of edges in connected graphs with a given domination number
- Maximum sizes of graphs with given domination parameters
- Relating the size of a connected graph to its total and restricted domination numbers
- Some results on characterizing the edges of connected graphs with a given domination number
- Sizes and transmissions of digraphs with a given clique number
- Maximum size of digraphs with some parameters
- Upper bounds for domination related parameters in graphs on surfaces
- Connected domination
- On the number of connected subgraphs with small edge‐boundary in regular graphs
- scientific article; zbMATH DE number 637618 (Why is no real title available?)
This page was built for publication: On the number of edges in graphs with a given connected domination number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1972141)
