1
$\begingroup$

I am reading a text for an upcoming class Social Network Analysis on Corsera.org and am trying to get a little bit ahead by reading some of the material before class starts. I am working on a question that asks me to:

Construct a graph in which all nodes are pivotal for at least one pair of nodes.

So I constructed a 'square' graph with 4 nodes A, B, C and D. The graph is undirected and is not complete, meaning there are only 4 edges between them and no diagonal edges. I am getting conflicting answers of yes and no for it being correct, I would appreciate any help, direction or readings that could be offered up.

A-----B
|     |
|     |
C-----D
$\endgroup$
1
$\begingroup$

In order for a node $X$ to be pivotal for the nodes $Y$ and $Z$, $X$ must be different from $Y$ and $Z$ and must lie on every shortest path between $Y$ and $Z$. Consequently, no node in your graph is pivotal for any pair of nodes. For example, $A$ is not pivotal for $B$ and $C$ because $BDC$ is a shortest path from $B$ to $C$ that does not contain $A$.

Try a closed loop of $5$ nodes and $5$ edges instead: then each node will be pivotal for its immediate neighbors, because it will lie on the only shortest path between them.

$\endgroup$
  • $\begingroup$ Thank you so much, I thought it was going to a fairly trivial graph, but its been a few years since I have touched graph theory unfortunately. $\endgroup$ – MCP_infiltrator Sep 10 '12 at 5:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.