Skip to main content
1 of 2
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

Defining fuzzy properties of crisp graphs

Is there a standard procedure to define fuzzy generalizations of typical graph properties?

Consider the concept of a fuzzy clique. Define the cliqueness $c(G)$ of a graph $G$ as the ratio $\text{deg}(G)\ /\ (|V(G)|-1)$ between the mean degree of $G$ and the number of its vertices (minus one).

Alternatively: $c(G) = 2\ |E|\ /\ (|V|^2 - |V|)$.

That is, a graph deviates from being a "true" clique with the number of its missing possible edges. But shouldn't the missing edges been distributed as uniformly as possible among the vertices? Isn't 3 more of a (fuzzy) clique than 2 (which is more of a "true" clique plus an extra vertex), even though they have the same cliqueness?

alt text http://epublius.de/mathoverflow/fuzzy4.png

Should one try to capture this (felt) difference between 2 and 3? E.g. by considering higher moments of the distribution of missing edges?

Is this program (including higher moments) executed somewhere? And how is it to be generalized?

Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113