Leaps: an approach to the block structure of a graph

Henry Martyn Mulder; Ladislav Nebeský

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 77-90
  • ISSN: 2083-5892

Abstract

top
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 + G as well as the set of leaps L G of the connected graph G. The underlying graph of + G , as well as that of L G , 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).

How to cite

top

Henry Martyn Mulder, and Ladislav Nebeský. "Leaps: an approach to the block structure of a graph." Discussiones Mathematicae Graph Theory 26.1 (2006): 77-90. <http://eudml.org/doc/270237>.

@article{HenryMartynMulder2006,
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 $+_G$ as well as the set of leaps $L_G$ of the connected graph G. The underlying graph of $+_G$, as well as that of $L_G$, 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).},
author = {Henry Martyn Mulder, Ladislav Nebeský},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {leap; leap operation; block; cut-vertex; block closure; block graph},
language = {eng},
number = {1},
pages = {77-90},
title = {Leaps: an approach to the block structure of a graph},
url = {http://eudml.org/doc/270237},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Henry Martyn Mulder
AU - Ladislav Nebeský
TI - Leaps: an approach to the block structure of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 77
EP - 90
AB - 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 $+_G$ as well as the set of leaps $L_G$ of the connected graph G. The underlying graph of $+_G$, as well as that of $L_G$, 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).
LA - eng
KW - leap; leap operation; block; cut-vertex; block closure; block graph
UR - http://eudml.org/doc/270237
ER -

References

top
  1. [1] 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. Zbl0977.05135
  2. [2] F. Harary, A characterization of block graphs, Canad. Math. Bull. 6 (1963) 1-6, doi: 10.4153/CMB-1963-001-x. Zbl0112.25002
  3. [3] F. Harary, Graph Theory (Addison-Wesley, Reading MA, 1969). 
  4. [4] 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. Zbl1003.05090
  5. [5] H.M. Mulder, The interval function of a graph (MC-tract 132, Mathematish Centrum, Amsterdam 1980). 
  6. [6] H.M. Mulder, Transit functions on graphs, in preparation. Zbl1166.05019
  7. [7] L. Nebeský, A characterization of the interval function of a graph, Czechoslovak Math. J. 44 (119) (1994) 173-178. Zbl0808.05046
  8. [8] L. Nebeský, Geodesics and steps in a connected graph, Czechoslovak Math. J. 47 (122) (1997) 149-161. Zbl0898.05041
  9. [9] L. Nebeský, An algebraic characterization of geodetic graphs, Czechoslovak Math. J. 48 (123) (1998) 701-710. Zbl0949.05022
  10. [10] L. Nebeský, A tree as a finite nonempty set with a binary operation, Mathematica Bohemica 125 (2000) 455-458. Zbl0963.05032
  11. [11] L. Nebeský, New proof of a characterization of geodetic graphs, Czechoslovak Math. J. 52 (127) (2002) 33-39. Zbl0995.05124

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.