Fact-checked by Grok 2 weeks ago

Block graph

A block graph is a simple undirected graph in which every biconnected component, known as a block, is a complete graph or clique.^[1] These graphs were first characterized by Frank Harary in 1963 as a class constructed by identifying vertices of complete graphs under specific conditions, forming a collection closed under disjoint unions and vertex identification.^[1] Block graphs generalize trees, as the blocks in a tree are edges (which are complete graphs K_2), and they exhibit unique shortest paths between any pair of vertices, making them a subclass of distance-hereditary graphs.^[2]^[3] They can be characterized as the diamond-free chordal graphs, or by metric properties where the shortest path between vertices is unique and adjacent vertices induce cliques in specific neighborhoods.^[4]^[5] Additionally, block graphs are precisely the intersection graphs of the blocks of arbitrary undirected graphs.^[1] In applications, block graphs arise in metric graph theory for modeling hierarchical structures, in molecular chemistry to represent certain molecular graphs, and in phylogenetics as models for evolutionary trees with reticulation.^[6] They also feature in algorithmic problems, such as efficient computation of centers and medians due to their tree-like block structure, and in coloring studies where equitable colorings can be determined in linear time.

Definition and Fundamentals

Definition

A block graph is an undirected graph in which every biconnected component, known as a block, is a complete graph or clique.^[7] This characterization, established by Harary in 1963,^[8] ensures that the graph's connectivity is structured around fully connected subgraphs without internal articulation points. Blocks in this context are the maximal biconnected subgraphs of the graph, meaning they are the largest possible induced subgraphs that remain connected after the removal of any single vertex and contain no articulation points of their own. In a block graph, the requirement that each such block forms a clique implies that within each block, every pair of vertices is adjacent, providing a rigid structure to the graph's 2-connected parts. These blocks intersect only at articulation points, or cut vertices, which are vertices whose removal increases the number of connected components.^[9] Block graphs can be constructed by starting with a collection of cliques and connecting them via shared articulation points, where each connection occurs at exactly one vertex per pair of cliques, forming a tree-like arrangement of these cliques known as a clique tree.^[9] This building process highlights their hierarchical nature, with the overall graph's connectivity determined by the articulation points linking the cliques.

Basic Terminology

Block graphs are studied in the context of undirected simple graphs, which consist of a finite set of vertices connected by edges without multiple edges between the same pair of vertices or self-loops.^[10] A graph is biconnected if it is connected and remains connected after the removal of any single vertex.^[10] Equivalently, every pair of vertices in a biconnected graph lies on a common cycle.^[10] A cut vertex, also known as an articulation point, is a vertex whose removal, along with its incident edges, increases the number of connected components in the graph.^[10] Cut vertices play a key role in the decomposition of a connected graph into its blocks: the blocks are the maximal biconnected subgraphs, and each cut vertex belongs to multiple blocks, serving as the points where these blocks intersect and connect the overall structure.^[11] A biconnected component, often called a block, is a maximal biconnected subgraph of the graph; these components partition the edges of the graph such that every edge belongs to exactly one block.^[12] A clique in a graph is a subgraph that is complete, meaning every pair of distinct vertices in the subgraph is adjacent by an edge.^[13] A chordal graph is an undirected graph in which every cycle of length greater than or equal to four contains a chord, an edge connecting two non-adjacent vertices of the cycle.^[14] Chordal graphs admit a perfect elimination ordering, where vertices can be ordered such that, for each vertex, its later neighbors form a clique.^[15]

Examples and Special Cases

Illustrative Examples

A path graph P_n on n vertices, consisting of a sequence of n-1 edges connecting the vertices in a line, is a block graph because its blocks are the individual edges, each forming a complete graph K_2.^[16] Similarly, any tree is a block graph, as trees are connected acyclic graphs where every block is an edge, which is a K_2 clique.^[16] A complete graph K_n for n \geq 1 is a block graph, since it is 2-connected and the entire graph forms a single clique block.^[16] In particular, a cycle of length 3, or C_3, is isomorphic to K_3 and thus a block graph, but longer cycles like C_4 are not, as their single block is the cycle itself, which is not a clique. The windmill graph Wd(r, t), formed by taking t copies of the complete graph K_r (with r, t \geq 2) and identifying a single vertex from each copy as a common central vertex, is a block graph; here, the t cliques are the blocks, all sharing the cut vertex at the center. A cluster graph, which is a disjoint union of one or more complete graphs (cliques), is a block graph because each component is a single clique block with no cut vertices connecting different components. As a non-example, the diamond graph—formed by taking K_4 and removing one edge—fails to be a block graph, since its single 2-connected component contains an induced 4-cycle without all necessary chords to form a clique.^[17]

Subclasses and Variants

Trees represent a fundamental subclass of block graphs, characterized by the property that every block is a single edge, isomorphic to the complete graph K_2. This structure ensures the graph is acyclic and connected, with no cycles whatsoever, making trees the simplest non-trivial block graphs.^[18] Line graphs of trees constitute another significant subclass, specifically the claw-free block graphs, where no induced subgraph is isomorphic to K_{1,3} (a claw). In these graphs, vertices correspond to the edges of an underlying tree, and two vertices are adjacent if the corresponding edges share a common vertex in the tree; equivalently, every cut vertex is incident to at most two blocks. This subclass arises naturally in applications involving edge representations of tree structures.^[19] Triangular cacti form a specialized subclass of block graphs in which every block is a triangle, isomorphic to the complete graph K_3. These graphs consist of cycles of length three sharing vertices in a tree-like arrangement, ensuring planarity and outerplanarity properties inherent to cacti. Such structures are particularly useful in modeling certain geometric or chemical configurations.^[20] Probe block graphs introduce a partitioned variant of block graphs, where the vertex set is divided into probes P and non-probes N, with N forming an independent set. Adding all possible edges between pairs in N (while respecting the probe structure) yields a standard block graph, analogous to probe interval graphs in intersection graph theory. This variant facilitates studies in graph recognition and computational biology.^[21] Generalizations of block graphs include weighted variants, where vertices or edges carry non-negative weights while maintaining the clique-block property, enabling applications in optimization and metric spaces. Directed block graphs extend the concept to digraphs, defining blocks as maximal strongly 2-connected subgraphs that are complete digraphs, with the block-cut structure adapted to directed connectivity.^[22]^[23]

Characterizations

Structural Characterizations

Block graphs admit several structural characterizations in terms of graph-theoretic properties, particularly their relation to chordal graphs and forbidden induced subgraphs. A graph is a block graph if and only if it is chordal and diamond-free, where a chordal graph is one without induced cycles of length at least four, and a diamond is the complete graph K_4 minus one edge.^[24]^[7] Another characterization states that a connected graph is a block graph if and only if there is a unique induced path between every pair of vertices.^[25] This property reflects the tree-like arrangement of cliques in block graphs, where paths cannot branch in ways that create multiple induced routes without forming forbidden structures. In block graphs, any two maximal cliques intersect in at most one vertex, which is a cut vertex separating the blocks they belong to.^[26] This intersection property ensures that the structure remains acyclic in terms of clique overlaps beyond single points. A graph is a block graph if and only if it is chordal and every minimal vertex separator has size one (i.e., consists of a single vertex).^[27] To see this, note that in a chordal graph, minimal separators are cliques by definition; restricting them to singletons enforces the block structure where biconnected components are cliques connected at articulation points. Conversely, if a graph has only singleton minimal separators and is chordal, its blocks must be cliques, as any non-clique block would introduce a larger separator or an induced cycle. The forbidden induced subgraph characterization follows directly: block graphs are precisely the graphs without induced diamonds (and, by chordality, without induced cycles of length at least four).^[28]

Metric Characterizations

Block graphs satisfy a metric four-point condition analogous to that of tree metrics, reflecting their underlying tree-like structure composed of clique blocks connected at cut vertices. Specifically, for any four vertices u, v, x, y in a connected block graph G, the three distance sums d(u,v) + d(x,y), d(u,x) + d(v,y), and d(u,y) + d(v,x) have the property that the two largest are equal.^[29] This condition ensures that the distances behave additively along a unique "backbone" path in the block-cut tree of G, where deviations within cliques do not create alternative distance pairings that would violate the equality. The intuition behind this theorem is that any quartet of vertices partitions into two pairs whose paths either overlap on a common subpath (yielding equal large sums) or are disjoint in a tree fashion, preventing the strict inequality seen in graphs with cycles that shortcut distances. As a consequence of their structure, block graphs are geodetic graphs, meaning there exists a unique shortest path between every pair of vertices.^[30] This geodetic property stems from the fact that multiple shortest paths would require parallel routes through distinct blocks, which is impossible without creating non-clique biconnected components. Block graphs coincide with the subclass of Ptolemaic graphs—defined as the intersection of chordal and distance-hereditary graphs—where every pair of vertices at distance 2 admits a unique shortest path between them.^[31] In broader Ptolemaic graphs, multiple length-2 paths may exist due to intersecting induced paths, but the clique-block condition in block graphs enforces uniqueness by ensuring that any two non-adjacent vertices in the same block are directly connected, while inter-block paths of length 2 must traverse a single cut vertex without alternatives.

Properties

Graph-Theoretic Properties

Block graphs possess several important graph-theoretic properties stemming from their structural definition as graphs where every biconnected component is a clique. They are chordal, meaning that every cycle of length at least four induces a chord, which follows from the fact that any induced cycle longer than three would span multiple blocks without forming a complete subgraph, contradicting the clique property of blocks.^[32] This chordality ensures that block graphs are perfect, with the chromatic number \chi(G) equal to the clique number \omega(G) for every induced subgraph, a consequence of the perfect elimination ordering inherent in chordal graphs.^[32] Additionally, block graphs are distance-hereditary, a property where the distances between vertices in any induced connected subgraph match those in the original graph; this arises because the unique paths between vertices in block graphs, due to their tree-like block structure, preserve metric properties under induced subgraphs. As a subclass of both chordal and distance-hereditary graphs, which are themselves perfect, block graphs inherit perfection and exhibit \chi(G) = \omega(G).^[3] Block graphs have boxicity at most 2, allowing representation as the intersection graph of axis-aligned boxes in the plane (equivalently, the intersection of two interval graphs), which reflects their limited dimensional complexity compared to general chordal graphs.^[33] They are also quasi-median graphs, where for any three vertices u, v, w, median sets exist (possibly non-unique) that lie on the shortest paths between each pair, computable via the block structure.^[34] The class of block graphs is hereditary, meaning that every induced subgraph of a block graph is itself a block graph, as the biconnected components of the subgraph remain cliques.^[3] Furthermore, as chordal graphs, block graphs have treewidth exactly \omega(G) - 1, bounding the complexity of their tree decompositions by the size of the largest clique minus one.^[35]

Algorithmic Properties

Block graphs admit polynomial-time recognition algorithms. One approach is to verify that the graph is chordal, which can be tested in linear time using maximum cardinality search or lexicographic breadth-first search, and diamond-free, which can be recognized in O(n + m) time via algorithms that list simplicial vertices and check for induced diamonds.^[36] Since block graphs are precisely the diamond-free chordal graphs, this combined procedure recognizes them in linear time overall.^[21] An alternative recognition method computes the biconnected components in linear time using depth-first search and then verifies that each component induces a clique by checking that the number of edges equals the binomial coefficient of its vertex count choose two; this also runs in linear time, as the components partition the edges. Additionally, the P4-structure of a block graph—representing its modular decomposition or cotree-like hierarchy—can be recognized in linear time, enabling efficient structural analysis.^[37] As perfect graphs, block graphs allow the maximum independent set, graph coloring, and maximum clique problems to be solved in polynomial time using the ellipsoid method on the associated semidefinite programming formulations.^[38] More efficiently, as a subclass of chordal graphs, these problems admit linear-time solutions via dynamic programming on the clique tree, which for block graphs corresponds to the block-cut tree structure. The maximum clique size is simply the size of the largest block (clique), computable during biconnected component decomposition. Equitable coloring of block graphs, where color classes differ in size by at most one, can be solved in polynomial time using dynamic programming along the block tree, with applications to balanced scheduling problems such as resource allocation in tree-like networks.^[39]

Intersection Graph Representations

Block graphs admit a representation as the block intersection graph B(G) of some graph G. Specifically, for a connected graph G, the graph B(G) has a vertex for each block (maximal biconnected component) of G, and two vertices in B(G) are adjacent if and only if the corresponding blocks of G share a cut vertex. In this construction, the cliques of B(G) correspond to the sets of blocks incident to each cut vertex of G, and the overall structure ensures that every biconnected component of B(G) is a clique. Every block graph arises uniquely as B(G) for some connected graph G, providing a direct intersection model where the blocks of G serve as the intersecting sets.^[8] As a subclass of chordal graphs, block graphs also possess an intersection representation using subtrees of a tree. A graph is chordal if and only if it is the intersection graph of a family of subtrees of some tree T, meaning each vertex v of the graph is assigned a subtree S_v \subseteq T such that two vertices are adjacent precisely when their subtrees intersect. For block graphs, this representation aligns with their structure: the host tree T can be taken as a clique tree of the block graph, and the subtree S_v for each vertex v consists of the nodes of T (maximal cliques) that contain v. In block graphs, these subtrees S_v form connected subgraphs of T, and intersections between subtrees occur only at nodes corresponding to shared cut vertices or within single cliques.^[40] Block graphs are further characterized by their clique tree representations. A clique tree of a chordal graph is a tree whose nodes are the maximal cliques of the graph, with an edge between two nodes if the corresponding maximal cliques share vertices, satisfying the property that for any two maximal cliques, their intersection is contained in every maximal clique on the unique path between them in the tree. In a block graph, the maximal cliques coincide with the blocks, each of which is a clique, and the clique tree reflects the cut vertices: adjacent maximal cliques in the tree intersect at exactly one vertex (a cut vertex), while non-adjacent ones do not intersect. This tree structure encodes the articulation points, with each cut vertex labeling the intersection along tree edges.^[41] A precise intersection-theoretic characterization states that a graph is a block graph if and only if it is chordal and every pair of distinct maximal cliques intersects in at most one vertex. In this tree-like decomposition via the clique tree, the single-vertex intersections ensure no larger shared separators, distinguishing block graphs from general chordal graphs where maximal cliques may overlap in multiple vertices. This property guarantees that the intersection model remains faithful to the block structure, with cut vertices serving as the pivotal intersection points in the representation.^[42]

Comparisons to Other Classes

Block graphs form a proper subclass of chordal graphs, as every block graph is chordal by virtue of having no induced cycles of length greater than three—its biconnected components are cliques—but not every chordal graph is a block graph, excluding structures like split graphs where non-clique blocks exist.^[43] For instance, the diamond graph (K_4 minus an edge) is chordal but induces a non-clique biconnected component, placing it outside the block graph class. The intersection of block graphs and cographs consists precisely of cluster graphs, which are disjoint unions of cliques; block graphs permit cut vertices that connect cliques in tree-like fashion, potentially inducing P_4 subgraphs forbidden in cographs, while cographs built via disjoint union and join operations lack such articulations unless restricted to isolated cliques.^[44] Block graphs and threshold graphs are both subclasses of chordal graphs but are incomparable, as threshold graphs—characterized by forbidden induced 2K_2, P_4, and C_4 subgraphs—are P_4-free split graphs with a specific degree sequence ordering, whereas block graphs allow induced P_4 (as in paths of length three) and encompass structures beyond split graphs, such as arbitrary clique trees.^[45] Block graphs constitute a subclass of Ptolemaic graphs, which satisfy Ptolemy's inequality on distances for any four vertices; within Ptolemaic graphs, block graphs are distinguished by the property that every pair of vertices at distance two is connected by a unique shortest path.^[46] Although block graphs have occasionally been termed Husimi trees, this nomenclature more accurately applies to cactus graphs where every block is a cycle or single edge, differing from block graphs in that the latter permit cliques of arbitrary size rather than restricting to triangle-based or cycle-only blocks.^[47]

History and Applications

Historical Development

The concept of block graphs was introduced by Frank Harary in his 1963 paper "A Characterization of Block-Graphs", where they were defined as graphs in which every block (biconnected component) is a complete graph, serving as a natural model for the block-cutpoint structure of general graphs. This construction arises from the block graph of a graph G, which has vertices corresponding to the blocks of G and edges between vertices if the respective blocks share a cutpoint, providing a framework to study connectivity and decomposition in the 1970s.^[1] Early characterizations focused on metric properties, with Edward Howorka establishing in 1979 that block graphs are precisely the connected graphs where shortest paths are unique between any pair of vertices and every induced path is isometric, linking them to distance-hereditary graphs.^[48] Building on this, work in the mid-1980s explored their Ptolemaic nature; Victor Chepoi showed in 1986 that block graphs satisfy the Ptolemaic inequality—a four-point condition on distances—via an α₀-metric characterization, confirming their subclass within chordal and distance-hereditary graphs.^[49] Key contributions include Harary's foundational definition, H.M. Mulder's 1980 analysis of the interval function, which demonstrated that block graphs have subconvex interval functions and are λ-interval graphs for appropriate λ, and Robert E. Jamison's 1985 results on intersection representations, identifying block graphs as the edge intersection graphs of paths in trees.^[50] The study of block graphs evolved from initial block modeling in the 1970s to their integration into perfect graph theory during the 1980s and 1990s, as their chordal structure ensured strong perfect graph properties, including polynomial-time solvability for coloring and clique problems. In recent developments, particularly from the 2010s, attention has shifted to probe variants—graphs where vertices are partitioned into probes and non-probes, with edges only between probes or from probes to non-probes—yielding efficient recognition algorithms for probe block graphs.^[21] Algorithmic improvements include T.M. Wang's 1999 polynomial-time method for recognizing the P₄-structure of block graphs, facilitating broader structural analysis.^[37]

Practical Applications

Block graphs find application in modeling network reliability, where their block structure—consisting of cliques connected via cut vertices—facilitates analysis of fault tolerance in connected systems. By representing maximal biconnected components as cliques and articulation points as potential single points of failure, block graphs enable efficient computation of connectivity measures and vulnerability assessments, such as identifying critical nodes whose removal disconnects the network. This approach is useful in designing resilient communication and infrastructure networks, where the block-cut tree representation highlights hierarchical failure modes. Equitable colorings of block graphs, which partition vertices into color classes of nearly equal size while avoiding adjacent vertices sharing colors, have practical utility in scheduling and resource management scenarios. In timetabling for educational institutions, vertices represent courses or classes, edges denote conflicts (e.g., shared instructors or rooms), and equitable coloring ensures balanced distribution across time slots to optimize facility usage and instructor workloads. Similarly, in task allocation problems, such colorings balance computational loads across processors or workers, minimizing idle time in parallel processing environments. These applications leverage the polynomial-time solvability of equitable coloring on block graphs due to their tree-like clique structure, allowing efficient algorithms for large-scale instances. For transport networks, equitable colorings model route assignments to vehicles or tracks, promoting even traffic distribution and reducing bottlenecks.^[51]^[52] As a subclass of perfect graphs, block graphs enable polynomial-time optimization for problems like maximum independent set and coloring, which underpin resource allocation tasks. In scenarios involving precedence constraints modeled as graphs, the perfect property ensures that the clique number equals the chromatic number for every induced subgraph, allowing exact solutions via ellipsoid methods or separation oracles without exponential complexity. This facilitates applications in project scheduling and inventory management, where allocating limited resources (e.g., budget or personnel) to tasks respects conflict graphs while minimizing completion time. Such efficiency contrasts with general graphs, where these problems are NP-hard, making block graphs suitable for structured allocation in manufacturing and logistics. In biological networks, block graphs model protein-protein interaction (PPI) data by representing dense interaction clusters as cliques linked at shared articulation points (e.g., hub proteins). The "clique backbone" of a PPI network, which extracts the block graph by identifying maximal cliques as blocks and cut vertices as connectors, aids in predicting disease-related proteins by highlighting essential pathways and modular structures. This representation captures the modular nature of biological systems, where cliques denote functional complexes and cut vertices indicate regulatory points, enabling targeted analysis of disease propagation or drug targeting in networks like those derived from human proteome databases.^[53] Planar subclasses of block graphs, such as triangular cacti (where blocks are triangles forming a tree-like structure), support approximation algorithms for geometric optimization problems like maximum planar subgraph extraction. In these settings, greedy algorithms construct a maximum triangular cactus in linear time, achieving approximation ratios around 7/12 for finding large planar subgraphs in non-planar inputs, which is valuable for VLSI layout design and map simplification tasks requiring embedded planar representations. Local optimization refinements on these structures further improve ratios to (4/9) + ε, balancing computational efficiency with solution quality in geometric embedding problems.^[54]

References

[1]
A CHARACTERIZATION OF BLOCK-GRAPHS
A CHARACTERIZATION OF BLOCK-GRAPHS. Frank Harary. (received January 10, 1962). The purpose of this note is to characterize "block-graphs", a collection of ...
[2]
[PDF] Characterizing block graphs in terms of their vertex-induced partitions
A block graph is a graph in which every maximal 2-connected subgraph or block is a clique [1, 8]. Block graphs are a natural generalization of trees, and they ...
[3]
Distance-hereditary graphs - ScienceDirect.com
Distance-hereditary graphs (sensu Howorka) are connected graphs in which all induced paths are isometric. Examples of such graphs are provided by complete ...
[4]
(PDF) A characterization of block graphs - ResearchGate
Aug 10, 2025 · In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is ...
[5]
[PDF] arXiv:1611.06285v1 [math.CO] 19 Nov 2016
Nov 19, 2016 · Abstract. Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = (V,E) is said to be an ...<|control11|><|separator|>
[6]
https://ajc.maths.uq.edu.au/pdf/66/ajc_v66_p001.pdf
[7]
[PDF] arXiv:1808.03411v2 [cs.DS] 20 Nov 2018
Nov 20, 2018 · A block graph is a graph in which every block is a complete graph. ... West, D.B.: Introduction to graph theory, vol. 2. Prentice hall ...
[8]
https://www.cambridge.org/core/journals/canadian-mathematical-bulletin/article/characterization-of-blockgraphs/92858409D9B81918601D80C8BD145492
[9]
[PDF] CME 305: Discrete Mathematics and Algorithms Lecture 2 - Graph ...
Jan 11, 2018 · Definition 20 (Biconnectedness). We call a graph biconnected if every pair of vertices in the graph are. contained in a cycle. We call a ...
[10]
[PDF] Block decomposition
Block decomposition decomposes a graph into subgraphs (blocks), which are maximal connected subgraphs without a cut-vertex. The union of these blocks is the ...
[11]
[PDF] biconnected components
A graph with no articulation points is called biconnected or nonseparable. A maximal biconnected subgraph of a graph is called a biconnected component or a ...Missing: theory | Show results with:theory
[12]
14. Some Graph Theory - MIT Mathematics
A complete graph is often called a clique. The size of the largest clique that can be made up of edges and vertices of G is called the clique number of G.
[13]
[PDF] Section 9.7. Chordal Graphs
Jul 20, 2022 · 19). A chordal graph is a simple graph in which every cycle of length greater than three has a chord. Note 9.7. A.Missing: theory | Show results with:theory
[14]
[PDF] Maximum Cardinality Search and Chordal Graphs
Sep 25, 2018 · Definitions: • A graph G is chordal if every cycle of length > 3 has a chord, that is, an edge between vertices of the cycle that is not ...Missing: theory | Show results with:theory
[15]
[PDF] On the adjacency matrix of a block graph
Feb 1, 2013 · A block graph is a graph in which every block is a complete graph. Let G be a block graph and let A be the adjacency matrix of G. We first ...
[16]
[PDF] Excluded vertex-minors for graphs of linear rank-width at most k
Nov 11, 2013 · Since a diamond graph is not a block graph, we deduce that G is not a block graph. If B0 is a star bag with the center w0, then by ...<|control11|><|separator|>
[17]
Block Graph -- from Wolfram MathWorld
A block graph, also called a clique tree, is a simple graph in which every block is a complete graph.
[18]
Optimal Radio Labellings of Block Graphs and Line Graphs of Trees
Aug 29, 2021 · We prove that if a tree is a lower bound block graph then, under certain conditions, its line graph is also a lower bound block graph, and vice versa.
[19]
[PDF] arXiv:2402.17413v3 [math.AC] 26 Feb 2025
Feb 26, 2025 · Recall that a triangular cactus graph is a connected graph in which every block is a cycle of length 3. We will use a result of Katthän [9] ...
[20]
Characterizing and recognizing probe block graphs - ScienceDirect
Feb 23, 2015 · Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = ( V , E ) is said to be an (unpartitioned) ...
[21]
Nonsingular (vertex-weighted) block graphs - ScienceDirect.com
Oct 1, 2020 · Block graphs are a natural generalization of trees. A block in a graph is a maximal connected subgraph with no cut-vertex. A block graph is a ...
[22]
(PDF) Block digraph of a directed graph - ResearchGate
Aug 9, 2025 · A weighted cactoid digraph is a strongly connected directed graph whose blocks are weighted directed cycles such that any two distinct weighted ...
[23]
[PDF] On probe 2-clique graphs and probe diamond-free graphs - Hal-Inria
Mar 14, 2015 · block graphs are exactly the diamond-free chordal graphs. A graph is chordal if it has no Cn with n ≥ 4 as an induced subgraph. A graph is ...
[24]
[PDF] An Observation on Block Graphs - ResearchGate
A connected graph G is a block graph if ... Harary, A characterization of block-graphs. Canad. Math. Bull. 6 (1963), 1 - 6. [3] F. Harary, Graph Theory.
[25]
[PDF] A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex ...
Let G be a graph that does not contain C4 and D4 as an induced subgraph then (a) any two maximal cliques intersect on at most one vertex and (b) the number of ...
[26]
Properties and Recognition of Atom Graphs - MDPI
Aug 19, 2022 · The atom graph of a connected graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph ...<|control11|><|separator|>
[27]
A forbidden induced subgraph characterization of distance ...
Jun 28, 2009 · A graph is a block graph if each of its blocks is a clique. Clearly, a chordal graph is a block graph if and only if it is diamond-free (cf.
[28]
[PDF] A New Proof of the Szeged-Wiener Theorem
Jan 29, 2011 · The block graphs are natural generalization of trees. They are the ... (b) For every four vertices u, v, x, y of G, the greatest two ...
[29]
[PDF] Metric graph theory and geometry: a survey - CNU 27 Marseille
Metric graph theory studies graphs defined by distance properties, such as median, Helly, and bridged graphs, where geodesic distance plays a key role.
[30]
Block duplicate graphs and a hierarchy of chordal graphs
Dec 15, 2002 · A block duplicate (BD) graph is a graph obtained by adding true twins (ie, adjacent vertices with the same closed neighborhood) to vertices of a block graph.
[31]
A polynomial algorithm to compute the boxicity and threshold ... - arXiv
Oct 2, 2025 · Since block graphs are known to have boxicity at most two, computing their boxicity amounts to the linear-time interval graph recognition ...
[32]
The median function of a block graph: Axiomatic characterizations
May 15, 2024 · In this paper, we study the median sets and median function of block graphs, an immediate generalization of trees.
[33]
[PDF] Lecture notes for Mar 27, 2024 Chordal graphs and tree ...
Mar 27, 2024 · If we take C to be a maximum clique of G, we know the width of (T,X) is at least ω(G) − 1. Hence the tree-width of G is at least ω(G) − 1.
[34]
[PDF] Listing simplicial vertices and recognizing diamond-free graphs - Pure
Jan 1, 1994 · e is the number of edges in the graph. We present also a new algorithm for the recognition of diamond-free graphs using the same techniques.
[35]
Recognizing the P4-structure of block graphs - ScienceDirect
We shall give in this paper a simple algorithm that recognizes the P 4 -structure of a block graph in polynomial time.
[36]
[PDF] A Polynomial Algorithm for Recognizing Perfect Graphs
We present a polynomial algorithm for recognizing whether a graph is perfect, thus settling a long standing open question. The algorithm uses a ...
[37]
[PDF] Graph theoretic and algorithmic aspect of the equitable coloring ...
Nov 4, 2022 · (2021), we define a cluster graph as a graph formed from the disjoint union of complete graphs. For a given graph G, its distance to the ...
[38]
Spanning cactus of a graph: Existence, extension, optimization, and ...
In this case, we show that the MSCP is equivalent to a class of optimization problems that properly includes the TSP and they all have the same approximation ...
[39]
A Characterization of Block-Graphs | Canadian Mathematical Bulletin
Nov 20, 2018 · The purpose of this note is to characterize "block-graphs", a collection of graphs defined by a construction involving certain subgraphs called ...
[40]
The intersection graphs of subtrees in trees are exactly the chordal ...
The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more ...
[41]
[PDF] An introduction to chordal graphs and clique trees - People
Finally, a chord of a path (cycle) is any edge joining two nonconsecutive vertices of the path (cycle). Definition 1. An undirected graph G = (V, E ) is chordal ...
[42]
Vertex deletion problems on chordal graphs - ScienceDirect.com
Oct 12, 2018 · A graph is a block graph ... Moreover, block graphs are precisely those chordal graph in which any two maximal cliques share at most one vertex.
[43]
[PDF] Characterizing Block Graphs in Terms of One-vertex Extensions
Harary. A characterization of block graphs. Canadian Mathematical Bulletin, 6(1) (1963), 1–6. [8] E. Howorka. On metric properties of certain clique graphs ...
[44]
The cluster deletion problem for cographs - ScienceDirect.com
Cluster graphs have been used in a variety of applications whenever clustering ... The intersection graphs of subtrees in trees are exactly the chordal graphs.
[45]
Threshold Graph Limits and Random Threshold Graphs
Nov 4, 2009 · Threshold graphs have edges if wi + wj > t, and are built by adding isolated or dominant vertices, and have no 2K2, P4, or C4 subgraphs.
[46]
[PDF] A Polynomial Kernel for Deletion to Ptolemaic Graphs - DROPS
Block graphs are a subclass of Ptolemaic graphs, and Block Vertex Deletion is known to admit an FPT algorithm running in time 4knO(1) and a kernel with O(k4) ...
[47]
[PDF] A Characterization of Uniquely Representable Graphs - arXiv
Jun 20, 2020 · Block graphs were first studied by Harary in [40]. They ... Harary, A characterization of block-graphs, Canad. Math. Bull. 6 (1). (1963) 1–6.<|control11|><|separator|>
[48]
[PDF] graph theory 1 harary - DTIC
condition of Theorem 3.5 that L\H) is a block graph. Hence H is a tree, and ... [H28] A characterization of block-graphs. Canad. Math. Bull. 6 (1963X 1 ...
[49]
On metric properties of certain clique graphs - ScienceDirect.com
The paper provides a unified point of view on some classes of graphs: clique graphs, weakly geodetic graphs, ptolemaic graphs and Husimi trees.<|control11|><|separator|>
[50]
[PDF] The axiomatic characterization of the interval function of Ptolemaic ...
The axiomatic approach using transit functions in graphs is a tool for studying and characterizing graph classes. If V is the vertex set of a graph G and R a ...
[51]
Interval graphs and related topics - ScienceDirect.com
July 1985, Pages 113-121. Discrete Mathematics. Interval graphs and related ... Golumbic, R.E. Jamison. Edge and vertex intersection of paths in a tree.
[52]
Network Connectivity, Graph Theory, and Reliable Network Design
Graph Theory: Connectivity and Network Reliability ... In this session, you will learn what a cut-vertex is, and several ways of finding them in a network.
[53]
[PDF] Equitable coloring of graphs. Recent theoretical results and new ...
Abstract. In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible.
[54]
[PDF] Block graphs - some general results and their equitable colorings 1
Feb 7, 2024 · Abstract. In this paper, we consider some general properties of block graphs as well as the equitable coloring problem in this class of ...
[55]
[PDF] convex resource allocation problems on directed acyclic graphs ...
The resource allocation problem is how to optimally allocate the budget among the jobs in order to complete the project in the least amount of time. This model ...
[56]
Predicting Disease-Related Proteins Based on Clique Backbone in ...
Predicting Disease-Related Proteins Based on Clique Backbone in Protein-Protein Interaction Network. International Journal of Biological Sciences, 10(7), 677- ...
[57]
[PDF] An Improved Algorithm for Finding Maximum Outerplanar Subgraphs
Jun 14, 2023 · The greedy triangular cactus approximation algorithm from [3] results in a non-trivial approximation ratio of 7/12. Furthermore, [3] used the ...