4
$\begingroup$

A graph is a minimal graph of diameter $2$ if it has diameter $2$ and the deletion of any edge increases its diameter.

Let $G$ be a minimal graph of diameter $2$, then every edge of $G$ belongs to a path $u$-$v$ in $G$ which is the unique path of length at most $2$ with endpoints $u$ and $v$.

My question is: If $H$ is a graph satisfies every edge of $H$ belongs to a path $u$-$v$ in $H$ which is the unique path of length at most $2$ with endpoints $u$ and $v$. Does there must exist a minimal graph $G$ of diameter $2$ such that $V(G)=V(H)$ and $H$ is a subgraph of $G$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I challenge your implication. Let $G$ be a four-vertex cycle. It is a minimal graph of diameter 2, but there are not unique paths for all pairs u-v. (Every edge does belong to a unique u-v path such that the path contains u and contains v and contains that edge, but this is a different condition from what you have stated.) In spite of this, I think the answer to your question is yes. Gerhard "Don't Have A Proof Now" Paseman, 2016.08.30. $\endgroup$
    – Gerhard Paseman
    Commented Aug 30, 2016 at 20:09
  • 1
    $\begingroup$ @GerhardPaseman - Actually I think the OP is right. The condition stated in the OP is: for any edge, there exists a pair of vertices u,v with a path of length ≤2 connecting them and containing that edge, and there does not exist any other path of length ≤2 connecting those vertices (whether containing the given edge or not). The OP is right that this condition is implied by being min of diam 2, since for deletion of an edge to increase the diam there must be a pair of vertices with the only path of length ≤2 between them going through the deleted edge. $\endgroup$
    – benblumsmith
    Commented Aug 31, 2016 at 14:13
  • 1
    $\begingroup$ In case of $C_4$, for each edge there is a pair of vertices (namely, the pair incident to that edge) such that the unique path of length $\leq 2$ connecting them goes through that edge. $\endgroup$
    – benblumsmith
    Commented Aug 31, 2016 at 14:14

1 Answer 1

Reset to default
2
$\begingroup$

If I understand the question correctly, the answer is no.

Let $H$ be the 5-vertex graph consisting of a triangle with "tails" on two vertices; more explicitly let $V(H)=\{1,2,3,4,5\}$ and $E(H)=\{\{1,2\},\{2,3\},\{1,3\},\{1,4\},\{2,5\}\}$.

Then $H$ has the stated property: each edge is part of a path of length $\leq 2$ that is the unique such path between its endpoints. Explicitly:

For $\{1,2\}$, take $4\to 1\to 2$ or $1\to 2\to 5$.

For $\{2,3\}$, take $5\to 2\to 3$.

For $\{1,3\}$, take $4\to 1\to 3$.

For $\{1,4\}$ and $\{2,5\}$ take $1\to 4$ and $2\to 5$ respectively.

However, $H$ is not the subgraph of any minimal graph of diameter $2$ on five vertices. In fact, no such graph contains a triangle. Proof, by fully classifying minimal diameter 2 graphs on 5 vert's: if a minimal graph of diameter 2 on five vertices contains a vertex of degree 4, it contains the star $K_{1,4}$ and then it equals this since this is min. diameter 2. If it contains no vertex of degree $>2$, then it is clearly the $5$-cycle $C_5$ since again it must contain this graph (otherwise it would have diameter $>2$) and this too is min. diameter 2. Finally, if it contains a vertex of degree $3$ but none of degree $4$, then it must be $K_{2,3}$ since, say the degree 3 vertex is $a$ and it's adjacent to $b,c,d$. If the final vertex $e$ is connected to only $b$, then $b$ is forced to be degree $4$ to achieve diameter $2$, contradiction; if it's connected only to $b$ and $c$, then to achieve diameter 2 one of them must be connected to $d$ and then the graph contains the $5$-cycle properly and is not minimal. Thus $e$ must be adjacent to $b,c,d$, so the graph contains $K_{2,3}$, and then it equals this since it is already min. diameter 2.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .