Maximum number of edges in connected graphs with a given domination number

DOI10.1016/0012-365X(91)90071-9MaRDI QIDQ1174141zbMATH OpenOpenAlexFDO

Authors Laura A. Sanchis

Publication date 25 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(91)90071-9

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

A dominating set in a graph is a subset \(U\) of its vertices such that each vertex not in \(U\) has a neighbour in \(U\). The domination number is the minimum size of a dominating set. The paper under review shows that a graph with \(n\) vertices, domination number \(d\) (where \(3\leq d\leq n/2)\) and no isolated vertices has at most \(n-d+1\choose 2\) edges. The graphs for which this bound is tight are also characterized. The proof is based on work of \textit{Y. Usami} [``Minimum number of edges in graphs that are both \(P_ 2\)- and \(P_ i\)-connected, Discrete Math. 44, 195-199 (1983; Zbl 0503.05038)]. The corresponding bound and related characterization for graphs with isolated vertices is due to Vizing.

Recommendations

• On the number of edges in graphs with a given connected domination number
• Some results on characterizing the edges of connected graphs with a given domination number
• scientific article; zbMATH DE number 861339
• Relating the size of a connected graph to its total and restricted domination numbers

Cites work

• Domination alteration sets in graphs
• Domination critical graphs
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3221976 (Why is no real title available?)
• Minimum number of edges in graphs that are both \(P_ 2-\) and \(P_ i- \)connected
• Towards a theory of domination in graphs

Cited in

(25)

• The number of edges in a maximum cycle-distributed graph
• Domination number and neighbourhood conditions
• A generalization of Vizing's theorem on domination
• New results about the bondage number of a graph
• Average distance and domination number
• Generating hard and diverse test sets for NP-hard graph problems
• 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
• On bondage numbers of graphs: a survey with some comments
• On the number of edges in graphs with a given connected domination number
• Bounds on neighborhood total domination number in graphs
• On the spectral radius of graphs with a given domination number
• Traceability of connected domination critical graphs
• Sizes and transmissions of digraphs with a given clique number
• Maximum size of digraphs with some parameters
• scientific article; zbMATH DE number 5159426 (Why is no real title available?)
• scientific article; zbMATH DE number 721636 (Why is no real title available?)
• Upper bounds on the bondage number of a graph
• LAPLACIAN EIGENVALUES OF GRAPHS WITH GIVEN DOMINATION NUMBER
• scientific article; zbMATH DE number 5498807 (Why is no real title available?)
• Discrete and Computational Geometry
• Optimal linear‐Vizing relationships for (total) domination in graphs
• On approximation of multiple intruder locating domination number of a graph
• The maximum number of edges in geometric graphs with pairwise virtually avoiding edges

This page was built for publication: Maximum number of edges in connected graphs with a given domination number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174141)