Geodesic
On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 127-136.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: 4-regular graph, claw-free, cut-vertices, end-blocks 
@article{DMGT_2014_34_1_a10,
     author = {Wang, Dingguo and Shan, Erfang},
     title = {On the {Numbers} of {Cut-Vertices} and {End-Blocks} in {4-Regular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {127--136},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a10/}
}
TY  - JOUR
AU  - Wang, Dingguo
AU  - Shan, Erfang
TI  - On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 127
EP  - 136
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a10/
LA  - en
ID  - DMGT_2014_34_1_a10
ER  - 
%0 Journal Article
%A Wang, Dingguo
%A Shan, Erfang
%T On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 127-136
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a10/
%G en
%F DMGT_2014_34_1_a10
Wang, Dingguo; Shan, Erfang. On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 127-136. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a10/

[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

[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

[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.

[5] N. Achuthan and A.R. Rao, On the number of cut edges in a regular graph, Australas. J. Combin. 27 (2003) 5-12.

[6] A. Ramachandra Rao, An extremal problem in graph theory, Israel J. Math. 6 (1968) 261-266. doi:10.1007/BF02760258

[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