Talk:Complete graph

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	Mid Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Needs references and applications. Tompw (talk) 13:03, 4 January 2007 (UTC)

Contents 1 POV on "worst case" 2 Enneagon and Decagon 3 K100 4 Extending this wiki to include complete digraphs 5 Is there a general way of determining all of the subgraphs of Kj UP TO isomorphism? 6 Is there a general way of determining all of the directed subgraphs of a directed Kj UP TO isomorphism? 7 3D complete graph?

[edit] POV on "worst case"

In the current version, the sentence "(..) a complete graph can be the worst case for large connected systems like social and computer networks" is POV. It needs explanation. Otherwise the statement is not generally true and needs to be removed. Why should a complete social network be any bad? Worse in comparison to what?

I guess the person who wrote it was thinking of benefit-cost-ratio. But that needs some elaboration and possibly sources to make it credible. Otherwise not worthy of an existence in an encyclopedia. Tang Wenlong (talk) 21:27, 28 April 2008 (UTC)

Er, although this statement is poorly-written, I think this just means that it's the worst-case size (as in worst-case analysis) for such a network; which is of course not expressing a point of view. Dcoetzee 21:30, 28 April 2008 (UTC)

[edit] Enneagon and Decagon

This article has pictures of all regular polygons from a triangle to an octagon. The triangle has nothing but its sides and corners, but the octagon looks very complicated. Can anyone see how complicated an enneagon or decagon will look?? 66.245.86.215 01:21, 16 Oct 2004 (UTC)

You mean K₉ and K₁₀? As a general rule, the complete graph on n vertices, K_n, has n × (n - 1) / 2 edges; so K₉ has 9 × (9 - 1) / 2 = 36 edges, and K₁₀ has 10 × (10 - 1) / 2 = 45. So yeah, they can look quite complicated!  :-) I guess since we've already got K₁ to K₈, we might as well add 9 and 10; or we could add K₁₀₀ just to illustrate how messy they can get... --Ejrh 02:22, 18 Oct 2004 (UTC)

[edit] K100

K100 added! It's really beautiful. Alpt 18:41, 30 October 2006 (UTC)

yes, it is, but it adds little to the article. More like "ooh, look what my computer can do". I suppose it might illustrate that the number of connections increases rapidly —Preceding unsigned comment added by 24.18.43.240 (talk • contribs)

It's completely inappropriate and I'm going to remove it. Even at the highest resolution it is hard to see the edges but only the interference pattern they make. It will only confuse people who come to this page for information on complete graphs. --McKay 01:56, 30 December 2006 (UTC)

I agree, thanks. I was going to remove it myself, and I am glad you did it first. -- Dominus 03:37, 30 December 2006 (UTC)

[edit] Extending this wiki to include complete digraphs

Silly point - but this wiki could also define the concept for directional graphs. This request is motivated by the next two entries.

[edit] Is there a general way of determining all of the subgraphs of K_j UP TO isomorphism?

Yes, this is a simple exercise, and I will probably hunt it down on the internet. But, say, for K₄ how many subgraphs are there (where I would like to differentiate between subgraphs that are NOT isomophic to one another - clearly it is simple to enumerate all the subgraphs, calculate their adjacency matrices and get a computer program to get rid of all of the similar matrices so that you are left with ONLY isomorphically distinct subgraphs - but, surely, this has been done already?).

ConcernedScientist 19:01, 30 May 2007 (UTC)

[edit] Is there a general way of determining all of the directed subgraphs of a directed K_j UP TO isomorphism?

Same as above request, but everything is to do with directed graphs (so their should be more subgraphs up to isomorphism...). ConcernedScientist 19:01, 30 May 2007 (UTC)

[edit] 3D complete graph?

I have yet to see one but I think it would be very interesting. -Eeky 06:56, 6 August 2007 (UTC)

The simplex family has vertex/edge sets as complete graphs, so the tetrahedron is 3D, and pentachoron is 4D. Tom Ruen 14:15, 6 August 2007 (UTC)

Interesting. So shouldn't simplex mention complete graphs as being 3D equivalents? -Eeky 15:41, 6 August 2007 (UTC)

Any graph, no matter how many vertices, can be embedded without crossings in 3d, for instance by placing the ith vertex at the coordinates (i,i², i³). —David Eppstein 15:13, 6 August 2007 (UTC)

OK, but is there a 12-vertex version? -Eeky 15:41, 6 August 2007 (UTC)