Editing Glossary of graph theory (section)

==T==
{{glossary}}

{{term|theta}}
{{defn|no=1|A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.<ref>{{citation
 | last = Bondy | first = J. A.
 | contribution = The "graph theory" of the Greek alphabet
 | doi = 10.1007/BFb0067356
 | mr = 0335362
 | pages = 43–54
 | publisher = Springer
 | series = Lecture Notes in Mathematics
 | title = Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)
 | volume = 303
 | year = 1972| isbn = 978-3-540-06096-3
 }}</ref>}}
{{defn|no=2|The [[theta graph]] of a collection of points in the Euclidean plane is constructed by constructing a system of cones surrounding each point and adding one edge per cone, to the point whose projection onto a central ray of the cone is smallest.}}
{{defn|no=3|The [[Lovász number]] or Lovász theta function of a graph is a graph invariant related to the clique number and chromatic number that can be computed in polynomial time by semidefinite programming.}}

{{term|Thomsen graph}}
{{defn|The [[Thomsen graph]] is a name for the [[complete bipartite graph]] <math>K_{3,3}</math>.}}

{{term|topological}}
{{defn|no=1|A [[topological graph]] is a representation of the vertices and edges of a graph by points and curves in the plane (not necessarily avoiding crossings).}}
{{defn|no=2|[[Topological graph theory]] is the study of graph embeddings.}}
{{defn|no=3|[[Topological sorting]] is the algorithmic problem of arranging a directed acyclic graph into a topological order, a vertex sequence such that each edge goes from an earlier vertex to a later vertex in the sequence.}}

{{term|totally disconnected}}
{{defn|Synonym for {{gli|edgeless graph|edgeless}}.}}

{{term|tour}}
{{defn|A closed trail, a {{gli|walk}} that starts and ends at the same vertex and has no repeated edges. Euler tours are tours that use all of the graph edges; see {{gli|Eulerian}}.}}

{{term|tournament}}
{{defn|A [[Tournament (graph theory)|tournament]] is an orientation of a complete graph; that is, it is a directed graph such that every two vertices are connected by exactly one directed edge (going in only one of the two directions between the two vertices).}}

{{term|traceable}}
{{defn|A [[traceable graph]] is a graph that contains a Hamiltonian path.}}

{{term|trail}}
{{defn|A {{gli|walk}} without repeated edges.}}

{{term|transitive}}
{{defn|Having to do with the [[transitive property]]. The [[transitive closure]] of a given directed graph is a graph on the same vertex set that has an edge from one vertex to another whenever the original graph has a path connecting the same two vertices. A [[transitive reduction]] of a graph is a minimal graph having the same transitive closure; directed acyclic graphs have a unique transitive reduction. A [[transitive orientation]] is an orientation of a graph that is its own transitive closure; it exists only for [[comparability graph]]s.}}

{{term|transpose}}
{{defn|The [[transpose graph]] of a given directed graph is a graph on the same vertices, with each edge reversed in direction. It may also be called the converse or reverse of the graph.}}

{{term|tree}}
{{defn|no=1|A [[Tree (graph theory)|tree]] is an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices.}}
{{defn|no=2|A [[k-tree|{{mvar|k}}-tree]] is a graph formed by gluing {{math|(''k'' + 1)}}-cliques together on shared {{mvar|k}}-cliques. A tree in the ordinary sense is a {{math|1}}-tree according to this definition.}}

{{term|tree decomposition}}
{{defn|A [[tree decomposition]] of a graph {{mvar|G}} is a tree whose nodes are labeled with sets of vertices of {{mvar|G}}; these sets are called bags. For each vertex {{mvar|v}}, the bags that contain {{mvar|v}} must induce a subtree of the tree, and for each edge {{mvar|uv}} there must exist a bag that contains both {{mvar|u}} and {{mvar|v}}. The width of a tree decomposition is one less than the maximum number of vertices in any of its bags; the treewidth of {{mvar|G}} is the minimum width of any tree decomposition of {{mvar|G}}.}}

{{term|treewidth}}
{{defn|The [[treewidth]] of a graph {{mvar|G}} is the minimum width of a tree decomposition of {{mvar|G}}. It can also be defined in terms of the clique number of a [[chordal completion]] of {{mvar|G}}, the order of a [[Haven (graph theory)|haven]] of {{mvar|G}}, or the order of a [[Bramble (graph theory)|bramble]] of {{mvar|G}}.}}

{{term|triangle}}
{{defn|A cycle of length three in a graph. A [[triangle-free graph]] is an undirected graph that does not have any triangle subgraphs.}}

{{term|trivial}}
{{defn|A trivial graph is a graph with 0 or 1 vertices.<ref>{{citation |last=Diestel |first=Reinhard |url=http://link.springer.com/10.1007/978-3-662-53622-3 |title=Graph Theory |date=2017 |publisher=Springer Berlin Heidelberg |isbn=978-3-662-53621-6 |series=Graduate Texts in Mathematics |volume=173 |location=Berlin, Heidelberg |language=en |doi=10.1007/978-3-662-53622-3 |page=2}}</ref> A graph with 0 vertices is also called [[null graph]].}}

{{term|Turán}}
{{defn|no=1|[[Pál Turán]]}}
{{defn|no=2|A [[Turán graph]] is a balanced complete multipartite graph.}}
{{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}}