Talk:Glossary of graph theory/Archive 2

Archive 1

Archive 2

Terminology

I've been doing graph theory for a long time, and I find some of the terminology in this article very peculiar if not wrong.

For instance, I've never seen the term "anti-edge". I'm sure someone used it, since there is a great deal of variation in terminology. There is no standard term for this, but I believe "non-edge" is far more common. There is also "nonadjacency".

Similarly, many people, possibly most, say "endpoint" instead of "endvertex". I believe that giving priority to "endvertex" is not in accord with general usage. (Diestel likes "endvertex"; maybe that's part of the cause of the confusion.)

A "hypergraph" is not a graph at all. This has to be fixed.

An edge "is" not a pair of vertices. One common definition of an edge is that it is a pair of vertices. Another is that it is an object that has two associated vertices. There are other definitions. None of them is wrong, but none of them is the one correct definition. Definitions in graph theory are chosen to suit the problem; one person's problem may call for an edge to be merely a pair of vertices, and another person's work may require another definition. This must be made clear in a useful glossary. Zaslav (talk) 12:45, 29 July 2010 (UTC)

hole ?

I'm trying to find a RS for the origination of the term 'hole' - also I am not sure if it belongs to the domain of GT or CS. Any ideas? (20040302 (talk) 08:59, 16 August 2011 (UTC))

Hole as in an induced cycle? Definitely graph theory more than CS, in the theory of perfect graphs. I don't know the original sources but it seems to have become standard in that context at least by the mid-1970s. One possible place to look (though I'm not sure since it doesn't seem to be online would be Tucker, Alan. "The strong perfect graph conjecture and an application to a municipal routing problem". Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), pp. 297–303. Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972. —David Eppstein (talk) 03:48, 17 August 2011 (UTC)

Hi there David - and thanks for your help, but no, not as in induced cycle. I'm now wondering if 'hole' is the correct term. The term I am looking for is to do with the legal places for where vertices may be inserted. So, for instance, on an Arborescence there is an easily defined set of potential node - positions where a new node/vertex may be inserted. IE, a potential insertion point. So far, the only tern that I could find that relates to this is 'hole'. (20040302 (talk) 12:17, 17 August 2011 (UTC))

Maze and tie set

Ernst Guillemin uses the terms maze and tie set to mean the duals of trees and cut sets respectively. Should these be added? I am not sure how widespread that usage is. SpinningSpark 11:05, 22 January 2012 (UTC)

I also have yoke, chain and yoke-chain from Percy MacMahon, and tentacle from M. Minas. Any comments on adding these? SpinningSpark 23:02, 24 January 2012 (UTC)

Are any of these used by significant numbers of authors? I'm not sure we want to clutter this up with idiosyncratic terminology that nobody else uses. Also what do you mean by the dual of a tree? Its planar dual is a multigraph with a single vertex, not very interesting as an abstract graph divorced of its embedding. Do you mean the dual of a spanning tree of a planar-embedded graph (in which case the dual is just the complement of a spanning tree, and is for that reason sometimes called a cotree)? —David Eppstein (talk) 00:06, 25 January 2012 (UTC)

Yes, dual of a planar mappable graph spanning tree is meant. I don't know how widely used any of these terms are, that's why I asked here first. Although tie set, at least, I found in two or three different authors. SpinningSpark 01:47, 25 January 2012 (UTC)

Path and Chain override the Trail?

In one paragraph, the page says: "A trail is a walk in which all the edges are distinct." Later, it says that "when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated. (The term chain has also been used to refer to a walk in which all vertices and edges are distinct.)" It is not clear if author forget the first definition of "all edges distinct walk" or chain is somehow different from the trail. --Javalenok (talk) 18:55, 10 March 2012 (UTC)

A trail is not necessarily simple (it could have repeated vertices without having repeated edges). --Lasunncty (talk) 10:14, 12 March 2012 (UTC)

Empty tree

Could somebody add its definition to the list? Does it denote K₀, K₁, or either depending on the mood of the researcher? Now I’m going to convert null graph to a dab page, and in absence of proposals will not change the “empty tree” redirect. Incnis Mrsi (talk) 08:48, 7 June 2013 (UTC)

An empty tree can only be K₁. K₀ is not a tree: it has the wrong number of edges for its number of vertices. I would say that it is a forest, though (a forest with zero trees in it). —David Eppstein (talk) 16:04, 7 June 2013 (UTC)

Total degree definition vz. conclusion.

I'm going to change the stated definition of the total degree. (Right now this is explained as twice the number of edges. The paragraph then is concluded by the remark that by the hand shaking lemma the total degree equals twice the number of edges. However, with the presented definition, there would be nothing to prove.)

(Besides, for loop-free graphs, the incidence concept may be used to explain the equality in-line.) JoergenB (talk) 20:43, 25 January 2014 (UTC)

Strongly connected component

It is somewhat weird that the "strongly connected component" section appears before the "connectivity" section, isn't it? And, in general, I'd think of connectivity as "Basics"... Peleg (talk)