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 

1 Answers 1

1

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.

  • 0
    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.2012-09-10