Talk:Graph property

I do not think that redirecting graph invariant to graph property is a good idea. To me a graph invariant is a mathematical concept (usually a number) associated with a graph that stays the same (= is invariant) under the graph isomorphism. For instance, the sum of the elementes of the first row of the adjacency matrix is not a graph invariant (since it depends on the vertex ordering) while the maximal row sum (= maximal degree of the graph) is a graph invariant.Tomo (talk) 06:29, 7 August 2008 (UTC)[reply]

I think this is resolved now. Radagast3 (talk) 12:01, 23 March 2009 (UTC)[reply]

Invariant discussion[edit]

I find the current writeup of graph invariants to be poorly written. A property is said to be a "descriptive characterization of [a] graph." Lets assume for the moment this does no allow qualitative characterizations. The article then defines a graph invariant as "an indexed family of graph properties." This is confusing when one rereads the given example of a graph property ("graph does not have vertices of degree 1").

The given example does not help. Indeed, I think it's wrong:

For example "the number of vertices" is an indexed family of graph properties "a graph has M edges, M = 0, 1, 2....".

Shouldn't that read:

For example "the number of vertices" is an indexed family of graph properties "a graph has N vertices, N = 0, 1, 2....".

Or have I misunderstood? Pugget (talk) 19:05, 22 March 2009 (UTC)[reply]

-- I've reworded the para to be more standard. Tell us if it's still confusing. Radagast3 (talk) 07:30, 23 March 2009 (UTC)[reply]

Reads much better now. Matches my understanding from Diestel. Thanks for the general cleanup and rewrite of the article! Pugget (talk) 12:28, 23 March 2009 (UTC)[reply]

"monotone property"[edit]

Please see my edits at Hereditary property regarding the meaning of "monotone property". Actually I'm not sure that "hereditary" is any more uniquely defined but I'm out of steam for now. Someone else feel free... McKay (talk) 11:47, 23 March 2009 (UTC)[reply]

Yes, I saw that while I was editing and have made this article consistent. Radagast3 (talk) 11:55, 23 March 2009 (UTC)[reply]

Lead paragraph[edit]

I don't think readers will understand "inherently graph-theoretical". It sounds like a contrast with inherently topological (e.g. the graph genus) or inherently linear algebraic (e.g. the eigenvalues). I suggest:

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. McKay (talk) 12:20, 23 March 2009 (UTC)[reply]

Much better! Radagast3 (talk) 12:26, 23 March 2009 (UTC)[reply]