Let $X=(V, E)$ be an undirected connected trivalent graph and $d_X$ denote the path metric on $X$, i.e., the distance $d_X(u, v)$ between two nodes $u, v$ in the graph is the length of a shortest path between them. Note that, the length of a path in a graph is the number of edges it consists of. Now, the diameter of $X$ is defined by $$d(X)=\max\limits_{u,v\in V} d_X(u, v).$$

Now we define $T(2k)$ to be the set of all trivalent graphs with $2k$ nodes (we know that any trivalent graph has even number of nodes). Note that, multi-edges and loops are allowed in the trivalent graphs we considered.

My questions are the following:

$\bullet$ Can one estimate $D(2k)$ where $D(2k)=\min\limits_{X\in T(2k)}d(X).$

$\bullet$ What is the trivalent graph $X$ realizing $D(2k)$, i.e., $d(X)=D(2k)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.