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

Dingguo Wang; Erfang Shan

Discussiones Mathematicae Graph Theory (2014)

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

Abstract

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

How to cite

top

Dingguo 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. [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. [2] B. Bollobás, Modern Graph Theory (New York, Springer-Verlag, 2001). 
  3. [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. [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. [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. [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. [7] A. Ramachandra Rao, Some extremal problems and characterizations in the theory of graphs, Ph.D. Thesis, Indian Statistical Institute (1969). 
  8. [8] S.B. Rao, Contributions to the theory of directed and undirected graphs, Ph.D. Thesis, Indian Statistical Institute (1970). 
  9. [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 ?

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.