ArticleOriginal scientific text
Title
Leaps: an approach to the block structure of a graph
Authors 1, 2
Affiliations
- Econometrisch Instituut, Erasmus Universiteit, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands
- Filozofická Fakulta, Univerzita Karlova v Praze, J. Palacha 2, 116 38 Praha 1, Czech Republic
Abstract
To study the block structure of a connected graph G = (V,E), we introduce two algebraic approaches that reflect this structure: a binary operation + called a leap operation and a ternary relation L called a leap system, both on a finite, nonempty set V. These algebraic structures are easily studied by considering their underlying graphs, which turn out to be block graphs. Conversely, we define the operation as well as the set of leaps of the connected graph G. The underlying graph of , as well as that of , turns out to be just the block closure of G (i.e., the graph obtained by making each block of G into a complete subgraph).
Keywords
leap, leap operation, block, cut-vertex, block closure, block graph
Bibliography
- M. Changat, S. Klavžar and H.M. Mulder, The all-path transit function of a graph, Czechoslovak Math. J. 51 (2001) 439-448, doi: 10.1023/A:1013715518448.
- F. Harary, A characterization of block graphs, Canad. Math. Bull. 6 (1963) 1-6, doi: 10.4153/CMB-1963-001-x.
- F. Harary, Graph Theory (Addison-Wesley, Reading MA, 1969).
- M.A. Morgana and H.M. Mulder, The induced path convexity, betweenness, and svelte graphs, Discrete Math. 254 (2002) 349-370, doi: 10.1016/S0012-365X(01)00296-5.
- H.M. Mulder, The interval function of a graph (MC-tract 132, Mathematish Centrum, Amsterdam 1980).
- H.M. Mulder, Transit functions on graphs, in preparation.
- L. Nebeský, A characterization of the interval function of a graph, Czechoslovak Math. J. 44 (119) (1994) 173-178.
- L. Nebeský, Geodesics and steps in a connected graph, Czechoslovak Math. J. 47 (122) (1997) 149-161.
- L. Nebeský, An algebraic characterization of geodetic graphs, Czechoslovak Math. J. 48 (123) (1998) 701-710.
- L. Nebeský, A tree as a finite nonempty set with a binary operation, Mathematica Bohemica 125 (2000) 455-458.
- L. Nebeský, New proof of a characterization of geodetic graphs, Czechoslovak Math. J. 52 (127) (2002) 33-39.