Print

Print


*****  To join INSNA, visit http://www.insna.org  *****

Hi
These graph types are usually derived from  permutation group properties and so the classes of graph studied are a consequence of the structures found in group theory. The only relaxation I know of is distance regular graphs but this relaxation is not what you want. I am pretty sure the answer will be no. Sorry not to be of more help.

Martin


________________________________
From: Social Networks Discussion Forum [[log in to unmask]] on behalf of Gizem Korkmaz [[log in to unmask]]
Sent: 09 December 2010 19:47
To: [log in to unmask]
Subject: [SOCNET] question on graph theory

***** 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.