Lecture
A block graph (clique tree) — is a type of undirected graph in which every biconnected component (block) is a clique .Block graphs can be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.
A clique of an undirected graph is a subset of its vertices, any two of which are joined by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions with graphs. Cliques are also studied in computer science — the problem of determining whether a clique of a given size exists in a graph (the clique problem) is NP-complete. Despite this difficulty, many algorithms for finding cliques are studied.
Block graph
Block graphs — are exactly those graphs in which, for every four vertices 
, 
and 
, the largest two of the three distances 
, 
, 
are always equal[
They can also be characterized by forbidden subgraphs, as the graphs that contain no diamond or cycle of length four or more as an induced subgraph. That is, they are chordal graphs without diamonds . They are also Ptolemaic graphs (chordal distance-hereditary graphs ), in which any two vertices at distance two are joined by a unique shortest path, and chordal graphs in which any two cliques have at most one vertex in common.
A graph 
is a block graph if and only if the intersection of any two connected subsets of vertices of the graph is either empty or connected. Thus, the connected subsets of vertices in a connected block graph form a convex geometry[en], and no other type of graph has this property Because of this property, in a connected block graph any set of vertices has a unique minimal connected superset, the closure of the set in the convex geometry. Connected block graphs — are exactly those graphs in which there is a unique induced path connecting any two pairs of vertices .
Block graphs are chordal and distance-hereditary graphs. Distance-hereditary graphs — are graphs in which any two induced paths between two vertices have the same length, which is weaker than the requirement for block graphs of having a unique induced path between any two vertices. Since both chordal graphs and distance-hereditary graphs are subclasses of perfect graphs, block graphs are also perfect.
Every tree is a block graph. Another example of a class of block graphs is given by the windmill graphs.
Every block graph has boxicity at most two
Block graphs are an example of pseudo-median graphs — for any three vertices, either there is a unique vertex lying on the three shortest paths between these three vertices, or there is a unique triangle whose edges lie on these shortest paths.
The line graphs of trees — are the block graphs in which every cut vertex is incident to at most two blocks, or, equivalently, the claw-free block graphs. The line graphs of trees are used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small as possible
The block graph of a given graph (denoted 
) — is the intersection graph of the blocks of the graph : has a vertex for each biconnected component of the graph , and two vertices of the graph are adjacent if the corresponding two blocks share (have in common) a hinge (in Harary's terms — a cut vertex). If 
— is a graph with a single vertex, then 
is by definition the empty graph. is certainly a block graph — it has one biconnected component for each cut vertex of the graph , and each biconnected component formed in this way is a clique. Conversely, every block graph is the graph for some . If — is a tree, then coincides with the line graph of the graph .
The graph 
has a vertex for each cut vertex of the graph . Two vertices are adjacent in if they belong to the same block in
Comments