LISTSERV mailing list manager LISTSERV 15.5

Help for SOCNET Archives


SOCNET Archives

SOCNET Archives


View:

Next Message | Previous Message
Next in Topic | Previous in Topic
Next by Same Author | Previous by Same Author
Chronologically | Most Recent First
Proportional Font | Monospaced Font

Options:

Join or Leave SOCNET
Reply | Post New Message
Search Archives


Subject: Re: question on graph theory
From: Moses Boudourides <[log in to unmask]>
Reply-To:Moses Boudourides <[log in to unmask]>
Date:Fri, 10 Dec 2010 16:19:48 +0100
Content-Type:text/plain
Parts/Attachments:
Parts/Attachments

text/plain (62 lines)


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

Back to: Top of Message | Previous Page | Main SOCNET Page

Permalink



WWW.LISTS.UFL.EDU

CataList Email List Search Powered by the LISTSERV Email List Manager