Editing Glossary of graph theory (section)

==B==
{{glossary}}

{{term|bag}}
{{defn|One of the sets of vertices in a {{gli|tree decomposition}}.}}

{{term|balanced}}
{{defn|A bipartite or multipartite graph is balanced if each two subsets of its vertex partition have sizes within one of each other.}}

{{term|ball}}
{{defn|A ball (also known as a neighborhood ball or distance ball) is the set of all vertices that are at most distance r from a vertex. More formally, for a given vertex v and radius r, the ball B(v,r) consists of all vertices whose shortest path distance to v is less than or equal to r.}}

{{term|bandwidth}}
{{defn|The [[Graph bandwidth|bandwidth]] of a graph {{mvar|G}} is the minimum, over all orderings of vertices of {{mvar|G}}, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of {{mvar|G}}, chosen to minimize the clique size.}}

{{term|biclique}}
{{defn|Synonym for [[complete bipartite graph]] or complete bipartite subgraph; see {{gli|complete}}.}}

{{term|biconnected}}
{{defn|Usually a synonym for [[k-vertex-connected graph|{{math|2}}-vertex-connected]], but sometimes includes ''K''<sub>2</sub> though it is not 2-connected. See {{gli|connected}}; for [[biconnected component]]s, see {{gli|component}}.}}

{{term|binding number}}
{{defn|The smallest possible ratio of the number of neighbors of a proper subset of vertices to the size of the subset.<ref>{{Citation | first = D. R. | last = Woodall | title = The Binding Number of a Graph and its Anderson Number | journal= J. Combin. Theory Ser. B| year = 1973 | volume = 15 | issue = 3 |pages=225–255 | doi=10.1016/0095-8956(73)90038-5| doi-access = free }}</ref>}}

{{term|bipartite}}
{{defn|A [[bipartite graph]] is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written {{math|1=''G'' = (''U'',''V'',''E'')}} where {{mvar|U}} and {{mvar|V}} are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.}}

{{term|biregular}}
{{defn|A [[biregular graph]] is a {{gli|bipartite}} graph in which there are only two different vertex degrees, one for each set of the vertex bipartition.}}

{{term|block}}
{{defn|no=1|A block of a graph {{mvar|G}} is a maximal subgraph which is either an isolated vertex, a bridge edge, or a 2-connected subgraph. If a block is 2-connected, every pair of vertices in it belong to a common cycle. Every edge of a graph belongs in exactly one block.}}
{{defn|no=2|The block graph of a graph {{mvar|G}} is another graph whose vertices are the blocks of {{mvar|G}}, with an edge connecting two vertices when the corresponding blocks share an articulation point; that is, it is the intersection graph of the blocks of {{mvar|G}}.  The block graph of any graph is a {{gli|forest}}.}}
{{defn|no=3|The block-cut (or block-cutpoint) graph of a graph {{mvar|G}} is a bipartite graph where one partite set consists of the cut-vertices of {{mvar|G}}, and the other has a vertex <math>b_i</math> for each block <math>B_i</math> of {{mvar|G}}. When {{mvar|G}} is connected, its block-cutpoint graph is a tree.}}
{{defn|no=4|A [[block graph]] (also called a clique tree if connected, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete graphs. A {{gli|forest}} is a block graph; so in particular the block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.}}

{{term|bond}}
{{defn|A {{gli|minimal}} {{gli|cut-set}}: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.}}

{{term|book}}
{{defn|no=1|A [[Book (graph theory)|book]], book graph, or triangular book is a complete tripartite graph {{math|''K''<sub>1,1,''n''</sub>}}; a collection of {{mvar|n}} triangles joined at a shared edge.}}
{{defn|no=2|Another type of graph, also called a book, or a quadrilateral book, is a collection of {{math|4}}-cycles joined at a shared edge; the Cartesian product of a star with an edge.}}
{{defn|no=3|A [[book embedding]] is an embedding of a graph onto a topological book, a space formed by joining a collection of half-planes along a shared line. Usually, the vertices of the embedding are required to be on the line, which is called the spine of the embedding, and the edges of the embedding are required to lie within a single half-plane, one of the pages of the book.}}

{{term|boundary}}
{{defn|no=1| In a [[graph embedding]], a boundary walk is the subgraph containing all incident edges and vertices to a {{gli|face}}.}}

{{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.}}

{{term|branch}}
{{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}}
{{defn|A [[branch-decomposition]] of {{mvar|G}} is a hierarchical clustering of the edges of {{mvar|G}}, represented by an unrooted binary tree with its leaves labeled by the edges of {{mvar|G}}. The width of a branch-decomposition is the maximum, over edges {{mvar|e}} of this binary tree, of the number of shared vertices between the subgraphs determined by the edges of {{mvar|G}} in the two subtrees separated by {{mvar|e}}. The branchwidth of {{mvar|G}} is the minimum width of any branch-decomposition of {{mvar|G}}.}}

{{term|branchwidth}}
{{defn|See {{gli|branch-decomposition}}.}}

{{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|A bridge of a subgraph ''H'' is a maximal connected subgraph separated from the rest of the graph by ''H''.  That is, it is a maximal subgraph that is edge-disjoint from ''H'' and in which each two vertices and edges belong to a path that is internally disjoint from ''H''.  ''H'' may be a set of vertices.  A chord is a one-edge bridge.  
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}}
{{defn|no=1|The [[butterfly graph]] has five vertices and six edges; it is formed by two triangles that share a vertex.}}
{{defn|no=2|The butterfly network is a graph used as a network architecture in distributed computing, closely related to the [[cube-connected cycles]].}}

{{glossary end}}