# On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 1, page 127-136
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDingguo Wang, and Erfang Shan. "On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 127-136. <http://eudml.org/doc/267975>.

@article{DingguoWang2014,

abstract = {A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.},

author = {Dingguo Wang, Erfang Shan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {4-regular graph; claw-free; cut-vertices; end-blocks},

language = {eng},

number = {1},

pages = {127-136},

title = {On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs},

url = {http://eudml.org/doc/267975},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Dingguo Wang

AU - Erfang Shan

TI - On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 1

SP - 127

EP - 136

AB - A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.

LA - eng

KW - 4-regular graph; claw-free; cut-vertices; end-blocks

UR - http://eudml.org/doc/267975

ER -

## References

top- [1] M.O. Albertson and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Math. 89 (1991) 97-100. doi:10.1016/0012-365X(91)90402-N[Crossref]
- [2] B. Bollobás, Modern Graph Theory (New York, Springer-Verlag, 2001).
- [3] L.H. Clark and R.C. Entringer, The number of cut vertices in graphs with given minimum degree, Discrete Math. 18 (1990) 137-145. doi:10.1016/0012-365X(90)90145-8[Crossref]
- [4] K. Nirmala and A.R. Rao, The number of cut vertices in a regular graph, Cahiers Centre Etudes Reserche Oper. 17 (1975) 295-299. Zbl0321.05138
- [5] N. Achuthan and A.R. Rao, On the number of cut edges in a regular graph, Australas. J. Combin. 27 (2003) 5-12. Zbl1021.05055
- [6] A. Ramachandra Rao, An extremal problem in graph theory, Israel J. Math. 6 (1968) 261-266. doi:10.1007/BF02760258[Crossref] Zbl0174.55201
- [7] A. Ramachandra Rao, Some extremal problems and characterizations in the theory of graphs, Ph.D. Thesis, Indian Statistical Institute (1969).
- [8] S.B. Rao, Contributions to the theory of directed and undirected graphs, Ph.D. Thesis, Indian Statistical Institute (1970).
- [9] O. Suil and D.B. West, Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, J. Graph Theory 64 (2010) 116-131. doi:10.1002/jgt.20443 [WoS][Crossref] Zbl1201.05049

## NotesEmbed ?

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