Characterizing Block Graphs in Terms of One-vertex Extensions

Lilian Markenzon, Christina Fraga Esteves Maciel Waga

Abstract


Block graphs has been extensively studied for many decades. In this paper we present a new characterization of the class in terms of one-vertex extensions. To this purpose, a specific representation based on the concept of boundary cliques is presented, bringing about some properties of the graph.


Keywords


block graph, one-vertex-extension

Full Text:

PDF

References


F. Harary, “A characterization of block graphs,” Canadian Mathematical Bul- letin, vol. 6, no. 1, pp. 1–6, 1963.

E. Howorka, “On metric properties of certain clique graphs,” Journal of Com- binatorial Theory, Series B, vol. 27, pp. 67–74, 1979.

H.-J. Bandelt and H. M. Mulder, “Three interval conditions for graphs,” Ars Combinatoria, vol. 29B, pp. 213–223, 1990.

A. Behtoei, M. Jannesari, and B. Taeri, “A characterization of block graphs,” Discrete Applied Mathematics, vol. 158, pp. 219–221, 2010.

H.-J. Bandelt and H. M. Mulder, “Distance-hereditary graphs,” Journal of Combinatorial Theory, Series B, vol. 41, pp. 182–208, 1986.

H. Mulder and L. Nebeský, “Leaps: an approach to the block structure of a graph,” Discussiones Mathematicae Graph Theory, vol. 26, pp. 77–90, 2006.

A. Dress, K. Huber, J. Koolen, V. Moulton, and A. Spillner, “Characterizing block graphs in terms of their vertex-induced partitions,” Australasian Journal of Combinatorics, vol. 66, no. 1, pp. 1–9, 2016.

H. Mulder, “An observation on block graphs,” Bulletin of the Institute of Com- binatorics and its Applications, vol. 77, pp. 57–58, 2016.

J. R. S. Blair and B. Peyton, “An introduction to chordal graphs and clique trees,” In Graph Theory and Sparse Matrix Computation, IMA, vol. 56, pp. 1– 29, 1993.

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 2 ed., 2004.

L. Markenzon, P. R. C. Pereira, C. F. E. M. Waga, C. V. P. Friedmann, and A. Lozano, “An efficient representation of chordal graphs,” Operations Research Letters, vol. 41, pp. 331–335, 2013.

D. J. Rose, R. E. Tarjan, and G. Lueker, “Algorithmic aspects of vertex elimination on graphs,” SIAM Journal on Computing, vol. 5, pp. 266–283, 1976.




DOI: https://doi.org/10.5540/tema.2019.020.02.323

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia