Content deleted Content added
No edit summary |
→K: see e.g. https://mathworld.wolfram.com/VertexConnectivity.html. The clique number is usually denoted ω(G) |
||
| (22 intermediate revisions by 14 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 126:
{{term|bramble}}
{{defn|A [[Bramble (graph theory)|bramble]] is a collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an edge. The order of a bramble is the smallest size of a set of vertices that has a nonempty intersection with all of the subgraphs. The treewidth of a graph is the maximum order of any of its brambles.}}
{{defn|A path of degree-two vertices, ending at vertices whose degree is unequal to two.<ref>{{citation
| last = van der Holst | first = Hein
| date = March 2009
| doi = 10.1016/j.jctb.2008.10.002
| issue = 2
| journal = Journal of Combinatorial Theory, Series B
| pages = 512–530
| publisher = Elsevier BV
| title = A polynomial-time algorithm to find a linkless embedding of a graph
| volume = 99}}</ref>}}
{{term|branch-decomposition}}
Line 135 ⟶ 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|
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 174 ⟶ 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 279 ⟶ 295:
{{term|connected}}
{{defn|A [[Connectivity (graph theory)|connected graph]] is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), [[k-vertex-connected graph|{{mvar|k}}-vertex-connected graphs]] (removing fewer than {{mvar|k}} vertices cannot disconnect the graph), and [[k-edge-connected graph|{{mvar|k}}-edge-connected graphs]] (removing fewer than {{mvar|k}} edges cannot disconnect the graph).}}
{{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 353 ⟶ 375:
{{term|depth}}
{{defn|The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use ''depth'' as a synonym for the ''level'' of a node.<ref>{{
{{term|diameter}}
Line 408 ⟶ 430:
{{defn|no=1|Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.}}
{{defn|no=2|The disjoint union of two or more graphs is a graph whose vertex and edge sets are the [[disjoint union]]s of the corresponding sets.}}
{{term|dissociation number}}
{{defn|A subset of vertices in a graph ''G'' is called ''dissociation'' if it induces a [[Glossary of graph theory#subgraph|subgraph]] with maximum [[Degree (graph theory)|degree]] 1.}}
{{term|distance}}
Line 715 ⟶ 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 724 ⟶ 756:
{{term|kappa|''κ''}}
{{defn|{{math|''κ''(''G'')}} (using the Greek letter kappa)
{{term|kernel}}
Line 752 ⟶ 784:
{{term|level}}
{{defn|no=1|This is the ''depth'' of a node plus 1, although some<ref name="NIST Level">{{
{{defn|no=2|A set of all node having the same level or depth.<ref name="NIST Level"/>}}
Line 815 ⟶ 847:
{{term|monotone}}
{{defn|A monotone property of graphs is a property that is closed under subgraphs: if {{mvar|G}} has a
{{term|Moore graph}}
Line 1,017 ⟶ 1,049:
==S==
{{glossary}}
▲{{term|second order}}
{{defn|The second order [[logic of graphs]] is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in which variables can only represent vertices.}}▼
{{term|saturated}}
Line 1,026 ⟶ 1,055:
{{term|searching number}}
{{defn|Node searching number is a synonym for {{gli|pathwidth}}.}}
{{term|second order}}
▲{{defn|The second order [[logic of graphs]] is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in which variables can only represent vertices.}}
{{term|self-loop}}
Line 1,035 ⟶ 1,067:
{{term|separation number}}
{{defn|Vertex separation number is a synonym for {{gli|pathwidth}}.}}
{{term|sibling}}
{{defn|In a rooted tree, a sibling of a vertex {{mvar|v}} is a vertex which has the same parent vertex as {{mvar|v}}.}}
{{anchor|simple graph}}{{term|simple}}
Line 1,044 ⟶ 1,079:
{{term|size}}
{{defn|The size of a graph {{mvar|G}} is the number of its edges, {{math|{{!}}''E''(''G''){{!}}}}.<ref>{{
{{term|small-world network}}
{{defn|A [[small-world network]] is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a graph where the typical distance ''L'' between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes ''N'' in the network
{{term|snark}}
Line 1,075 ⟶ 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}}
Line 1,179 ⟶ 1,215:
{{term|trivial}}
{{defn|A trivial graph is a graph with 0 or 1 vertices.<ref>{{
{{term|Turán}}
Line 1,186 ⟶ 1,222:
{{defn|no=3|[[Turán's theorem]] states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.}}
{{defn|no=4|[[Turán's brick factory problem]] asks for the minimum number of crossings in a drawing of a complete bipartite graph.}}
{{term|twin}}
{{defn|Two vertices {{mvar|u,v}} are true twins if they have the same closed {{gli|neighborhood}}: {{math|''N''{{sub|''G''}}[''u''] {{=}} ''N''{{sub|''G''}}[''v'']}} (this implies {{mvar|u}} and {{mvar|v}} are neighbors), and they are false twins if they have the same open neighborhood: {{math|''N''{{sub|''G''}}(''u'') {{=}} ''N''{{sub|''G''}}(''v''))}} (this implies {{mvar|u}} and {{mvar|v}} are not neighbors).}}
{{glossary end}}
Line 1,191 ⟶ 1,230:
==U==
{{glossary}}
{{term|unary vertex}}
{{defn|In a rooted tree, a unary vertex is a vertex which has exactly one child vertex.}}
{{term|undirected}}
Line 1,256 ⟶ 1,298:
{{term|walk}}
{{defn|A [[Path (graph theory)#Walk, trail, path|walk]] is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]]. Walks are also sometimes called ''chains''.<ref>{{
{{term|weakly connected}}
| |||