In a graph G = (V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ε E(Ḡ), the double domination number of G + uv is less than the double domination number of G. We investigate double domination edge critical graphs and characterize the trees and cycles having this property. Then we concentrate on double domination edge critical graphs having small double domination numbers. In particular, we characterize the ones with double domination number three and subfamilies of those with double domination number four.

A graph G is diameter 2-critical if its diameter is two, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G). The graph G is 3t-critical if γt(G)=3 and γt(G+e)=2 for every edge e in the complement of G. We show that no bipartite graph is 3t-critical. The tripartite 3 t-critical graphs are characterized. For every k<3, we prove that there are only a finite number of 3t-critical k-partite graphs. We show that the 5-cycle is the only 3t-critical K3-free graph and that there are only a finite number of 3t-critical K4-free graphs.

A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n24 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and cycles, graphs with double domination numbers of 3, and graphs with double domination numbers of 4 with maximum diameter.

A graph $$G$$G is diameter 2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊n2/4⌋ and that the extremal graphs are the complete bipartite graphs K⌊n/2⌋,⌈n/2⌉. We survey the progress made to date on this conjecture, concentrating mainly on recent results developed from associating the conjecture to an equivalent one involving total domination.

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊n2/4⌋ and that the extremal graphs are the complete bipartite graphs K⌊n/2⌋,⌈n/2⌉. A graph is t-edge-critical, abbreviated 3tEC, if its total domination number is 3 and the addition of any edge decreases the total domination number. It is known that proving the Murty–Simon Conjecture is equivalent to proving that the number of edges in a 3tEC graph of order n is greater than ⌈n(n-2)/4⌉. We study a family F of 3tEC graphs of diameter 2 for which every pair of nonadjacent vertices dominates the graph. We show that the graphs in F are precisely the bull-free 3tEC graphs and that the number of edges in such graphs is at least ⌊(n2-4)/4⌋, proving the conjecture for this family. We characterize the extremal graphs, and conjecture that this improved bound is in fact a lower bound for all 3tEC graphs of diameter 2. Finally we slightly relax the requirement in the definition of F—instead of requiring that all pairs of nonadjacent vertices dominate to requiring that only most of these pairs dominate—and prove the Murty–Simon equivalent conjecture for these 3tEC graphs.

A graph G is diameter 2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a connected spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s; that is, Ks,s, = G ⊕ H is a factorization of Ks,s. The graph G is k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.