***** To join INSNA, visit http://www.insna.org *****
As Martin has told you, the only other relative definition is of a
distance-regular graph but this is related to West's definition of a
strongly regular graph than to a graph in which one relaxes the
condition of having the same number of common actors to any arbitrary
pair of actors (as you want it). Actually, these types of graphs are
used to prove the Friendship Theorem, which says that if each pair of
people has precisely one common friend, then someone is everyone's
friend. For instance, according to the proof of Biggs-Higman (West's
proof is similar but it rests upon the notion of strong regulaity),
the hypothesis of the Friendship Theorem implies that such a graph
consists either of a number of triangles all with a common vertex or
it is an appropriate distance-regular graph. Now, by showing the
infeasibility of the second alternative, one completes the proof of
the Friendship Theorem.
On Thu, Dec 9, 2010 at 8:47 PM, Gizem Korkmaz <[log in to unmask]> wrote:
> ***** To join INSNA, visit http://www.insna.org ***** Hi,
> I wanted to ask a quick question on graph theory.. I'd be very thankful if
> you could help me with it..
> A k-regular simple graph G on v nodes is strongly k-regular if there exist
> positive integers (k,s,m) such that every vertex has k neighbors (i.e., the
> graph is regular), every adjacent pair of vertices has 's' common neighbors,
> and every nonadjacent pair has 'm' common neighbors (West 2000,
> pp. 464-465).
> I am looking for graphs for which the last property (that every nonadjacent
> pair has m common neighbors) is relaxed. So, the nonadjacent pairs might
> have different number of common neighbours, while adjacent pairs have same
> number of common neighbors. (a cycle graph with n>5 is an example of such a
> graph). Do you know whether this family of graphs have a particular name in
> the literature so that I can check for their properties?
> Thank you very much in advance!
> Gizem Korkmaz
> European University Institute
> _____________________________________________________________________ SOCNET
> is a service of INSNA, the professional association for social network
> researchers (http://www.insna.org). To unsubscribe, send an email message to
> [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of
> the message.
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.