***** To join INSNA, visit http://www.insna.org ***** Hi, 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. Regards, --Moses 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! > > best, > > 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.