RUS  ENG
Full version
JOURNALS // Vladikavkazskii Matematicheskii Zhurnal // Archive

Vladikavkaz. Mat. Zh., 2019 Volume 21, Number 1, Pages 74–78 (Mi vmj686)

Notes

Block graph of a graph

A. Kelkar, K. Jaysurya, H. M. Nagesh

Department of Computer Science and Engineering, P.E.S. Institute of Technology, Bangalore South Campus, Bangalore, Karnataka 560100, India

Abstract: The block graph of a graph $G$, written $B(G)$, is the graph whose vertices are the blocks of $G$ and in which two vertices are adjacent whenever the corresponding blocks have a cut-vertex in common. We study the properties of $B(G)$ and present the characterization of graphs whose $B(G)$ are planar, outerplanar, maximal outerplanar, minimally non-outerplanar, Eulerian, and Hamiltonian. A necessary and sufficient condition for $B(G)$ to have crossing number one is also presented.

Key words: crossing number, inner vertex number, dutch windmill graph, complete graph.

UDC: 519.17

MSC: 05C05, 05C45

Received: 07.03.2018

Language: English

DOI: 10.23671/VNC.2019.1.27736



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024