Talk:Glossary of graph theory

definition of partition

Is missing. — Preceding unsigned comment added by 2A00:23C5:69EF:B300:5D73:7AE4:635E:1D3C (talk) 20:20, 25 August 2017 (UTC)

Theta Circles

The definition of theta graph stipulates distinct endpoints, but over in the article on biased graphs the article refers to circles (simple cycles) as being in theta graphs. Not a big deal--I suppose they are just using a little abuse of notation. Lewis Goudy (talk) 04:19, 10 October 2016 (UTC)

I don't see a problem. A theta graph contains three circles as subgraphs. Zaslav (talk) 01:49, 27 March 2019 (UTC)

Formatting

After dual graph was featured on the Main Page yesterday, I found my way here and started exploring what else links to this page, particularly with regard to individual terms. I made adjustments per MOS:GLOSSARIES as I went. Since Wikipedia doesn't seem to have a concept of a featured glossary, there wasn't any particular gold standard I could look to emulate, but one of the concepts of a glossary (implied but not explicitly stated in the MoS) is that definitions do not need to repeat in their definition the terms that they are defining. This, IMO, makes definitions clearer, and also puts the onus on the term (and not the definition) to be explicit about what is being defined. One side effect of this change is that terms with their own article are not regularly linked directly in the definition. I opted to take advantage of the features of {{term}} and wikilink the terms themselves when they had their own individual articles. Also, given that one of the more likely ways of getting to this glossary in the first place is through a redirect, and that the reader is likely only to be initially concerned about that one definition, I thought it wise to take advantage of the many anchors on the page and wikilink any first occurrence in a definition of terms that were defined elsewhere on the page (as if each were an article's introductory section). I also italicized these links to differentiate them from regular wikilinks to other articles. I don't know that these changes are controversial enough to get into a revert war over, but I'm open to having a discussion about whether they are the best approach. —Gordon P. Hemsley→✉ 22:42, 21 November 2016 (UTC)

The model I was following (when I reformatted this glossary last February from its previous much messier state) was that of Glossary of algebraic geometry and Glossary of classical algebraic geometry. Those two, like this one, do not have links in the terms. I don't feel strongly about this except to note that in many cases linking the terms is likely to produce awkward or wrong links. For instance, take the first one that isn't notation, "achromatic". The correct link is "achromatic number". So we would either have to make the term be "achromatic number" rather than "achromatic" (more cumbersome) or we would have to make a link on the word achromatic that goes to an article whose title uses that word but is not actually that word. Also, in some other cases (e.g. "cycle") there are multiple relevant links within a single definition and it might not make sense to choose a single one as the primary meaning that goes on the link. And of course for terms with multiple conflicting definitions, it does not even make sense to choose one of them to be the link on the term. To avoid complications like these and be consistent between the single- and multi-definition terms I think it's simplest and best to keep all the links within the definitions. —David Eppstein (talk) 00:17, 22 November 2016 (UTC)

I'm personally of the opinion that using terms that are adjectives when the definitions refer to nouns is the wrong way to go. I would prefer to see "achromatic" be "achromatic number" and other terms like "book" or "chord" be split out with separate entries for each term, similar to like what I did to "cut"/"cut-set" or "weight"/"weighted graph". I don't think anything is gained by having definitions grouped together just because their terms happen to have words in common. It makes it difficult for a newcomer (and the redirects they are likely to follow) to find the exact term they are looking for, and I don't agree that it is more cumbersome. —Gordon P. Hemsley→✉ 03:38, 22 November 2016 (UTC)

It is not possible to pretend that all of these terms have unique meanings if only we put them into complete phrases rather than separating out the adjectives. Some of them are genuinely used, not as part of a larger phrase, in conflicting ways. See e.g. bridge (an edge whose removal disconnects the edge or part of a graph separated from the rest by a cycle) or core (graph with no self-homomorphisms or highest-minimum-degree subgraph). It would be wrong to rewrite these as e.g. "bridge edge" because that's not what these things are actually called in the graph theory literature (you can find papers using that phrase but it's uncommon; they're just called bridges). —David Eppstein (talk) 05:40, 22 November 2016 (UTC)

I didn't say that there was no place for multiple definitions per term; I think "bridge" and "core" are good examples of where they can be useful (though I believe terms like "bridged graph" and "k-core" should be separated out into their own entries, and some of numbered definitions can be combined in a single, multi-sentence definition, like the aforementioned "cut"/"cut-set"). Also, I see a number of other glossaries wikilink every term they have; see, e.g., Glossary of areas of mathematics, Glossary of communication disorders, Glossary of geology, Glossary of education terms (A–C). While these are all bullet-style glossaries, rather than template-based, I think this is precedent enough to move forward with it. —Gordon P. Hemsley→✉ 07:41, 22 November 2016 (UTC)

Internal glossary links

I just discovered {{gli}}, so I replaced all manual internal glossing links with uses of that template. —Gordon P. Hemsley→✉ 17:53, 23 November 2016 (UTC)

Yes, this looks like a useful template and the right one to use here. —David Eppstein (talk) 18:19, 23 November 2016 (UTC)

Definition for "direct neighbor"

The glossary needs a definition for "direct neighbor" to satisfy the redirect target of direct neighbor. This book seems to define the term, but I don't have a full enough grasp of the material to be able to extract a standalone definition suitable for this glossary. Can someone create a definition for this term? Thanks. —Gordon P. Hemsley→✉ 06:43, 23 November 2016 (UTC)

That doesn't even look like graph theory. Why do you think it is relevant? —David Eppstein (talk) 07:35, 23 November 2016 (UTC)

It's unclear to me whether you're questioning the relevance of the term or the book, but I'll answer anyway: The page direct neighbor has redirected to this glossary since 2005; prior to that, it was defined as a situation "where a node has vertical or horizontal edge with its adjacent nodes". And as for the book, the definition I linked to is found in a section on graph theory and was one of the more promising results when I attempted to find a suitable definition. —Gordon P. Hemsley→✉ 15:34, 23 November 2016 (UTC)

Vertical and horizontal are geometric terms, not graph theoretic terms. My guess is that the redirect was always a mistake. —David Eppstein (talk) 16:42, 23 November 2016 (UTC)

Definition for "θ₀ graph"

Both Theta0 graph and Theta0 Graph redirect to this page as a whole, apparently in an attempt to create a corresponding Wikipedia page for the theta_0 Graph page on MathWorld. I don't understand the significance of this graph, and the MathWorld page doesn't give any clear indication as to what the best target of those redirects on Wikipedia would be. (Biconnected graph?) If having a definition for this specific concept is useful, can someone add it to the glossary and update the redirects? And if not, can someone update the redirects to point to something more useful? Thanks. —Gordon P. Hemsley→✉ 06:49, 23 November 2016 (UTC)

We don't have a separate article on the graphs that are defined as the union of three interior-vertex-disjoint paths with shared endpoints, but they're called theta-graphs (because they look like Θ) and this is one of them. We do have an article theta-graph but it's on an unrelated topic. The appropriate target is def.1 of "theta". I don't think the specific graph described by MathWorld has enough significance for a separate mention. —David Eppstein (talk) 07:39, 23 November 2016 (UTC)

Symbols section

Would it make more sense to name the !$@ section to something like "Symbols and Notation?" I honestly thought my browser was glitching out and wasn't displaying that section properly. Also it could use some clean up.

Austin.erwin (talk) 23:55, 28 February 2018 (UTC)

 Fixed (you could have done this by yourself). D.Lazard (talk) 08:48, 1 March 2018 (UTC)

Block

The entry for "block" has four separate terms. I split it into 4 definitions, all under the heading "block". I also corrected the erroneous definition of a block, which said it has a cycle (if it has 2 or more vertices). I also modified the other definitions, which had errors or were too specialized.

Question: Why should "block graph of a graph", "block graph", and "block-cut graph of a graph" all be under "block" but have their names concealed by not being boldfaced? I think this makes it harder for the uninitiated (and some of the initiated). Zaslav (talk) 03:17, 27 March 2019 (UTC)

Requested move 13 February 2021

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: page moved. Strong consensus. Andrewa (talk) 18:56, 25 February 2021 (UTC)

---

Glossary of graph theory terms → Glossary of graph theory – For simplicity. Compare with Glossary of mathematics. St.nerol (talk) 15:50, 13 February 2021 (UTC)

• Support as "terms" is redundant since a glossary is a list of terms. Rreagan007 (talk) 18:29, 13 February 2021 (UTC)
• Support simpler and still meaningful title. —David Eppstein (talk) 21:57, 13 February 2021 (UTC)
• Comment: I kind of like the shorter title, but "terms" was added on in 2016 to fit with MOS:NCGLOSSARIES. --Lasunncty (talk) 05:04, 14 February 2021 (UTC)

I see. But MOS:NCGLOSSARIES seems to be quite weakly followed in practice. Sometimes it gives a better title, somtimes not, as arguably, in this case, it didn't. For example, "Glossary of video game terms" is fine, but I think no one would suggest that "Glossary of astronomy" be moved to "Glossary of astronomical terms"! St.nerol (talk) 10:30, 25 February 2021 (UTC)

• Closing comment: We should IMO review MOS:NCGLOSSARIES in view of this decision. Andrewa (talk) 18:56, 25 February 2021 (UTC)

---

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Flashcards link

We wanted to learn all these terms in a flashcard format so we built one and made it freely available. Thought it would be helpful for anyone who wanted to learn the content of this glossary in a flashcard format like Anki to also be able to discover that they exist and have access to it from the source.

Was going to suggest it to be added in an external links section like the following but as it is linking to our own site, following the instructions of the Wikipedia guidelines, thought it would be best to leave this in the talk page for other contributors to see if it would be relevant or see if there was a better place/format to put it

• Flashcard version of the Wikipedia Glossary of graph theory in an Anki-readable format

Darigov Research (talk) 19:14, 20 March 2021 (UTC)

Symbol for Clique number

It seems it should be omega instead of kappa, as the article says (clique number). Not 100% sure why it says kappa, so not editing myself. — Preceding unsigned comment added by Mtzguido (talk • contribs) 23:23, 30 March 2022 (UTC)

I think you're right. I'm not sure why either, but I'll switch to omega. —David Eppstein (talk) 00:39, 31 March 2022 (UTC)

"Edge(graph theory)" listed at Redirects for discussion

An editor has identified a potential problem with the redirect Edge(graph theory) and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 April 6#Edge(graph theory) until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Steel1943 (talk) 19:02, 6 April 2022 (UTC)

Term for child with zero, one, or two or more siblings

I have searched the internet for terms which describe the number of siblings of a node, in the context of a rooted tree. I found the term "unary child", but I do not believe that this is correct usage of the term "unary" since in every other context, it describes the number of children of a node, not the number of siblings. I hope that this group will know the answer. In the context of a rooted tree, are there terms for:

• A child node which has no siblings
• A child node which has exactly one sibling
• A child node which has two or more siblings

Rossbundy (talk) 16:26, 27 May 2023 (UTC)

Add entries for head and tail

We try to reference our usage of the terms head and tail by links to this glossary. Althoug they are in full explained in the entry for arrow, they have no own entries. These could either rephrase the explanation or link to arrow. The point being, that links to #head and #tail would work as prepared in the entry for #arrow.

Should we just edit the glossary? It seems so well-maintained we think there might be a system to the 'missing' entries that we have not yet grasped. 2003:C2:872A:E800:2C16:FB66:F308:4213 (talk) 10:23, 24 November 2023 (UTC)