6 problems

Let $G$ be a diameter-2-critical graph with $n$ vertices, and let $e(G)$ denote its number of edges. Murty–Simon Conjecture. … Moreover, equality holds if and only if … The conject…

Let $G$ be a diameter-2-critical graph with $n$ vertices, let $d_v$ denote the degree of vertex $v$, and let $e(G)$ denote the number of edges. Cacetta–Häggkvist conjecture. … This…

For $k\geq 3$, let $a_1$ disjoint paths $x_1^ix_2^i\cdots x_{k-1}^i$ be given for $i=1,2,\ldots,a_1$. Add $a_0$ new vertices adjacent to each $x_1^i$, and add $a_2$ new vertices ad…

Let $G$ be a non-bipartite diameter-$2$-critical graph of order $n$, and let $H_5$ be the exceptional graph and $\mathcal{C}_5^+$ the family of expanded $5$-cycles described in the…

Let $G$ be a non-bipartite diameter-$2$-critical graph without a dominating edge, and let $n$ be its order. Let $\mathcal{C}_5^+$ denote the family of expanded $5$-cycles described…

A graph $G$ is diameter-critical if deleting every edge increases its diameter, and it is diameter-$k$-critical if it is diameter-critical with diameter $k$. For a graph on $n$ ver…