Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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. –  MCP_infiltrator Sep 10 '12 at 5:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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