Wikipedia

Glossary of graph theory: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
→‎K: see e.g. https://mathworld.wolfram.com/VertexConnectivity.html. The clique number is usually denoted ω(G)
 
(8 intermediate revisions by 6 users not shown)
Line 67:
 
{{term|articulation point|[[articulation point]]}}
{{defn|A {{gli|vertex}} in a {{gli|connected graph}} whose removal would {{gli|disconnect}} the graph. More generally, a vertex whose removal increases the number of {{gli|component}}s.}}
 
{{term|k-ary|-ary}}
Line 147:
{{term|bridge}}
{{defn|no=1|A [[Bridge (graph theory)|bridge]], isthmus, or cut edge is an edge whose removal would disconnect the graph. A bridgeless graph is one that has no bridges; equivalently, a 2-edge-connected graph.}}
{{defn|no=2|EspeciallyA inbridge theof contexta ofsubgraph [[planarity''H'' testing]],is a bridgemaximal connected subgraph separated from the rest of athe cyclegraph by ''H''. That is, it is a maximal subgraph that is edge-disjoint from the cycle''H'' and in which each two vertices and edges belong to a path that is internally disjoint from the cycle''H''. A chord''H'' ismay be a one-edgeset bridgeof vertices. A [[peripheral cycle]]chord is a cycle with at most one-edge bridge; it. must be a face in any planar embedding of its graph.}}
In [[planarity testing]], ''H'' is a cycle and a [[peripheral cycle]] is a cycle with at most one bridge; it must be a face boundary in any planar embedding of its graph.}}
{{defn|no=3|A bridge of a cycle can also mean a path that connects two vertices of a cycle but is shorter than either of the paths in the cycle connecting the same two vertices. A [[bridged graph]] is a graph in which every cycle of four or more vertices has a bridge.}}
 
{{term|bridgeless}}
{{defn|A [[bridgeless graph|bridgeless]] or isthmus-free graph is a graph that has no bridge edges (i.e., isthmi); that is, each connected component is a [[k-edge-connected graph|2-edge-connected graph]].}}
 
{{term|butterfly}}
Line 186 ⟶ 187:
{{term|center}}
{{defn|The [[Graph center|center]] of a graph is the set of vertices of minimum {{gli|eccentricity}}.}}
 
{{term|centroid}}
{{defn|A [[Centroid (graph theory)|centroid]] of a tree is a vertex {{mvar|v}} such that if rooted at {{mvar|v}}, no other vertex has subtree size greater than half the size of the tree.}}
 
{{term|chain}}
Line 294 ⟶ 298:
{{term|connected component}}
{{defn|Synonym for {{gli|component}}.}}
 
{{term|contraction}}
{{defn|[[Edge contraction]] is an elementary operation that removes an edge from a graph while merging the two vertices that it previously joined. Vertex contraction (sometimes called vertex identification) is similar, but the two vertices are not necessarily connected by an edge. Path contraction occurs upon the set of edges in a path that contract to form a single edge between the endpoints of the path. The inverse of edge contraction is vertex splitting.}}
 
{{term|converse}}
Line 733 ⟶ 740:
{{defn|Synonym for {{gli|bridge}}, in the sense of an edge whose removal disconnects the graph.}}
 
{{glossary end}}
 
==J==
{{glossary}}
 
{{term|join}}
{{defn|The [[Graph operations#Binary operations|join]] of two graphs is formed from their [[#disjoint|disjoint union]] by adding an edge from each vertex of one graph to each vertex of the other. Equivalently, it is the complement of the disjoint union of the complements.}}
{{glossary end}}
 
Line 742 ⟶ 756:
 
{{term|kappa|''κ''}}
{{defn|{{math|''κ''(''G'')}} (using the Greek letter kappa) iscan therefer order ofto the [[maximumvertex cliqueconnectivity]] inof {{mvar|G}}; seeor to the {{gli|clique|clique number}} of {{mvar|G}}.}}
 
{{term|kernel}}
Line 833 ⟶ 847:
 
{{term|monotone}}
{{defn|A monotone property of graphs is a property that is closed under subgraphs: if {{mvar|G}} has a hereditarymonotone property, then so must every subgraph of {{mvar|G}}. Compare {{gli|hereditary}} (closed under induced subgraphs) or ''minor-closed'' (closed under minors).}}
 
{{term|Moore graph}}
Line 1,096 ⟶ 1,110:
{{defn|no=1|A [[split graph]] is a graph whose vertices can be partitioned into a clique and an independent set. A related class of graphs, the double split graphs, are used in the proof of the strong perfect graph theorem.}}
{{defn|no=2|A [[split (graph theory)|split]] of an arbitrary graph is a partition of its vertices into two nonempty subsets, such that the edges spanning this cut form a complete bipartite subgraph. The splits of a graph can be represented by a tree structure called its ''split decomposition''. A split is called a strong split when it is not crossed by any other split. A split is called nontrivial when both of its sides have more than one vertex. A graph is called prime when it has no nontrivial splits.}}
{{defn|no=3|[[Edge contraction#Vertex cleaving|Vertex splitting]] (sometimes called vertex cleaving) is an elementary graph operation that splits a vertex into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. The inverse of vertex splitting is vertex contraction.}}
 
{{term|square}}
Retrieved from "https://en.wikipedia.org/wiki/Glossary_of_graph_theory"