Talk:Glossary of graph theory

Merging and Organization

I don't think this page should be merged into graph theory. It was deliberately created to list definitions. Charles Matthews 16:41, 21 Mar 2005 (UTC)

I only skimmed articles in question (i.e., graph theory, glossary of graph theory and graph (mathematics), but it seems there is a fair amount of overlap. The question, I think, is not if we should merge the two articles, but how we can make distinction among those articles; maybe one idea is let graph theory be the overview article, then create subtopic articles like properties of graphs (degree, Hamiltonian and such), or an article about directed or undirected. Merely listing definitions is really a bad idea. Besides, if this is a glossary, should each line stars with a bold term followed by the definition? -- Taku 19:16, Mar 21, 2005 (UTC)

This page is 30K of minor definitions. The idea is to have many redirects to it, rather than one page for each small definition. That is what a glossary page is supposed to do. Clearly 30K is too much to put into graph theory, which should give a broad introduction only.

So, I really don't see what the problem is with this. There are quite a few other examples, e.g. general topology and glossary of general topology.

Charles Matthews 20:38, 21 Mar 2005 (UTC)

OK, it seems that the correct idea is to merge graph (mathematics) into graph theory. But this page is fine as it is. Charles Matthews 20:41, 21 Mar 2005 (UTC)

Please don't try to merge the new stuff (recently moved from Graph theory) into the stuff that was already here. The new stuff is "Graph theory glossary for Dummies"; the old stuff is more like a Reader's Digest Condensed version of Graph Theory 101.

I promise I will do as I indicated at Wikipedia talk:WikiProject Mathematics#Graph (mathematics) vs Graph theory: drag all the content into a few user pages, stir them around, and organize them so that readers at different levels can make good use of them. Only then will I offer the refactoring to the project. It's not my place to say who will edit what when, but I'd be grateful if I didn't have to try to hit a moving target. — Xiong (talk) 03:47, 2005 Mar 22 (UTC)

As you know, we are all free to edit here as we see fit. That being said, it is more helpful to be more explicit. Charles Matthews 10:02, 22 Mar 2005 (UTC)

---

I think (as a newbie to graph theory) that we should remember who our audience is. It is me. I was directed to the glossary by several of the pages, because I thought I would get a better grasp of the term that was being defined on another page. What I found was a very incomplete definition that was disjointed from the supporting terms and concepts. For a glossary (which is typically a collection of disjointed definitions) to be useful, it should contain concepts which are easy to understand on their own, without having to understand the rest of the glossary. Otherwise, I, the learner, end up skipping back and forth between concepts trying to piece together a picture of what is being said. When I do that, I am essentially creating my own encyclopedia article in my mind in order to construct the full picture of the concept. But what if I don't have some of the pieces? As a learner of new information, it would be much better to have someone break down the knowledge ontologically into the correct sequence or taxonomy of ideas so that one idea builds upon the other. A glossary is a cheap imitation of doing that and should be reserved for more disjointed kinds of understanding, like quickly finding the definitions of acronyms used in telecommunications or something like that.

What I would like to see is each idea more fully developed to include separate illustrations to provide examples of each type of graph element. The concepts are much easier to understand when you have that kind of visual map presented to you. We are talking about graphs, here, so more graphs are better. Each graph should have more explicit instructions on how we are explaining it, by using colors and numbers, perhaps, to highlight various sections. That's just my two cents worth. TimIngalls 22:58, 15 November 2006 (UTC)

I agree that this page seems messy. The glossary of general topology page that Charles Matthews pointed out looks much cleaner. Do we want to head towards something like that? The "To be merged" section looks like it is already trying to. If we had the glossary organized alphabetically it would also clear up the 'order of definitions' issue, as Quintopia noted.

I haven't read through all of the discussion pages yet, but it looks like Xiong still wanted to do some work on this before he left. I'd hate for his hard work to be undone if I make changes without understanding the intent. Is there a consensus on what we should do here? --Culix 08:28, 7 December 2006 (UTC)

Order of definitions

It seems to me that no definition on this page should incorporate a term that is defined later on the page. It should be that any term that requires another term as part of its definition should come after the other term is defined, so that someone with no knowledge of graph theory reading the page from top to bottom would never have to stop and say "Oh, I don't even know what that means," and have to go search for it before continuing. Thus, the section on trees should come after the section on connectivity because trees and subtrees are defined to be connected.

The other option is to put everything in alphabetical order so that if someone does have to look up another term in the definition they won't have to search, but this is a huge change.--Quintopia 09:17, 25 October 2006 (UTC)

Direction: head/tail

Under Direction an arc is defined to de directed from the head to the tail. This is just the opposite of the definition in Graph (mathematics). There, the edge is directed from x to y, where x is the tail and y is the head. Who's wrong?

I agree, the direction of an arc is always from tail to head, both referring to the components of an arrow, which are frequently used to draw the arcs of a directed graph. DVanDyck 16:40, 11 August 2006 (UTC)

Direction: "A linked to B" is A->B or B->A?

Hi! I put to discussion what is the direction of the link between A and B, if it is written that "A is linked to B". Is it A->B or B->A? I'm not a native speaker of English, and this issue is hard for me to decide. I feel that A->B is appropriate for "A is linked to B", however also for "A links to B", and "A is linked to B" seems to be the passive form of "B links to A".. Is there a consensus on this, or could you refer me a book or scientific paper where this is explicitly defined? It would be also nice if this could make it into the article. Ron85 01:43, 5 February 2007 (UTC)

The passive form has "by" in it. This is a passive where the "by" part is missing (because it's "by the link"). The key part is "from" or "to"; that tells you the direction. Thus, "A links to B " = "A is linked to B ".

There are two answers to your question. If the graph is undirected, then "A links to B " is just a manner of speaking and means the same as " B links to A ". If the graph is directed, then "A links to B " means there is a path of directed edges starting at A and ending at B. (I hope I am guessing the context of your question correctly. Perhaps this is not really answering you.) Zaslav 09:51, 27 February 2007 (UTC)

knots

what's this definition of knots? it should be written if there is a link with knots of knots theory. and it should be explained more what are they and what they mean and what they imply! achab

Is this term "knot" common? I never heard of it in years of doing graph theory - mostly undirected, though. Opinions from experts? Zaslav (talk) 12:25, 29 July 2010 (UTC)

Minor

I find the definition of "minor" given here to be incomprehensible. What on earth does "every edge in E2 corresponds to a path (disjoint from all other such paths) in G1 such that every vertex in V1 is in one or more paths, or is part of the injection from V1 to V2" mean? I suggest defining "edge contraction" first then defining "minor" like at Minor (graph theory). 202.45.98.61 12:43, 13 June 2006 (UTC)

Indeed, this is the most common and clearest way to define "minor", and in addition consistent with the Minor (graph theory) page. DVanDyck 11:39, 13 August 2006 (UTC)

I totally and emphatically disagree with DVanDyck. I know exactly what a minor is and I still cannot understand the definition easily. It is very technical and gives no understanding. Zaslav (talk) 12:26, 29 July 2010 (UTC)

Request for More Illustrations

The discussion above regarding whether there needs to be a glossary or not could

Questions

• I can not find the answer to the following question on the page:

  How is a graph called, where edges might also be vertices?

  For example, (a,b) is the edge from the vertex a to the vertex b, and ((a,b),c) would be an edge from the edge (a,b) to the vertex c. 217.83.100.240 13:55, 28 September 2006 (UTC)

I never heard of a name for this. One usually assumes the vertex set and edge set are disjoint, because otherwise horrible technical complications can arise. I think you have something new that may not fit precisely into graph theory. Zaslav 09:39, 27 February 2007 (UTC)

I don't know if this is what you were looking for, but there is something called Hypergraph, where an edge may conect 2 vertexes or more. 128.243.21.225 13:44, 24 April 2007 (UTC)

A hypergraph is not exactly right. It allows more than 2 endpoints. If you would be satisfied to allow "edges" that have only one vertex (as opposed to loops, which have a repeated vertex thus two vertices), then you can have "half edges". Zaslav (talk) 12:29, 29 July 2010 (UTC)

• Fourth paragraph in "Walks" section: If a path (stated without qualification) is usually defined to be simple, and if simple means that every vertex is incident to at most two edges, then doesn't the fact that in the example graph 5 is incident to 3 edges mean that (5,2,1) isn't a path? Or maybe I'm not clear on what "incident to n edges" means? Or was this meant to be an example of an old usage of the term 'path'? I find this paragraph to be slightly confusing, if not self-contradictory. -Jesse again

Ok, I have fixed the definition of simple. It should make more sense now. --Lasunncty 22:40, 5 January 2007 (UTC)

• I can not find the term "dicycle" explained in the graph theory glossary.

• I followed a link to 'Tournament' in the article Probabilistic method and ended up here, where there's no mention of tournaments.. I'm left with absolutely no idea of the word's meaning.

Look again! It's there now! --Quintopia 09:17, 25 October 2006 (UTC)

• What are vertex disjoint cycles? 220.226.9.173

Subgraphs are called "vertex disjoint" if (pairwise) they have no vertices in common. Zaslav 09:39, 27 February 2007 (UTC)

Thanks

I think it is extremely helpful to have a glossary page. Thank you to whoever started this. I found a small problem, however, with the formula for the length of a walk (open, l=n-1; closed, l=n; n is number of vertices visited). It doesn't work for the example given directly below it. I believe this formula would work for a trail, but it doesn't work for a walk that has repeated edges. Of course you could decompose each walk into trails and then apply the formula, and that should work. I should mention that I am merely a lowly undergraduate, and I could be wrong about all this. If so, boy won't my face be red. Anywho, great page. -Jesse Supina, U of L (still don't know how that signature thing works)

I see your point. Vertices should be counted each time they are visited. Thanks for your input!! --Lasunncty 22:40, 5 January 2007 (UTC)

adjacency vs co-incidence

I was taught by Doug West 20 years ago that the edge was "incident" the node and vice versa, so that one spoke of adjacent nodes (sharing an edge) but co-incident edges (sharing a node). The article combines these concepts, calling edges adjacent if they share a node. The two concepts are not dual. If G is a graph the line graph of G, styled L(G), has as nodes the edges of G and they are adjacent nodes of L(G) if they are co-incident edges of G. G is called a line graph if it is the line graph of some graph H. Not all graphs are line graphs. There is a forbidden subgraph characterization: G is a line graph just in case it does not contain as subgraph any of a list of nine little graphs.

Perhaps the nomenclatural distinction has evaporated in the interim, but I hope not, since the logical one certainly hasn't. In any case I propose "line graph" as candidate glossary entry. Lewis Goudy66.82.51.210 01:32, 5 January 2007 (UTC)

Two edges that have a common vertex are generally called "adjacent" and have been for decades. Thus, adjacency of edges becomes adjacency of vertices in the line graph. I never heard "co-incident"; it can't be common. But in graph theory everyone is entitled to make up his/her own names, if he/she can get away with it, and some do! Zaslav 09:43, 27 February 2007 (UTC)

Lewis is correct. If you have a look up the definition of the Incidence Matrix of a graph, you'll see that it indicates which edges have which vertex as endpoint. Edges are incident to vertices, vertices are adjacent when they are endpoints of the same edge, and edges are co-incident when they share a vertex. —Preceding unsigned comment added by 216.88.130.72 (talk) 00:34, 14 February 2008 (UTC)

Lewis is undoubtedly correct that he was taught this by Doug West. Most graph theorists call edges adjacent if they share a vertex. Some notion of duality not being satisfied does not bother them. If WP reflects actual usage instead of a theory of usage, it must accept that edges sharing a vertex are adjacent. You may call them co-incident instead, if you wish, and probably people will understand, but that is not general usage. Zaslav (talk) 12:36, 29 July 2010 (UTC)

Proposal to split out List of graphs

I propose we split some of this material into an article List of graphs, which would list links to many or all of the specific kinds of graphs in Category:Graphs and Category:Graph families, plus bundle together a bunch of dicdefs for things like "path graphs", "caterpillar graphs", "lobster graphs", "gear graphs", "web graphs", and so on. (Those would all become redirects to the new page.) However, I can't do the page split all by myself; I'll start it tonight, if all goes well, and any help in adding definitions to List of graphs will be greatly appreciated. --Quuxplusone 01:47, 18 January 2007 (UTC)

You mean, something like Gallery of named graphs? —David Eppstein 02:08, 18 January 2007 (UTC)

• 

Thanks for the link. Something like that, yeah, but better. :) My beefs with that page include: Its name, which doesn't follow the "List of..." Wikipedia convention (although I am now aware of Wikipedia:Galleries, which seems to bless the "Gallery of..." alternative for picture-heavy articles). It's not very browseable, since it's not in alphabetical order and formatted in a grid instead of linearly. It has a few images like Image:Brinkmann graph.svg, shown above, which don't actually exist but pretend they do; I'll try to find out where to report this as a usability issue. (On Firefox on Linux, that image displays as a kind of blue splotch with vertices at the two upper corners and edges incident on those vertices, which is totally not what the Brinkmann graph looks like! Newbies will be even more confused than I was.) In its current form, it doesn't appear very friendly toward graphs or graph families that don't already have SVG images on Wikipedia; I'd be afraid to add a textual description of caterpillar graph to that page without a picture. And none of the graphs on that page currently have unambiguous textual descriptions, which makes it of dubious utility to a math student.

So I'm still planning to make List of graphs, even though I didn't get around to it yet. --Quuxplusone 23:08, 18 January 2007 (UTC)

2007-02-1 Automated pywikipediabot message

--CopyToWiktionaryBot 15:23, 1 February 2007 (UTC)

References not related to glossary to be removed from article

The shopping list of textbook references and their links are not directly related to the content of the Glossary of graph theory and begs the questions: "Why THAT list?" and "Why THOSE links?". Unless one or more of the references specifically contributed the definitions in the glossary, and this can be cited, they should be removed.

I plan to remove the references section from this article after 25 March 2008. If you have any objections or suggestions, please voice them prior to this date.Aarond144 (talk) 07:26, 17 March 2008 (UTC)

Induced Subgraphs

I read and re-read the definition of the word "induced" and it didn't help me understand what it meant. I then found the following very helpful definition in another book. Please consider using it.

"An induced subgraph is a subset of the edges of a graph together with any edges whose endpoints are both in this subset. - in "CRC Concise Encyclopedia of Mathematics" By Eric W. Weisstein (Published 2003 CRC Press, ISBN:1584883472 )

A figure included on page 1478 of that book was also very helpful. Cf. Google Books: http://books.google.com/books?id=aFDWuZZslUUC&pg=PA1478&dq=induced+graph+%7C+subgraph&lr=&sig=MsbTYy4gxQzdRc96cePtsB0X4IM —Preceding unsigned comment added by Kmote (talk • contribs) 19:21, 14 April 2008 (UTC)

References to "the example graph"

As noted by Lasunncty, numerous references are made in the article to "the example graph". This goes back to the time there was only one for the whole article (the one on the basics, "labeled simple graph..."). The problem is that since there are now many of them, most references are unclear or even plain wrong. I suggest giving this graph the title "reference graph" and replacing occurrences of "the example graph" by "the reference graph". Any other ideas? I'm opposed to numbering graphs, because the numbering and the references would have to be changed every time anybody adds or removes a graph. Ratfox (talk) 15:41, 14 August 2008 (UTC)

separating cycle

I've found in some literature (about planar graphs) the term "separating cycle". I can't find any concise definition of it. Anyone happens to know what does it mean? Stdazi (talk) 23:47, 8 September 2008 (UTC)

Transitive?

The current definition of an undirected graph is: "A graph that represents a symmetric, transitive relationship between nodes. Its edges are rendered as plain lines or arcs." How is this relation transitive? —3mta3 (talk) 10:32, 9 September 2009 (UTC)

Graphic Caption: "with the map w being the identity"

This makes me confused. —Preceding unsigned comment added by 75.152.169.231 (talk) 07:00, 12 September 2009 (UTC)

Me too. It's been there since the start of the article in 2003 and appears to have been as mystifying then as it was now. I have no idea what it was intended to refer to, so I removed it. —David Eppstein (talk) 07:29, 12 September 2009 (UTC)

I would assume that the original idea was to illustrate a weighted graph. Then it's easy to guess what the confusing statement tries to say: the map w: V → R which associates a weight with each vertex is an identity function, w(v) = v. That is, the numbers in the figure are both vertex labels and vertex weights. And yes, it's confusing and should be removed. — Miym (talk) 17:25, 12 September 2009 (UTC)

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)