A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no induced path on five vertices. 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 the complete bipartite graphs with partite sets whose cardinality differs by at most one. We use an association with total domination to prove that if G is a diameter-2-critical graph with no induced path P5, then G is triangle-free. As a consequence, we observe that the Murty-Simon Conjecture is true for P5-free, diameter-2-critical graphs by Turán's Theorem. Finally we characterize these graphs by characterizing their complements.

The total domination number γt(G) of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, γt(G)≤1+nln(n). This bound is optimal in the sense that given any ε>0, there exist graphs G with diameter 2 of all sufficiently large even orders n such that γt(G)>(14+ε)nln(n).

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235-240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81-98] proved the conjecture for n > n 0 where n 0 is a tower of 2's of height about 1014. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. The complete graph on four vertices minus one edge is called a diamond, and a diamond-free graph has no induced diamond subgraph. In this paper we use an association with total domination to characterize the diameter-2-critical graphs whose complements are diamond-free. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊ n24⌋ and that the extremal graphs are the complete bipartite graphs K⌊ n2⌋n2⌉. As a consequence of our characterization, we prove the Murty-Simon conjecture for graphs whose complements are diamond-free.

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 set S of vertices in a graph G is a total dominating set 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 vertex removal stable if the removal of an arbitrary vertex leaves the total domination number unchanged. On the other hand, a graph is total domination vertex removal changing if the removal of an arbitrary vertex changes the total domination number. In this paper, we study total domination vertex removal changing and stable graphs.

A connected graph is total domination stable upon edge removal, if the removal of an arbitrary edge does not change the total domination number. We determine the minimum number of edges required for a total domination stable graph in terms of its order and total domination number.

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 total dominating set of a graph G with no isolated vertex is a set 5 of vertices of G such that every vertex is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set in G. In this paper, we present several upper bounds on the total domination number in terms of the minimum degree, diameter, girth and order.