Editing Glossary of graph theory (section)

==S==
{{glossary}}

{{term|saturated}}
{{defn|See {{gli|matching}}.}}

{{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}}
{{defn|Synonym for {{gli|loop}}.}}

{{term|separating vertex}}
{{defn|See {{gli|articulation point}}.}}

{{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}}
{{defn|no=1|A [[simple graph]] is a graph without loops and without multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise.}}
{{defn|no=2|A simple path or a simple cycle is a path or cycle that has no repeated vertices and consequently no repeated edges.}}

{{term|sink}}
{{defn|A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).}}

{{term|size}}
{{defn|The size of a graph {{mvar|G}} is the number of its edges, {{math|{{!}}''E''(''G''){{!}}}}.<ref>{{citation|last=Harris|first=John M.|title=Combinatorics and Graph Theory|year=2000|publisher=Springer-Verlag|location=New York|isbn=978-0-387-98736-1|page=5|url=https://www.springer.com/gp/book/9780387797106}}</ref> The variable {{mvar|m}} is often used for this quantity. See also ''order'', the number of vertices.}}

{{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<ref>{{citation|title=Collective dynamics of 'small-world' networks|first1=Duncan J.|last1=Watts|first2=Steven H.|last2=Strogatz|date=June 1998|journal=Nature|volume=393|issue=6684|pages=440–442|doi=10.1038/30918|bibcode=1998Natur.393..440W|pmid=9623998|s2cid=4429113}}</ref>}}

{{term|snark}}
{{defn|A [[Snark (graph theory)|snark]] is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.}}

{{term|source}}
{{defn|A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).}}

{{term|space}}
{{defn|In [[algebraic graph theory]], several [[vector spaces]] over the [[GF(2)|binary field]] may be associated with a graph. Each has sets of edges or vertices for its vectors, and [[symmetric difference]] of sets as its vector sum operation. The [[edge space]] is the space of all sets of edges, and the [[vertex space]] is the space of all sets of vertices. The [[cut space]] is a subspace of the edge space that has the cut-sets of the graph as its elements. The [[cycle space]] has the Eulerian spanning subgraphs as its elements.}}

{{term|spanner}}
{{defn|A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include [[geometric spanner]]s, graphs whose vertices are points in a geometric space; [[tree spanner]]s, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.}}

{{term|spanning}}
{{defn|A subgraph is spanning when it includes all of the vertices of the given graph.
Important cases include [[spanning tree]]s, spanning subgraphs that are trees, and [[perfect matching]]s, spanning subgraphs that are matchings. A spanning subgraph may also be called a [[Graph factorization|factor]], especially (but not only) when it is regular.}}

{{term|sparse}}
{{defn|A [[sparse graph]] is one that has few edges relative to its number of vertices. In some definitions the same property should also be true for all subgraphs of the given graph.}}

{{term|spectral}}
{{term|spectrum|multi=y}}
{{defn|The spectrum of a graph is the collection of [[eigenvalue]]s of its adjacency matrix. [[Spectral graph theory]] is the branch of graph theory that uses spectra to analyze graphs. See also spectral {{gli|expansion}}.}}

{{term|split}}
{{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}}
{{defn|no=1|The square of a graph {{mvar|G}} is the [[graph power]] {{math|''G''<sup>2</sup>}}; in the other direction, {{mvar|G}} is the square root of {{math|''G''<sup>2</sup>}}. The [[half-square]] of a bipartite graph is the subgraph of its square induced by one side of the bipartition.}}
{{defn|no=2|A [[squaregraph]] is a planar graph that can be drawn so that all bounded faces are 4-cycles and all vertices of degree ≤ 3 belong to the outer face.}}
{{defn|no=3|A square grid graph is a [[lattice graph]] defined from points in the plane with integer coordinates connected by unit-length edges.}}

{{term|stable}}
{{defn|A stable set is a synonym for an {{gli|independent|independent set}}.}}

{{term|star}}
{{defn|A [[Star (graph theory)|star]] is a tree with one internal vertex; equivalently, it is a complete bipartite graph {{math|''K''<sub>1,''n''</sub>}} for some {{math|''n'' ≥ 2}}. The special case of a star with three leaves is called a claw.}}

{{term|strength}}
{{defn|The [[strength of a graph]] is the minimum ratio of the number of edges removed from the graph to components created, over all possible removals; it is analogous to toughness, based on vertex removals.}}

{{term|strong}}
{{defn|no=1|For strong connectivity and [[strongly connected component]]s of directed graphs, see {{gli|connected}} and {{gli|component}}. A [[strong orientation]] is an orientation that is strongly connected; see {{gli|orientation}}.}}
{{defn|no=2|For the [[strong perfect graph theorem]], see {{gli|perfect}}.}}
{{defn|no=3|A [[strongly regular graph]] is a regular graph in which every two adjacent vertices have the same number of shared neighbours and every two non-adjacent vertices have the same number of shared neighbours.}}
{{defn|no=4|A [[strongly chordal graph]] is a chordal graph in which every even cycle of length six or more has an odd chord.}}
{{defn|no=5|A strongly perfect graph is a graph in which every induced subgraph has an independent set meeting all maximal cliques. The [[Meyniel graph]]s are also called "very strongly perfect graphs" because in them, every vertex belongs to such an independent set.}}

{{term|subforest}}
{{defn|A subgraph of a {{gli|forest}}.}}

{{term|subgraph}}
{{defn|A subgraph of a graph {{mvar|G}} is another graph formed from a subset of the vertices and edges of {{mvar|G}}. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset.}}

{{term|subtree}}
{{defn|A subtree is a connected subgraph of a tree. Sometimes, for rooted trees, subtrees are defined to be a special type of connected subgraph, formed by all vertices and edges reachable from a chosen vertex.}}

{{term|successor}}
{{defn|A {{gli|vertex}} coming after a given vertex in a {{gli|directed path}}.}}

{{term|superconcentrator}}
{{defn|A superconcentrator is a graph with two designated and equal-sized subsets of vertices {{mvar|I}} and {{mvar|O}}, such that for every two equal-sized subsets {{mvar|S}} of {{mvar|I}} and {{mvar|T}} of {{mvar|O}} there exists a family of disjoint paths connecting every vertex in {{mvar|S}} to a vertex in {{mvar|T}}. Some sources require in addition that a superconcentrator be a directed acyclic graph, with {{mvar|I}} as its sources and {{mvar|O}} as its sinks.}}

{{term|supergraph}}
{{defn|A graph formed by adding vertices, edges, or both to a given graph. If {{mvar|H}} is a subgraph of {{mvar|G}}, then {{mvar|G}} is a supergraph of {{mvar|H}}.}}

{{glossary end}}